BST.C

#include<stdio.h>
#include<stdlib.h>

structNode
{
structNode*lchild;
intdata;
structNode*rchild;
} *root=NULL;

voidInsert(intkey)
{
structNode*t=root;
structNode*r, *p;

if (root==NULL)
 {
p= (structNode*)malloc(sizeof(structNode));
p->data=key;
p->lchild=p->rchild=NULL;
root=p;
return;
 }
while (t!=NULL)
 {
r=t;
if (key<t->data)
t=t->lchild;
elseif (key>t->data)
t=t->rchild;
else
return;
 }
p= (structNode*)malloc(sizeof(structNode));
p->data=key;
p->lchild=p->rchild=NULL;

if (key<r->data)
r->lchild=p;
else
r->rchild=p;
}

voidInorder(structNode*p)
{
if (p)
 {
Inorder(p->lchild);
printf("%d ", p->data);
Inorder(p->rchild);
 }
}

structNode*Search(intkey)
{
structNode*t=root;

while (t!=NULL)
 {
if (key==t->data)
returnt;
elseif (key<t->data)
t=t->lchild;
else
t=t->rchild;
 }
returnNULL;
}

structNode*RInsert(structNode*p, intkey)
{
structNode*t=NULL;
if (p==NULL)
 {
t= (structNode*)malloc(sizeof(structNode));
t->data=key;
t->lchild=t->rchild=NULL;
returnt;
 }
if (key<p->data)
p->lchild=RInsert(p->lchild, key);
elseif (key>p->data)
p->rchild=RInsert(p->rchild, key);
returnp;
}

intHeight(structNode*p)
{
intx, y;
if (p==NULL)
return0;
x=Height(p->lchild);
y=Height(p->rchild);
returnx>y ? x+1 : y+1;
}

structNode*InPre(structNode*p)
{
while (p&&p->rchild!=NULL)
p=p->rchild;
returnp;
}

structNode*InSucc(structNode*p)
{
while (p&&p->lchild!=NULL)
p=p->lchild;
returnp;
}

structNode*Delete(structNode*p, intkey)
{
structNode*q=NULL;
if (p==NULL)
returnNULL;
if (p->lchild==NULL&&p->rchild==NULL)
 {
if (p==root)
root=NULL;
free(p);
returnNULL;
 }

if (key<p->data)
p->lchild=Delete(p->lchild, key);
elseif (key>p->data)
p->rchild=Delete(p->rchild, key);
else
 {
if (Height(p->lchild) >Height(p->rchild))
 {
q=InPre(p->lchild);
p->data=q->data;
p->lchild=Delete(p->lchild, q->data);
 }
else
 {
q=InSucc(p->rchild);
p->data=q->data;
p->rchild=Delete(p->rchild, q->data);
 }
 }
returnp;
}

intmain()
{
structNode*temp;

root=RInsert(root, 10);
RInsert(root, 10);
RInsert(root, 40);
RInsert(root, 20);
RInsert(root, 30);
RInsert(root, 25);
RInsert(root, 35);
RInsert(root, 55);

Delete(root, 30);

Inorder(root);
printf("\n");

temp=Search(20);
if (temp!=NULL)
printf("Element %d is found\n", temp->data);
else
 {
printf("Element is not found\n");
 }

return0;
}