C Program to implement Binary Search Tree Traversal

C Program to implement Binary Search Tree Traversal

Preorder traversal sequence : F, B, A, D, C, E, G, I, H
   (root, left, right)
Inorder traversal sequence  : A, B, C, D, E, F, G, H, I
   (left, root, right)
Postorder traversal sequence: A, C, E, D, B, H, I, G, F
   (left, right, root)

Reference : http://en.wikipedia.org/wiki/Tree_traversal

---

Program :

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

typedef struct BST
{
    int data;
    struct BST *lchild,*rchild;
}node;

void insert(node *,node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *,int,node **);

void main()
{
 int choice;
 char ans='N';
 int key;
 node *new_node,*root,*tmp,*parent;
 node *get_node();
 root=NULL;
 clrscr();

 printf("nProgram For Binary Search Tree ");
 do
 {
   printf("n1.Create");
   printf("n2.Search");
   printf("n3.Recursive Traversals");
   printf("n4.Exit");
   printf("nEnter your choice :");
   scanf("%d",&choice);

   switch(choice)
   {
    case 1:
           do
             {
             new_node=get_node();

             printf("nEnter The Element ");
             scanf("%d",&new_node->data);

             if(root==NULL)   /* Tree is not Created */
                 root=new_node;
             else
                 insert(root,new_node);

             printf("nWant To enter More Elements?(y/n)");
             ans=getch();

             }while(ans=='y');

             break;

     case 2:
             printf("nEnter Element to be searched :");
             scanf("%d",&key);

             tmp = search(root,key,&parent);

             printf("nParent of node %d is %d",
                              tmp->data,parent->data);
             break;

    case 3:

            if(root==NULL)
                printf("Tree Is Not Created");
            else
               {
               printf("nThe Inorder display : ");
               inorder(root);
               printf("nThe Preorder display : ");
               preorder(root);
               printf("nThe Postorder display : ");
               postorder(root);
               }

            break;
    }
 }while(choice!=4);
}
/*
  Get new Node 
*/
node *get_node()
 {
 node *temp;
 temp=(node *)malloc(sizeof(node));
 temp->lchild=NULL;
 temp->rchild=NULL;
 return temp;
 }
/*
  This function is for creating a binary search tree 
*/
void insert(node *root,node *new_node)
{
  if(new_node->data < root->data)
     {
     if(root->lchild==NULL)
         root->lchild = new_node;
     else
         insert(root->lchild,new_node);
     }

  if(new_node->data > root->data)
     {
     if(root->rchild==NULL)
         root->rchild=new_node;
     else
         insert(root->rchild,new_node);
     }
}
/*
This function is for searching the node from
      binary Search Tree
*/
node *search(node *root,int key,node **parent)
{
 node *temp;
 temp=root;
    while(temp!=NULL)
    {
      if(temp->data==key)
         {
         printf("n The %d Element is Present",temp->data);
         return temp;
         }
      *parent=temp;

      if(temp->data>key)
         temp=temp->lchild;
      else
         temp=temp->rchild;
    }
 return NULL;
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp)
{
   if(temp!=NULL)
    {
    inorder(temp->lchild);
    printf("%d",temp->data);
    inorder(temp->rchild);
    }
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp)
{
 if(temp!=NULL)
    {
    printf("%d",temp->data);
    preorder(temp->lchild);
    preorder(temp->rchild);
    }
}

/*
This function displays the tree in postorder fashion
*/
void postorder(node *temp)
{
 if(temp!=NULL)
    {
    postorder(temp->lchild);
    postorder(temp->rchild);
    printf("%d",temp->data);
    }
}

[468x15]

---

Output :

Program For Binary Search Tree
1.Create
2.Search
3.Recursive Traversals
4.Exit
Enter your choice :1

Enter The Element 5

Do u Want To enter More Elements?(y/n)
Enter The Element 12

Do u Want To enter More Elements?(y/n)
Enter The Element 6

Do u Want To enter More Elements?(y/n)
Enter The Element 3

Do u Want To enter More Elements?(y/n)
1.Create
2.Search
3.Recursive Traversals
4.Exit
Enter your choice :3

The Inorder   display  :   3  5  6  12
The Preorder  display  :   5  3  12  6
The Postorder display  :   3  6  12  5

1.Create
2.Search
3.Recursive Traversals
4.Exit
Enter your choice :2

Enter Element to be searched :3

The 20 Element is Present
Parent of node 3 is 5

Explanation of Program :

Creating Tree :

case 1:
           do
             {
             new_node=get_node();

             printf("nEnter The Element ");
             scanf("%d",&new_node->data);

             if(root==NULL)   /* Tree is not Created */
                 root=new_node;
             else
                 insert(root,new_node);

             printf("nWant To enter More Elements?(y/n)");
             ans=getch();

             }while(ans=='y');

             break;

Explanation :

• get_node() function will allocate memory dynamically and allocate one node.
• if below condition is satisfied then we can say that we are going to create first node of the tree. (i.e Tree is empty and this created node is very first node)

if(root == NULL)

• If condition does not satisfied then we can say that we have already node in a tree. (i.e this node which we have created is not a first node)

Display Tree

To display tree we have 3 traversal Techniques -

1. In-Order Traversal
2. Pre-Order Traversal
3. Post-Order Traversal

Algorithm for Preorder Traversal of Binary Search Tree :

preorder(node)
  {
  if node = null
   then
     return
  else
     print Node Data
     Go to Left Child of node
     Go to Right Child of node
  }

Similarly Post order and inorder traversal works.

Summary of Traversal of BST :

Traversal Type	Inorder	Preorder	Postorder
Short Cut	L V R	V L R	L R V

---

Thanks to-

c4learn.com