Tuesday, 20 January 2015

Implementation of the Binary tree in C++ working code and tests

Implementation of the Binary tree in Cpp working code and tests:

From the previous posts we have seen the different possible problems and the solutions related to the binary trees.

Some of those are
Creating the binary tree [Creating the binary tree and find the size in C++ with examples]
Binary tree Traversals (in-order, pre-order & post- order)[ Binary Search tree in C++(BST) with examples]
Finding the size of the existing binary tree [Creating the binary tree and find the size in C++ with examples]
Inserting the data into the binary tree [Explain inserting the data into the Binary Tree in C++ with code examples ]
Finding maximum depth [Finding the maximum and minimum depth of the binary trees in C++ with examples]
Finding the minimum depth [Finding the maximum and minimum depth of the binary trees in C++ with examples]
Finding the total sum of the path of the Binary Tree [Finding the sum of the path of Binary tree in C++ with examples]
Finding the mirror of the tree [Finding the mirror of the binary tree with the solution in C++ with example]
Doubling the tree [Double the binary tree with the example in C++] etc.

Now, we can find the working code of the binary search tree.


Header files for the binary tree "BTreePointers.h"
#ifndef _BTREE_POINTERS_H_

#define _BTREE_POINTERS_H_
typedef struct stbst {
    int iData;
    stbst *pcLeftNode,
          *pcRightNode;          
}stBST;
class BTreePointers
{
public:
             /* This is the constructor of the class */
           BTreePointers ();
    /* This is the destructor of the class */  
  virtual ~BTreePointers ();
    /* This function is used to insert the given node in the tree */
  stBST* Insert (stBST *pcBST, int iIndex);
    /* This fucntion is used to create the node */
  stBST* CreateNode (int iData);
    /* This function is used to search the given node in the tree */
  bool SearchNode (stBST *pstBST, int iVal);
    /* This function is used to find the totla size of the tree */
  int Size (stBST *pstBST);
    /* This function is used to find the maximum depth of
       the tree, the number of nodes along the longest path 
       from the root node down to the farthest leaf node.*/
  int DepthMax (stBST *pstBST);
    /* This function is used to find the minimum depth of the tree,
       the number of nodes along the least path from
       the root node down to the nearest leaf node.*/
  int DepthMin (stBST *pstBST);
    /* This function is used to find the minimum depth of the tree */
  int MinimimVal (stBST *pstBST);
    /* This function is used to find the minimum depth of the tree */
  int MaximumVal (stBST *pstBST);
    /* This function is used to print the tree in the inorder traversal
       Iterate over each node and print them in increasing order */
  void PrintInOrder (stBST *pstBST);
    /* This function is used to print the tree in the post order traversal
       according to the bottom up approch.both subtrees of a node are
       printed out completely before the node itself is printed, and each
       left subtree is printed before the right subtree. */
  void PrintPostOrder (stBST *pstBST);
    /* This function is used to print
       the tree in the pre order traversal  */
  void PrintPreOrder (stBST *pstBST);
    /* This function is used to find the sum of the ROOTS.
       define a "root-to-leaf path" to be a sequence of nodes
       in a tree starting with the root node and proceeding
       downward to a leaf. That is an empty tree contains
       no root-to-leaf paths. */
  int FindSumOfPath (stBST *pstBST, int iSum);
    /* This function is used to print the paths
       presented in the tree. use the recursive function
       to print all the paths from root to child */
  void ShowPaths (stBST *pstBST);
    /* This function is used to changethe tree so
       that the roles of the left and right
       pointers are swapped at every node */
  void ShoowMirror (stBST *pstBST);

    /* This function is used for each node in a binary
       search tree, create a new duplicate node, and insert
       the duplicate as the left child of the original node.
       The resulting tree should still be a binary search tree.*/
  void Duplicate2Left (stBST *pstBST);

    /* This function is used to return true
       if they are structurally identical.*/
  int Equal (stBST *pstBST1, stBST *pstBST2);
};

Implementation of the binary tree
#include "stdafx.h"
#include "BTreePointers.h"
#include <iostream>
using namespace std;
/* This is the constructor of the class */
BTreePointers::BTreePointers ()
  { }
/* This is the destructor of the class */
BTreePointers::~BTreePointers ()
 { }
  /* This function is used to insert the given node in the tree */
stBST* BTreePointers::CreateNode (int iData)
{
  stBST *pstBST = new stBST;

  pstBST->iData = iData;

  pstBST->pcLeftNode = NULL;

  pstBST->pcRightNode = NULL;

  return pstBST;
}
 /* This fucntion is used to create the node */
stBST* BTreePointers::Insert (stBST *pcBST, int iData)
{
  if (pcBST == NULL)
    { return (CreateNode (iData)); }
  if (iData <= pcBST->iData)
    { pcBST->pcLeftNode = Insert (pcBST->pcLeftNode, iData); }
  else
    { pcBST->pcRightNode = Insert (pcBST->pcRightNode, iData); }
  return pcBST;
}
  /* This function is used to search the given node in the tree */
