#include <stdio.h>
#include <stdlib.h>
typedef struct BTree
{
int key;
BTree *p;
BTree *left;
BTree *right;
}TN,*TNP;
TNP createTree()
{
TNP t1=(TNP)malloc(sizeof(TN));
TNP t2=(TNP)malloc(sizeof(TN));
TNP t3=(TNP)malloc(sizeof(TN));
TNP t4=(TNP)malloc(sizeof(TN));
TNP t5=(TNP)malloc(sizeof(TN));
TNP t6=(TNP)malloc(sizeof(TN));
TNP t7=(TNP)malloc(sizeof(TN));
t1->key=15;
t2->key=6;
t3->key=18;
t4->key=3;
t5->key=7;
t6->key=17;
t7->key=20;
t1->p=NULL;
t1->left=t2;
t1->right=t3;
t2->p=t1;
t2->left=t4;
t2->right=t5;
t3->p=t1;
t3->left=t6;
t3->right=t7;
t4->p=t2;
t4->left=NULL;
t4->right=NULL;
t5->p=t2;
t5->left=NULL;
t5->right=NULL;
t6->p=t3;
t6->left=NULL;
t6->right=NULL;
t7->p=t3;
t7->left=NULL;
t7->right=NULL;
return t1;
}
TNP treeSearch(TNP root,int key)
{
TNP x=root;
while(x && x->key != key)
{
if(x->key>key)
x=x->left;
else
x=x->right;
}
return x;
}
TNP treeMaximum(TNP root)
{
TNP x=root;
while(x->right)
x=x->right;
return x;
}
TNP treeMinimum(TNP root)
{
TNP x=root;
while(x->left)
x=x->left;
return x;
}
TNP treeSuccessor(TNP x)
{
if(x->right)
{
return treeMinimum(x->right);
}
else
{
TNP xp=x->p;
while(xp && xp->left != x)
{
x=xp;
xp=x->p;
}
return xp;
}
}
TNP treePredeccessor(TNP x)
{
if(x->left)
{
return treeMaximum(x->left);
}
else
{
TNP xp=x->p;
while(xp && xp->right != x)
{
x=xp;
xp=x->p;
}
return xp;
}
}
TNP treeInsert(TNP *root,int k)
{
TNP t=(TNP)malloc(sizeof(TN));
t->key=k;
t->left=t->right=NULL;
TNP y=NULL,x=*root;
while(x)
{
y=x;
if(x->key<k)
x=x->right;
else
x=x->left;
}
t->p=y;
if(y==NULL)
*root=t;
else
{
if(y->key<k)
y->right=t;
else
y->left=t;
}
return t;
}
void transplant(TNP *root,TNP u,TNP v)
{
if(u&&v)
v->p=u->p;
if(u)
{
if(u->p==NULL)
{
*root=v;
}
else
{
if(u==u->p->left)
u->p->left=v;
else
u->p->right=v;
}
}
}
void treeDelete(TNP *root,TNP t)
{
if(t->left==NULL)
transplant(root,t,t->right);
else if(t->right==NULL)
transplant(root,t,t->left);
else
{
TNP y = treeSuccessor(t);
if(y!=t->right)
{
transplant(root,y,y->right);
y->right=t->right;
t->right->p=y;
}
transplant(root,t,y);
y->left=t->left;
t->left->p=y;
}
}
void inOrderTrav(TNP root)
{
if(!root)
return;
TNP x=root;
inOrderTrav(x->left);
printf("%d ",x->key);
inOrderTrav(x->right);
}
void main()
{
TNP root=createTree();
TNP max=treeMaximum(root);
if(max)
printf("Max node is %d\n",max->key);
TNP min=treeMinimum(root);
if(min)
printf("Min node is %d\n",min->key);
TNP t=treeSearch(root,7);
if(t && t->p)
printf("Parent of %d is %d\n",t->key,t->p->key);
TNP ts=treeSuccessor(t);
if(t && ts)
printf("Successor of %d is %d\n",t->key,ts->key);
TNP tp=treePredeccessor(t);
if(t && tp)
printf("Predeccessor of %d is %d\n",t->key,tp->key);
inOrderTrav(root);
printf("\n");
TNP ins = treeInsert(&root,16);
inOrderTrav(root);
printf("\n");
printf("Parent of %d is %d\n",ins->key,ins->p->key);
treeDelete(&root,ins);
inOrderTrav(root);
printf("\n");
treeDelete(&root,t);
inOrderTrav(root);
printf("\n");
getchar();
}
