Binary search tree traversal-Inorder,preorder,postorder.

Discussion in 'C' started by gordon_imran, Oct 25, 2007.

Thread Status:
Not open for further replies.
  1. gordon_imran

    gordon_imran New Member

    Joined:
    Oct 15, 2007
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    /*This program takes the elements from the user in random order & then arranges it in
    form of Binary Search Tree.It then asks user for traversal*/

    Code:
    
    #include<stdio.h>                          // including headerfiles
    #include<conio.h>
    #include<stdlib.h>
    struct tree                                        //creating structure
    { 
    int data;                         //data field of node
    struct tree *lchild,*rchild;               //left child & right child of node
    };
    struct tree *insert(struct tree *p,int n);     //function for insertion
    void inorder(struct tree *p);                      //function for inorder traversal
    void preorder(struct tree *p);                   // function for preorder traversal
    void postorder(struct tree *p);                  // function for postorder traversal
    void main()                      //main function
    { 
    int x,y,i;                                    
    struct tree *root;
    clrscr();
    root=NULL;
    printf("Enter the no. of nodes in the tree\n");
    scanf("%d",&x);
    while(x-->0)
    {
    printf("Enter the data part of the node\n");
    scanf("%d",&y);
    root=traverse(root,y);
    }
    clrscr();
    printf("\t\tEnter the traversal u want\n");
    printf("1.Inorder.\n2.Preorder.\n3.Postorder.\n");
    scanf("%d",&i);
    switch(i)
    {
    case 1:
    {
    printf("The inorder traversal is \n");
    inorder(root);                        //function calling
    }
    break;
    case 2:
    {
    printf("The preorder traversal is\n");
    preorder(root);                           //function calling
    }
    break;
    case 3:
    {
    printf("The postorder traversal is\n");
    postorder(root);                            // function calling
    }
    break;
    }
    getch();
    }
    
    //function definition for insertion
    struct tree *traverse(struct tree *p,int n)               
    {
    static struct tree *temp1,*temp2;
    if(p==NULL)
    {
    p=(struct tree *)malloc(sizeof(struct tree));
    p->data=n;
    p->lchild=p->rchild=NULL;
    }
    else
    {
    temp1=p;
    while(temp1!=NULL)
    {
    temp2=temp1;
    if(n<temp1->data)
    temp1=temp1->lchild;
    else
    temp1=temp1->rchild;
    }
    if(temp2->data>n)
    {
    temp2->lchild=(struct tree *)malloc(sizeof(struct tree));
    temp2=temp2->lchild;
    temp2->data=n;
    temp2->lchild=temp2->rchild=NULL;
    }
    else
    {
    temp2->rchild=(struct tree *)malloc(sizeof(struct tree));
    temp2=temp2->rchild;
    temp2->data=n;
    temp2->lchild=temp2->rchild=NULL;
    }
    }
    return p;
    }
    //function definition for inorder traversal
    
    void inorder(struct tree *p)
    {
    if(p!=NULL)
    {
    inorder(p->lchild);
    printf("%d ",p->data);
    inorder(p->rchild);
    }
    }
    
    //function definition for preorder traversal
    void preorder(struct tree *p)
    {
    if(p!=NULL)
    {
    printf("%d ",p->data);
    preorder(p->lchild);
    preorder(p->rchild);
    }
    }
    
    //function definition for postorder traversal
    void postorder(struct tree *p)
    {
    if(p!=NULL)
    {
    postorder(p->lchild);
    postorder(p->rchild);
    printf("%d ",p->data);
    }
    }
     
    Last edited by a moderator: Oct 25, 2007
  2. gordon_imran

    gordon_imran New Member

    Joined:
    Oct 15, 2007
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    sorry for the inconvinence...
    this program has a small bug...
    the program in the thread after this works...
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
Thread Status:
Not open for further replies.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice