Tuesday, February 26, 2008

Binary Tree in C++

this is my first ever tree program! ehehe...

(its just too bad that i dont have time to edit the spacing using html)

//btree.cpp

#include < iostream >

using namespace std;

template < class T >
class BTNode
{
private:
T key;
public:
BTNode *left;
BTNode *right;
BTNode *parent;
T getkey(){return key;}
BTNode(){left = NULL; right = NULL; }
BTNode(T k) {key = k;}
void w_key(T d){key = d;}
};


template < class T >
class BTree
{
public:
BTNode *root;
void insert(const T k);
void Display();
void print(BTNode *p);
void remove(T d);
BTree(){root = NULL;}
BTNode & find(T d)
{
BTNode *p = root;
while (p != NULL)
{ if (d == p->getkey())
return *p;
else if (d > p->getkey())
{
if (p->right != NULL)
{ p = p->right;
if(d==p->getkey())
return *p;
}
else
break;
}
else
{
if (p->left != NULL)
{ p = p->left;
if(d==p->getkey())
return *p;
}
else
break;
}
}
return *p;
}
};


template
void BTree :: Display()
{
print(root);
cout << endl;
}


template
void BTree::remove(T d)
{
BTNode * tmp = &find(d);
BTNode *ndel = tmp;

if(tmp->left==NULL && tmp->right==NULL)
{
if(tmp->parent->getkey() > tmp->getkey())
tmp->parent->left = NULL;
else
tmp->parent->right = NULL;
delete tmp;
Display();
}

else if(tmp->right==NULL)
{ if(tmp->getkey() == root->getkey())
{ root = tmp->left;
tmp->left->parent = NULL;
}
else if(tmp->parent->getkey() > tmp->getkey())
{ tmp->parent->left = tmp->left;
tmp->left = NULL;
}
else
{ tmp->parent->right = tmp->left;
tmp->left = NULL;
}
delete tmp;
Display();
}

else if(tmp->left==NULL)
{ if(tmp->getkey() == root->getkey())
{ root = tmp->right;
tmp->right->parent = NULL;
}
else if(tmp->parent->getkey() > tmp->getkey())
{ tmp->parent->left = tmp->right;
tmp->right = NULL;
}
else
{ tmp->parent->right = tmp->right;
tmp->right = NULL;
}
delete tmp;
Display();
}

else
{ if(tmp->getkey() == root->getkey())
{ tmp = tmp->left;
while(tmp->right != NULL)
tmp = tmp->right;
tmp->right = ndel->right;
root = ndel->left;
ndel->left->parent = NULL;
delete ndel;
}

else
{ tmp = tmp->left;
while(tmp->right != NULL)
tmp = tmp->right;

if (tmp->parent->left == tmp)
tmp->parent->left = NULL;
else
tmp->parent->right = NULL;
ndel->w_key(tmp->getkey());
delete tmp;
}
Display();
}

}





template
void BTree :: print(BTNode *p)
{
if (p != NULL)
{
print(p-> left);
cout << p-> getkey()<< " ";
print(p-> right);
}
}


template
void BTree :: insert(const T k)
{
BTNode *p = root;
BTNode *prev = NULL, *tmp;
while (p != NULL)
{
prev = p;
if (k > p->getkey())
{
if (p->right != NULL)
p = p->right;
else
break;
}
else
{
if (p->left != NULL)
p = p->left;
else
break;
}

}

if (root == NULL)
{
root = new BTNode(k);
root->parent = NULL;

}
else if (k > p->getkey()) {
prev->right = new BTNode(k);
prev->right->parent = prev;}
else {
prev->left = new BTNode(k);
prev->left->parent = prev; }
}


int main()
{
BTree mine;
int a, maxi, x=0, b;
maxi = 5;
while (x < maxi)
{
cout<<"Enter a number: ";
cin>>a;
mine.insert(a);
mine.Display();
x++;
}

cout<<"\nEnter the key that you would like to delete: ";
cin>>b;
mine.remove(b);


return 0;
}