bool BTreePointers::SearchNode (stBST *pstBST, int iVal)
{
  if (pstBST == NULL)
    { cout << "Tree is empty" << endl; return false; }
  else if (iVal >= pstBST->iData)
    { return SearchNode (pstBST->pcRightNode, iVal); }
  else
    { return SearchNode (pstBST->pcLeftNode, iVal); }
}
  /* This function is used to find the totla size of the tree */
int BTreePointers::Size (stBST *pstBST)
{
  if (pstBST == NULL)
    { return 0; }
  else {
     return (Size (pstBST->pcLeftNode) + 1 + Size (pstBST->pcRightNode));
  }
}
  /* This function is used to find the maximum depth of the tree,

     the number of nodes along the longest path from

     the root node down to the farthest leaf node.*/

int BTreePointers::DepthMax (stBST *pstBST)
{
  if (pstBST == NULL)
    { return -1; }
  else {
    int iRightDepth = DepthMax (pstBST->pcRightNode);
    int iLeftDepth  = DepthMax (pstBST->pcLeftNode);
    if (iLeftDepth > iRightDepth)
      { return iLeftDepth + 1; }
    else
      { return iRightDepth + 1; }
  }
}
  /* This function is used to find the minimum depth of the tree,
     the number of nodes along the least path from
     the root node down to the nearest leaf node.*/
int BTreePointers::DepthMin (stBST *pstBST)
{
  if (pstBST == NULL)
    { return -1; }
  else {
    int iRightDepth = DepthMin (pstBST->pcRightNode);
    int iLeftDepth  = DepthMin (pstBST->pcLeftNode);
    if (iLeftDepth < iRightDepth)
      { return iLeftDepth + 1; }
    else
      { return iRightDepth + 1; }
  } 
}
  /* This function is used to find the minimum value of the tree,
     here there is no need to traverse total tree */
int BTreePointers::MinimimVal (stBST *pstBST)
{
  if (pstBST == NULL)
    { return -1; }
  while (pstBST->pcLeftNode != NULL)
    { pstBST = pstBST->pcLeftNode; }
  return (pstBST->iData);
}
/* This function is used to find the minimum value of the tree,
     here there is no need to traverse total tree */
int BTreePointers::MaximumVal (stBST *pstBST)
{
  if (pstBST == NULL)
    { return -1; }
  while (pstBST->pcRightNode != NULL)
    { pstBST = pstBST->pcRightNode; }
  return (pstBST->iData);
}
  /* This function is used to print the tree in the inorder traversal
     Iterate over each node and print them in increasing order */
void BTreePointers::PrintInOrder (stBST *pstBST)
{
  if (pstBST == NULL)
    { return; }
  PrintInOrder (pstBST->pcLeftNode);
  cout << pstBST->iData << "\t";
  PrintInOrder (pstBST->pcRightNode);
}
  /* This function is used to print the tree in the post order traversal
     according to the bottom up approch.both subtrees of a node are
     printed out completely before the node itself is printed, and each
     left subtree is printed before the right subtree. */
void BTreePointers::PrintPostOrder (stBST *pstBST)
{
  if (pstBST == NULL)
    { return; }
  PrintPostOrder (pstBST->pcLeftNode);
  PrintPostOrder (pstBST->pcRightNode);
  cout << pstBST->iData << "\t";
}
  /* This function is used to print the tree in the pre order traversal  */
void BTreePointers::PrintPreOrder (stBST *pstBST)
{
  if (pstBST == NULL)
    { return; }
  cout << pstBST->iData << "\t";
  PrintPreOrder (pstBST->pcLeftNode);
  PrintPreOrder (pstBST->pcRightNode);
}
    /* This function is used to find the sum of the ROOTS.
       define a "root-to-leaf path" to be a sequence of nodes
       in a tree starting with the root node and proceeding
       downward to a leaf. That is an empty tree contains
       no root-to-leaf paths. */
int BTreePointers::FindSumOfPath (stBST *pstBST, int iSum)
{
  if (pstBST == NULL)
    { return -1; }
  else {
    int iTemp = iSum - pstBST->iData;
    return (FindSumOfPath (pstBST->pcLeftNode, iTemp) ||
            FindSumOfPath (pstBST->pcRightNode, iTemp));         
  }
}
  /* This function is used to print the paths
     presented in the tree. use the recursive function
     to print all the paths from root to child */
void BTreePointers::ShowPaths (stBST *pstBST)
{
}
  /* This function is used to changethe tree so
     that the roles of the left and right
     pointers are swapped at every node */
void BTreePointers::ShoowMirror (stBST *pstBST)
{
  if (pstBST == NULL)
    { return; }
  else {
    stBST *pstTemp = NULL;
    ShoowMirror (pstBST->pcLeftNode);
    ShoowMirror (pstBST->pcRightNode);
    pstTemp             = pstBST->pcLeftNode;
    pstBST->pcLeftNode  = pstBST->pcRightNode;
    pstBST->pcRightNode = pstTemp;
  }
}
void BTreePointers::Duplicate2Left (stBST *pstBST)
{
   stBST *pstTemp = NULL;
   if (pstBST == NULL)
    { return; }
  else {
    Duplicate2Left (pstBST->pcLeftNode);
    Duplicate2Left (pstBST->pcRightNode);
    pstTemp = pstBST->pcLeftNode;
    pstBST->pcLeftNode = CreateNode (pstBST->iData);
    pstBST->pcLeftNode->pcLeftNode = pstTemp;
  }
}
  /* This function is used to return true
     if they are structurally identical.*/
