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
*/
Header file: BinaryTree.hpp
Driver File:
Enjoy :bananaman: :gunsmilie:
## 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
*/
Header file: BinaryTree.hpp
#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
~BST() { destruct(pHead);} //Destructor
void destruct(Node *); //Destructor Helper
bool operator== (const BST &); //Equality check operator overloading function.
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
void operator= (BST &); // "=" operator overloading
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:
Node *pHead; //Root Node
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::operator== (const BST &rhs)//Equality check operator overloading function.
{
return compare(pHead,rhs.pHead);
}
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
{
if(pHead == NULL)
return;
Node *temp;
temp = pHead;
parent = pHead;
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;
if(pHead == NULL)
{
pHead = temp;
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;
}
}
}
void BST::operator= (BST &rhs) // "=" operator overloading
{
pHead = copy(pHead,rhs.pHead);
}
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)
{
case 1: Pre(pHead); break;
case 2: In(pHead); break;
case 3: Post(pHead); break;
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.
Page 1 of 1
Trackbacks for this entry [ Trackback URL ]
Tags
My Blog Links
Recent Entries
-
A simple and working Binary tree implementation in C++on May 24 2012 01:25 AM
Recent Comments
Search My Blog
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)
Categories
|
|



1 Comments








|