1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

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,292
    Likes Received:
    365
    Trophy Points:
    83
Thread Status:
Not open for further replies.

Share This Page