/*
* This program contains an efficient implementation of
* binary search tree deletion using search and delete
* functions using pointer to pointer features of C.
* This is effiecient than given in most(not all) books.
* compile with gcc (or your favourite compilers)
* The main() is irrelevant.It was used by me to do
* functionality test
* observe the similarity between the ldr() and lrd() routines
* easy to remember
* you only need non recurisve versions if you are probably hacking kernel
* S.Kartikeyan CSE BTech GMRIT(Rajam),CSE MTech (IITMadras)
* Use It As you like
*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define NULLNODE ((node*)NULL)
/* change to your needs */
#define STACKMAX 100
/* node of the binary tree */
struct Node
{
int data;
struct Node * left;
struct Node * right;
};
typedef struct Node node;
/* binary tree insertion */
void insert(node ** p,int data)
{
if(*p==(node*)0)
{
*p = (node*)malloc(sizeof(node));
p[0]->data = data;
p[0]->left = NULLNODE;
p[0]->right= NULLNODE;
}
else if(p[0]->data>data)
{
insert(&(p[0]->left),data);
}
else
{
insert(&(p[0]->right),data);
}
}
/* recursive ldr traversal routine */
void r_ldr(node* p)
{
if(p)
{
r_ldr(p->left);
printf("%d ",p->data);
r_ldr(p->right);
}
}
/* non recursive dlr traversal */
void dlr(node*root)
{
if(!root){ printf("Empty Tree\n");return;}
struct StackType{node*p;short flag;};
struct StackType stack[STACKMAX];
int top;
stack[top=0].p = root;
stack[top].flag= 0;
while(top>=0)
{
struct StackType p = stack[top--];
if(p.p)
{
stack[++top].p = p.p->right;
stack[top].flag= 0;
stack[++top].p = p.p->left;
stack[top].flag= 0;
stack[++top].p = p.p;
stack[top].flag=0;
stack[++top].p = NULLNODE;
stack[top].flag=1;
}
else
{
if(p.flag)
printf("%d ",stack[top--].p->data);
}
}
}
/* non recursive ldr routine in another way*/
void ldr(node *root)
{
if(!root) {printf("Empty Tree\n");return;}
struct StackType{
node * p;
short flag;
}stack[STACKMAX];
struct StackType p;
int top;
stack[top=0].p = root;
stack[top].flag = 0;
while(top>=0)
{
p = stack[top--];
if(p.p)
{
stack[++top].p = p.p->right;
stack[top].flag = 0;
stack[++top].p = p.p;
stack[top].flag = 0;
stack[++top].p = NULLNODE;
stack[top].flag = 1;
stack[++top].p = p.p->left;
stack[top].flag = 0;
}
else
{
if(p.flag)
printf("%d ",stack[top--].p->data);
}
}
}
/* recursive dlr pre-order traversal */
void r_dlr(node *p)
{
if(p)
{
printf("%d ",p->data);
r_dlr(p->left);
r_dlr(p->right);
}
}
/* non recursive ldr routine */
void ldr2(node *p)
{
if(!p) {printf("Empty Tree\n");return ;}
node * stack[STACKMAX];
int top;
stack[top=0]=p;
while(top>=0)
{
while(p){stack[top++]=p;p=p->left;}
if(!top--) return;
p = stack[top];
printf("%d ",p->data);
p = stack[top]->right;
}
}
/* yet another dlr implementation */
void dlr2(node*p)
{
if(!p){ printf("Empty Tree\n");return; }
node * stack[STACKMAX];
int top;
stack[top=0]=p;
while(top>=0)
{
p = stack[top--];
if(p)
{
printf("%d ",p->data);
stack[++top] = p->right;
stack[++top] = p->left;
}
}
}
/* recursive post order traversal */
void r_lrd(node *p)
{
if(p)
{
r_lrd(p->left);
r_lrd(p->right);
printf("%d ",p->data);
}
}
/* non recursive post order traversal */
void lrd2(node *root)
{
if(!root){printf("Empty Tree\n");return;}
struct StackType{
node * p;
short flag;
}stack[STACKMAX];
int top;
stack[top=0].p=root;
stack[top].flag=0;
struct StackType p;
while(top>=0)
{
p = stack[top--];
if(p.p)
{
stack[++top] = p;
stack[top].flag = 0;
//marker node hence flag = 0
stack[++top].p = NULLNODE;
stack[top].flag = 1;
stack[++top].p = p.p->right;
stack[top].flag=0;
stack[++top].p = p.p->left;
stack[top].flag=0;
}
else
{
//if print node pop after printing
if(p.flag)
printf("%d ",stack[top--].p->data);
}
}
}
/* non recursive post order traversal */
void lrd(node *p)
{
if(!p){printf("Empty Tree\n");return ;}
node * stack[STACKMAX];
int top=0;
stack[top] = p;
while(top>=0)
{
while(p){stack[++top]=p;p=p->left;}
if(!top) return;
if(stack[top])
{
p = stack[top]->right;
stack[++top]=0;
}
else
{
top--;
printf("%d ",stack[top--]->data);
}
}
}
/* The best binary search tree deletion algorithm i Know */
/* The algorithm was after a fight */
node ** search(node**p,int key)
{
if(!p[0]) return (node**)0;
else if(p[0]->data==key) return p;
else if(p[0]->data>key) return search(&p[0]->left,key);
return search(&p[0]->right,key);
}
int deletenode(node **p,int key)
{
node ** found = search(p,key);
if(found[0]==NULL) return 0;
node * temp = found[0];
if(found[0]->left==NULL) found[0] = found[0]->right;
else if(found[0]->right==NULL) found[0] = found[0]->left;
else
{
node ** itr;
for(itr=&(found[0]->right);itr[0]->left;itr=&(itr[0]->left));
temp = itr[0];
found[0]->data = itr[0]->data;
itr[0] = itr[0]->right;
}
free(temp);
return 1;
}
/* used by me for functioanality test */
int main()
{
node * head1 = (node*)0;
printf("Bstree Program\n");
int d[] = {100,50,150,75,25,125,175};
int n=sizeof(d)/sizeof(d[0]);
int i;
for(i=0;i<n;i++)
{
insert(&head1,d[i]);
lrd(head1);printf("\n");
lrd2(head1);printf("\n");
r_lrd(head1);printf("\n");
ldr(head1);printf("\n");
ldr2(head1);printf("\n");
r_ldr(head1);printf("\n");
dlr(head1);printf("\n");
dlr2(head1);printf("\n");
r_dlr(head1);printf("\n");
}
for( i=0;i<n;i++)
{
if(deletenode(&head1,d[i]))
printf("After %d deletion\n",d[i]);
ldr(head1);printf("\n");
}
return 0;
}