Subscribe to Indyarocks' Blog

## A simple and working Binary tree implementation in C++

Here is the snippet, any crib, post me :)
## WHAT IT DOES ??
/*Writing a binary tree
Requirements:
1. Find if a data is duplicate
2. Insert a data in the BTree
3. Check if two BTree are equal or no.
4. Assign a BTree.
5. Delete a data
6. Traverse in a.In-order, b.Pre-order, c.Post-order
*/

```#include <iostream>

using namespace std;

struct Node
{
Node *left;
int data;
Node *right;
};

class BST
{
public:
BST() { pHead = NULL;}          //Constructor
//  BST(const BST&);                //Copy constructor
void destruct(Node *);          //Destructor Helper
bool compare(Node *p,Node *q);  //Helper for "==" operator overloaded function
friend ostream& operator<< (ostream&, Node&);//To print the data of a Node
void Search(int num, bool &found, Node *&parent, Node *&x);    //Helper for Insert and Delete function
void Insert(int num);           //Insert a number into tree
void Delete(int num);           //Delete a number from tree
Node * copy(Node *p,Node *q);   //Helper copy funtion for "=" operator
void Traversal();               //Tree traversal
void In(Node *);                //In order traversal
void Pre(Node *);               //Pre order traversal
void Post(Node *);              //Post order traversal
static int GetCount() { return count;}//Public method to get the count of nodes
private:
static int count;               //Count of Nodes in tree
};

int BST::count = 0;                 //Initialize static counter.

//BST(const BST&);                //Copy constructor

void BST::destruct(Node *p)     //Destructor Helper
{
if(p == NULL)
return;

destruct(p->left);
destruct(p->right);
delete p;

}
{
}
bool BST::compare(Node *p,Node *q)//Helper for "==" operator overloaded function
{
static bool flag = 1;
if(p == NULL && q == NULL)
return flag;

if(p->data == q->data && flag == 1)
{
flag = compare(p->left,q->left);
flag = compare(p->right,q->right);
}
else flag = 0;
return flag;
}
ostream& operator<< (ostream &theStream, Node *&p)//To print the data of a Node
{
if(p != NULL)
{
theStream << p->data;
}
else
theStream << NULL;
return theStream;
}
//num : Number to find
//found: Found flag
//parent: Parent of the Node to be inserted or deleted
//x: Node to be deleted
void BST::Search(int num, bool &found, Node *&parent,Node *&x)    //Helper for Insert and Delete function
{
return;

Node *temp;
while(temp != NULL)
{
if(temp->data == num)
{
found = 1;
x = temp;
return;
}
if(temp->data > num)
{
parent = temp;
temp = temp->left;
}
else if(temp->data < num)
{
parent = temp;
temp = temp->right;
}
}
}

void BST::Insert(int num)       //Insert a number into tree
{
bool found = 0;
Node *parent = NULL;
Node *x = NULL;
Search(num,found,parent,x);
if(found == 1)
{
cout << "The number " << num << " already exists in tree" << endl;
return;
}
count++;                    //Increase the count of data
Node *temp = new Node;
temp->data = num;
temp->left = NULL;
temp->right = NULL;
{
return;
}
(parent->data > num)?(parent->left = temp):(parent->right = temp);
}

void BST::Delete(int num)       //Delete a number from tree
{
bool found = 0;
Node *parent = NULL;
Node *x = NULL;
Search(num,found,parent,x);
if(found == 0)
{
cout << "The number " << num << " doesn't exists in tree." << endl;
return;
}
count--;                    //Decrease the count of data
Node *xSucc;
// When a Node to be deleted has two successor
if(x->left != NULL && x->right != NULL)
{
//First get the In-Order successor of x
parent = x;
xSucc = x->right;       // Go one right and then
while(xSucc->left != NULL)  // go to left most children
{
parent = xSucc;
xSucc = xSucc->left;
}
x->data = xSucc->data; //Replace the data in x by data of its In-Order successor
x = xSucc;             //Now we just need to delete the node xSucc, which have
// 0 or one right children.
}
//When a node to be deleted has no children
if(x->left == NULL && x->right == NULL)
{
if(parent->left == x)
{
parent->left = NULL;
delete x;
return;
}
else
{
parent->right = NULL;
delete x;
return;
}
}
//When a node to be deleted has one right children
if(x->right != NULL && x->left == NULL)
{
if(parent->left == x)
{
parent->left = x->right;
delete x;
return;
}
else
{
parent->right = x->right;
delete x;
return;
}
}
//When a node to be deleted has one left children
if(x->left != NULL && x->right == NULL)
{
if(parent->left == x)
{
parent->left = x->left;
delete x;
return;
}
else
{
parent->right = x->left;
delete x;
return;
}
}
}

{
}
Node * BST::copy(Node *p,Node *q)//Helper copy funtion for "=" operator
{
if(q == NULL)
return NULL;

Node *temp = new Node;
temp->data = q->data;
temp->left = copy(temp->left,q->left);
temp->right = copy(temp->right,q->right);
return temp;
}

void BST::Traversal()           //Tree traversal
{
bool fQuit = 1;
int choice;
while(fQuit)
{
cout << "1.Pre-order, 2. In-order, 3.Post-order, 0.Quit" << endl;
cin >> choice;
switch(choice)
{
default: fQuit = 0; break;
}
cout << endl;
}

}
void BST::In(Node *p)             //In order traversal
{
if(p != NULL)
{
In(p->left);
cout << p->data << "\t";
In(p->right);
}
}

void BST::Pre(Node *p)           //Pre order traversal
{
if(p != NULL)
{
cout << p->data << "\t";
Pre(p->left);
Pre(p->right);
}
}
void BST::Post(Node *p)           //Post order traversal
{
if(p != NULL)
{
Post(p->left);
Post(p->right);
cout << p->data << "\t";
}
}

```

