The Recursively Traversal of Binary Tree
1. PRE-ORDERS TRAVERSAL
RECURSIVELY
To traverse a non-empty binary
tree in pre order following steps one to be processed
1. Visit the root node
2. Traverse the left sub-tree in
preorder
3. Traverse the right sub-tree in
preorder
That is, in preorder
traversal, the root node is visited (or processed) first, before traveling
through left and right sub trees recursively. It can be implement in C/C++
func-tion as below :
void preorder (Node * Root)
{
If (Root != NULL)
{
printf
(“%d\n”,Root → Info);
preorder(Root
→ L
child);
preorder(Root
→ R
child);
}
}
Fig.
The preorder traversal of a
binary tree in Fig. is
A, B, D, E, H, I, C, F, G, J.
2. IN ORDER TRAVERSAL
RECURSIVELY
The in-order traversal of a
non-empty binary tree is defined as follows :
1. Traverse the left sub tree in
order
2. Visit the root node
3. Traverse the right sub tree in
order
In order traversal, the
left sub-tree is traversed recursively, before visiting the root. After
visiting the root the right sub-tree is traversed recursively, in order
fashion. The procedure for an in-order traversal is given below :
void inorder (NODE *Root)
{
If (Root != NULL)
{
inorder(Root
→ L
child);
printf
(“%d\n”,Root → info);
inorder(Root
→ R
child);
}
}
The in-order traversal of a
binary tree in Fig. is
D, B, H, E, I, A, F, C, J, G.
3. POST ORDER TRAVERSAL
RECURSIVELY
The post-order traversal of a
non-empty binary tree can be defined as :
1. Traverse the left sub tree in
post order
2. Traverse the right sub tree in
post order
3. Visit the root node
In post-order traversal,
the left and right sub-tree (s) are recursively processed before visiting the
root.
void postorder (NODE *Root)
{
If (Root != NULL)
{
postorder(Root
→ Lchild);
postorder(Root
→ Rchild);
printf (“%d\n”,Root à info);
}
}
The post order traversal of a
binary tree in Fig. is
D, H, I, E, B, F, J, G, C, A
//PROGRAM TO IMPLEMENT THE INSERTION AND DELETION IN //B TREE CODED AND COMPILED USING TURBO C
#include<stdlib.h>
#include<malloc.h>
#include<conio.h>
#include<stdio.h>
#define M 5
//Structure is defined
struct node{
int n; /* n < M No. of keys in
node will always less than order of B tree */ int keys[M–1]; /*array of keys*/
struct node *p[M]; /* (n+1
pointers will be in use) */ }*root=NULL;
typedef struct node *NODE;
enum Key Status {
Duplicate,Search Failure,Success,InsertIt,Less Keys };
//Function declrations
void insert(int key);
void display(NODE root,int);
void search(int x);
enum KeyStatus ins(NODE r, int x,
int* y, NODE * u); int searchPos(int x,int *key_arr, int n); enum KeyStatus
del(NODE r, int x);
void main()
{
int key;
int choice;
while(1)
{
clrscr();//Clear the screen
//Menu options
printf (“\n1.Insert\n”);
printf (“2.Delete\n”);
printf (“3.Search\n”);
printf (“4.Display\n”);
printf (“5.Quit\n”);
printf (“\nEnter your choice :
”);
scanf (“%d”,&choice);
switch(choice)
{
case 1:
printf (“\nEnter the key : ”);
scanf (“%d”,&key);
insert(key);
break;
case 2:
printf (“\nEnter the key : ”);
scanf (“%d”,&key);
DelNode(key);
break;
case 3:
printf (“\nEnter the key : ”);
scanf (“%d”,&key);
search(key);
getch();
break;
case 4:
printf (“\nBtree is :\n”);
display(root,0);
getch();
break;
case 5:
exit(1);
default:
printf (“\nWrong choice\n”);
getch();
break;
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
void insert(int key)
{
NODE newnode;
int upKey;
enum KeyStatus value;
value = ins(root, key,
&upKey, &newnode);
//Cheking for duplicate keys
if (value == Duplicate)
{
printf(“\nKey already
available\n”);
getch();
}
if (value == InsertIt)
{
NODE uproot = root;
//Allocating memory
root=(NODE)malloc(sizeof(struct
node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}/*End of if */
}/*End of insert()*/
enum KeyStatus ins(NODE ptr, int
key, int *upKey,NODE *newnode)
{
NODE newPtr,lastPtr;
int pos, i, n,splitPos;
enum KeyStatus value;
if (ptr == NULL)
{
*newnode = NULL;
*upKey = key;
return InsertIt;
}
n = ptr->n;
pos = searchPos(key,
ptr->keys, n);
if (pos < n && key ==
ptr->keys[pos])
return Duplicate;
value = ins(ptr->p[pos], key,
&newKey, &newPtr);
if (value != InsertIt)
return value;
/*If keys in node is less than
M–1 where M is order of B tree*/
if (n < M – 1)
{
pos = searchPos(newKey,
ptr->keys, n);
/*Shifting the key and pointer
right for inserting the new key*/
for (i=n; i>pos; i--)
{
ptr->keys[i] =
ptr->keys[i–1];
ptr->p[i+1] = ptr->p[i];
}
/*Key is inserted at exact
location*/
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
++ptr->n; /*incrementing the
number of keys in node*/
return Success;
}/*End of if */
/*If keys in nodes are maximum
and position of node to be inserted is last*/
if (pos == M – 1)
{
lastKey = newKey;
lastPtr = newPtr;
}
else /*If keys in node are
maximum and position of node to be inserted is not last*/
{
lastKey = ptr->keys[M–2];
lastPtr = ptr->p[M–1];
for (i=M–2; i>pos; i--)
ptr->keys[i] =
ptr->keys[i–1];
ptr->p[i+1] = ptr->p[i];
}
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
}
splitPos = (M – 1)/2;
(*upKey) =
ptr->keys[splitPos];
(*newnode)=(NODE)malloc(sizeof(struct
node));/*Right node after split*/
ptr->n = splitPos; /*No. of
keys for left splitted node*/
(*newnode)->n =
M–1-splitPos;/*No. of keys for right splitted node*/
for (i=0; i <
(*newnode)->n; i++)
{
(*newnode)->p[i] = ptr->p[i
+ splitPos + 1];
if(i < (*newnode)->n – 1)
(*newnode)->keys[i] =
ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lastKey;
}
(*newnode)->p[(*newnode)->n]
= lastPtr;
return InsertIt;
}/*End of ins()*/
void display(NODE ptr, int
blanks)
{
if (ptr)
{
int i;
for(i=1;i<=blanks;i++)
printf (“ ”);
for (i=0; i < ptr->n; i++)
printf (“%d ”,ptr->keys[i]);
printf (“\n”);
for (i=0; i <= ptr->n; i++)
display(ptr->p[i], blanks+10);
}/*End of if*/
}/*End of display()*/
void search(int key)
{
NODE ptr = root;
printf (“\nSearch path:\n”);
while (ptr)
{
n = ptr->n;
for (i=0; i < ptr->n; i++)
printf (“ %d”,ptr->keys[i]);
printf (“\n”);
pos = searchPos(key,
ptr->keys, n);
if (pos < n && key ==
ptr->keys[pos])
{
printf (“\nKey %d found in
position %d of last dispalyed node\n”,key,i); return;
}
ptr = ptr->p[pos];
}
printf (“\nKey %d is not
available\n”,key);
}/*End of search()*/
int searchPos(int key, int
*key_arr, int n)
{
int pos=0;
while (pos < n && key
> key_arr[pos])
pos++;
return pos;
}/*End of searchPos()*/
void DelNode(int key)
{
NODE uproot;
enum KeyStatus value;
value = del(root,key);
switch (value)
{
case SearchFailure:
printf(“\nKey %d is not
available\n”,key);
break;
case LessKeys:
uproot = root;
root = root->p[0];
free(uproot);
}/*End of switch*/
}/*End of delnode()*/
enum KeyStatus del(NODE ptr, int
key)
{
int pos, i, pivot, n ,min;
int *key_arr;
enum KeyStatus value;
NODE *p,lptr,rptr;
if (ptr == NULL)
return SearchFailure;
/*Assigns values of node*/
n=ptr->n;
key_arr = ptr->keys;
p = ptr->p;
min = (M – 1)/2;/*Minimum number
of keys*/
pos = searchPos(key, key_arr, n);
if (p[0] == NULL)
{
if (pos == n || key <
key_arr[pos])
return SearchFailure;
/*Shift keys and pointers left*/
for (i=pos+1; i < n; i++)
{
key_arr[i–1] = key_arr[i];
p[i] = p[i+1];
}
return --ptr->n >=
(ptr==root ? 1 : min) ? Success : LessKeys; }
/*End of if */
if (pos < n && key ==
key_arr[pos])
{
struct node *qp = p[pos], *qp1;
int nkey;
while(1)
{
nkey = qp->n;
qp1 = qp->p[nkey];
if (qp1 == NULL)
qp = qp1;
}/*End of while*/
key_arr[pos] =
qp->keys[nkey–1];
qp->keys[nkey – 1] = key;
}/*End of if */
value = del(p[pos], key);
if (value != LessKeys)
return value;
if (pos > 0 &&
p[pos–1]->n > min)
{
pivot = pos – 1; /*pivot for left
and right node*/
lptr = p[pivot];
rptr = p[pos];
/*Assigns values for right node*/
rptr->p[rptr->n + 1] =
rptr->p[rptr->n];
for (i=rptr->n; i>0; i--)
{
rptr->keys[i] =
rptr->keys[i–1];
rptr->p[i] = rptr->p[i–1];
}
rptr->n++;
rptr->keys[0] =
key_arr[pivot];
rptr->p[0] =
lptr->p[lptr->n];
key_arr[pivot] =
lptr->keys[--lptr->n];
return Success;
}/*End of if */
if (pos<n &&
p[pos+1]->n > min)
{
pivot = pos; /*pivot for left and
right node*/
lptr = p[pivot];
rptr = p[pivot+1];
/*Assigns values for left node*/
lptr->keys[lptr->n] =
key_arr[pivot];
lptr->p[lptr->n + 1] =
rptr->p[0];
key_arr[pivot] =
rptr->keys[0];
lptr->n++;
rptr->n--;
for (i=0; i < rptr->n; i++)
{
rptr->keys[i] =
rptr->keys[i+1];
}/*End of for*/
rptr->p[rptr->n] =
rptr->p[rptr->n + 1];
return Success;
}/*End of if */
if(pos == n)
pivot = pos–1;
else
pivot = pos;
lptr = p[pivot];
rptr = p[pivot+1];
/*merge right node with left
node*/
lptr->keys[lptr->n] =
key_arr[pivot];
lptr->p[lptr->n + 1] =
rptr->p[0];
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i]
= rptr->keys[i];
lptr->p[lptr->n + 2 + i] =
rptr->p[i+1];
}
lptr->n = lptr->n +
rptr->n +1;
free(rptr); /*Remove right node*/
for (i=pos+1; i < n; i++)
{
key_arr[i–1] = key_arr[i];
p[i] = p[i+1];
}
return --ptr->n >=
(ptr == root ? 1 : min) ? Success : LessKeys; }/*End of del()*/
ü ======================
ü Like and Share with
friends
ü =====================
