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.

  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=insert(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 *insert(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);
    	}
    }
     

Share This Page