Program - Binary tree traversal

Program - Binary tree traversal

Preorder traversal of binary tree

preorder(node)

Step-1 : [do through step 3]

                if node ≠ NULL

                        output info[node]

Step-2  : call preorder(left_child[node])

Step-3  : call preorder(right_child[node])

Step-4 : exit

Inorder traversal of binary tree

inorder(node)

Step-1 : [do through step 4]

                if node ≠ NULL

Step-2 : call inorder(left_child[node])

Step-3  : Output info[node]

Step-4 : call inorder(right_child[node])

Step-5 : exit

Postorder traversal of binary tree

postorder(node)

Step-1 : [do through step 4]

                if node ≠ NULL

Step-2 : call postorder(left_child[node])

Step-3 : call postorder(right_child[node])

Step-4  : output info[node]

Step-5 : exit

Program

// Traversing  binary tree

// (preorder, inorder ,postorder

#include<stdio.h>

#include<conio.h>

struct tree

{

        char  info;

        struct tree *leftchild;

        struct tree *rightchild;

};

struct tree * create_tree(char*,int,int);

void output(struct tree*,int);

void preorder(struct tree *);

void inorder(struct tree *);

void postorder(struct tree *);

struct tree * create_tree(char *list,int low,int up)

{

        struct tree *node;

        int mid=(low+up)/2;

        node=(struct tree *)malloc(sizeof(struct tree));

        node->info=list[mid];

        if(low>=up)

        {

                node->leftchild=NULL;

                node->rightchild=NULL;

                return(node);

        }

        if(low<=mid-1)

                node->leftchild=create_tree(list,low,mid-1);

        else

                node->leftchild=NULL;

        if(mid+1<=up)

                node->rightchild=create_tree(list,mid+1,up);

        else

                node->rightchild=NULL;

        return(node);

}

void output(struct tree *t,int level)

{

        int i;

        if(t)

        {

                output(t->rightchild,level+1);

                printf("\n");

                for(i=0;i<level;i++)

                        printf(" ");

                printf("%c",t->info);

                output(t->leftchild,level+1);

        }

}

void preorder(struct tree *node)

{

        if(node)

        {

                printf("%c",node->info);

                preorder(node->leftchild);

                preorder(node->rightchild);

        }

}

void inorder(struct tree *node)

{

        if(node)

        {

                inorder(node->leftchild);

                printf("%c",node->info);

                inorder(node->rightchild);

        }

}

void postorder(struct tree *node)

{

        if(node)

        {

                postorder(node->leftchild);

                postorder(node->rightchild);

                printf("%c",node->info);

        }

}

void main()

{

        char list[100];

        int num=0;

        char info,ch;

        struct tree *t=(struct tree *)malloc(sizeof(struct tree));

        clrscr();

        t=NULL;

        printf("Input choice 'b' to break:");

        ch=getchar();

        fflush(stdin);

        while(ch!='b')

        {

                printf("Input information of the node:");

                scanf("%c",&info);

                list[num++]=info;

                fflush(stdin);

                printf("Input choice 'b' to break:");

                ch=getchar();

                fflush(stdin);

        }

        printf("\nNumber of elements in the list is %d",num);

        num--;

        t=create_tree(list,0,num);

        output(t,1);

        printf("\n\nPre-order Traversal: \n");

        preorder(t);

        printf("\n\nIn-order Traversal: \n");

        inorder(t);

        printf("\n\nPost-order Traversal: \n");

        postorder(t);

        getch();

}

Posted By : Ruchita Pandya