Driver File:
```#include "BinaryTree.hpp"

int main()
{
BST t1;
cout << "Trying to insert 3,9,2,6,4,10,32,4,55,58,56,12,11 in tree t1\n\n" << endl;
cout << "Inserting 3" << endl;
t1.Insert(3);
cout << "Inserting 9" << endl;
t1.Insert(9);
cout << "Inserting 2" << endl;
t1.Insert(2);
cout << "Inserting 6" << endl;
t1.Insert(6);
cout << "Inserting 4" << endl;
t1.Insert(4);
cout << "Inserting 10" << endl;
t1.Insert(10);
cout << "Inserting 32" << endl;
t1.Insert(32);
cout << "Inserting 4## DUPLICATE" << endl;
t1.Insert(4);
cout << "Inserting 55" << endl;
t1.Insert(55);
cout << "Inserting 58" << endl;
t1.Insert(58);
cout << "Inserting 56" << endl;
t1.Insert(56);
cout << "Inserting 12" << endl;
t1.Insert(12);
cout << "Inserting 11" << endl;
t1.Insert(11);

t1.Traversal();

cout << "Trying to delete an element 100, which is not in t1"<< endl;
t1.Delete(100);

cout << "Deleting 6 " << endl;
t1.Delete(6);
t1.Traversal();

cout << "Deleting 9 " << endl;
t1.Delete(9);
t1.Traversal();

cout << "Deleting 10 " << endl;
t1.Delete(10);
t1.Traversal();

cout << "Deleting 2 " << endl;
t1.Delete(2);
t1.Traversal();

BST t2;
cout << "Empty t2" << endl;
t2.Traversal();

cout << "Doing t2 = t1" << endl;
t2 = t1;
t2.Traversal();

cout << "Checking t2 == t1 operator" << endl;
if(t2 == t1)
{
cout << "t2 and t1 are equal" << endl;
}
else
{
cout << "t2 and t1 are not equal" << endl;
}

cout << "Deleting 32 from t2" << endl;
t2.Delete(32);
t2.Traversal();
cout << "Checking t2 == t1 operator after deleting 32 from t2" << endl;
if(t2 == t1)
{
cout << "t2 and t1 are equal" << endl;
}
else
{
cout << "t2 and t1 are not equal" << endl;
}

return 0;
}

```

Enjoy :bananaman: :gunsmilie:

### 1 Comments On This Entry

Page 1 of 1

#### Munawwar

06 July 2012 - 11:57 PM
A small nitpicking: A binary tree and a BTree are two different data structures. BTrees are similar to BSTs (binary search trees <-- these are "sorted" binary trees), except that they are generalized to n number of children.
0
Page 1 of 1

There are no Trackbacks for this entry

S M T W T F S
12
3456789
10111213141516
17181920212223
2425262728 29 30
31