Subscribe to Indyarocks' Blog        RSS Feed
-----

A simple and working Binary tree implementation in C++

Icon 1 Comments
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
#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 Icon

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

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

April 2014

S M T W T F S
  12345
6789101112
1314151617 18 19
20212223242526
27282930   

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)

    Categories