int BTreePointers::Equal (stBST *pstBST1, stBST *pstBST2)
{
  if (pstBST1 == NULL && pstBST2 == NULL)
    { return true; }
  else if (pstBST1 != NULL && pstBST2 != NULL) {   
    return ((pstBST1->iData == pstBST2->iData) &&
      Equal (pstBST1->pcLeftNode,  pstBST2->pcLeftNode) &&
      Equal (pstBST1->pcRightNode, pstBST2->pcRightNode));
  }
  return false;
}
Testing of the Binary tree functions
#include "stdafx.h"

#include <string>
#include <iostream>
#include "BTreePointers.h"
using namespace std;
int main ()
{
  BTreePointers ocPBST, ocPBST1;
  stBST *pcBSt= NULL, *pcBSt1 = NULL;
  pcBSt = ocPBST.Insert (pcBSt, 2);
  pcBSt = ocPBST.Insert (pcBSt, 1);
  pcBSt = ocPBST.Insert (pcBSt, 3);
  pcBSt = ocPBST.Insert (pcBSt, 12);
  pcBSt = ocPBST.Insert (pcBSt, 4);
  pcBSt = ocPBST.Insert (pcBSt, 5);
  int iSize = ocPBST.Size (pcBSt);
  int iMaxDepth = ocPBST.DepthMax (pcBSt);

  cout << "Max Depth:\t" << iMaxDepth << endl;

  int iMinDepth = ocPBST.DepthMin (pcBSt);

  cout << "Min Depth:\t" << iMinDepth << endl;

  int iMinValue = ocPBST.MinimimVal (pcBSt);

  cout << "Max Val:\t" << iMinValue << endl;

  int iMaxValue = ocPBST.MaximumVal (pcBSt);

  cout << "Max Val:\t" << iMaxValue << endl;

  cout << "In-Order:\t";

  ocPBST.PrintInOrder (pcBSt);

  cout << ' ' << endl;

  cout << "Pre-Order:\t";

  ocPBST.PrintPreOrder (pcBSt);

  cout << ' ' << endl;

  cout << "Post-Order:\t";

  ocPBST.PrintPostOrder (pcBSt);

  cout << ' ' << endl;

  int iSum = ocPBST.FindSumOfPath (pcBSt, 0); // need to verify

  cout << "Sum of the path:\t" << iSum << endl;

  ocPBST.ShoowMirror (pcBSt);

  cout << "Mirror image created" <<endl;

  cout << "In-Order:\t";

  ocPBST.PrintInOrder (pcBSt);

  cout << ' ' << endl;

  cout << "Pre-Order:\t";

  ocPBST.PrintPreOrder (pcBSt);

  cout << ' ' << endl;

  cout << "Post-Order:\t";

  ocPBST.PrintPostOrder (pcBSt);

  cout << ' ' << endl;

  ocPBST.Duplicate2Left (pcBSt);

  cout << "Tree duplicated successfully" << endl;

  cout << "In-Order:\t";

  ocPBST.PrintInOrder (pcBSt);

  cout << ' ' << endl;

  cout << "Pre-Order:\t";

  ocPBST.PrintPreOrder (pcBSt);

  cout << ' ' << endl;

  cout << "Post-Order:\t";

  ocPBST.PrintPostOrder (pcBSt);

  cout << ' ' << endl;

  pcBSt1 = ocPBST.Insert (pcBSt1, 2);

  pcBSt1 = ocPBST.Insert (pcBSt1, 1);

  pcBSt1 = ocPBST.Insert (pcBSt1, 3);

  pcBSt1 = ocPBST.Insert (pcBSt1, 12);

  pcBSt1 = ocPBST.Insert (pcBSt1, 4);

  pcBSt1 = ocPBST.Insert (pcBSt1, 5);

  int bStatus = ocPBST.Equal (pcBSt, pcBSt1);

  if (bStatus)

    { cout << "Trees are structurally equal "<< endl; }

  else { cout << "Trees are structurally not equal "<< endl; }

  delete pcBSt; pcBSt = NULL;

  getchar ();

}

The output of the above program is
Max Depth:      4

Min Depth:      1

Max Val:        1

Max Val:        12

In-Order:       1       2       3       4       5       12

Pre-Order:      2       1       3       12      4       5

Post-Order:     1       5       4       12      3       2

Sum of the path:        1

Mirror image created

In-Order:       12      5       4       3       2       1

Pre-Order:      2       3       12      4       5       1

Post-Order:     5       4       12      3       1       2

Tree duplicated successfully

In-Order:       12      12      5       5       4       4       3       3

2       2       1       1

Pre-Order:      2       2       3       3       12      12      4       4

5       5       1       1

Post-Order:     12      5       5       4       4       12      3       3

2       1       1       2



No comments: