Binary Tree Traversals MC9217 DATA STRUCTURES LAB Anna University lab manual download - Computer Programming

Latest

C C++ Java Python Perl Programs Examples with Output -useful for Schools & College Students

Saturday, January 29, 2011

Binary Tree Traversals MC9217 DATA STRUCTURES LAB Anna University lab manual download

Binary Tree Traversals MC9217 DATA STRUCTURES LAB Anna University lab manual download


Aim : To write a program to Create a binary search tree and do the following traversals
      (i)In-order   (ii) Pre order    (iii) Post order

Algorithm :

  1. Start
  2. Read the values of ch
  3. If ch=1 then it traverse through Inorder
      Inorder(T-left)
      Print(T->data)
      Inorder(T->right)
  1. if ch=2 then it traverse through
      Postorder         Postorder(T->left)
                              Postorder(T->right)
                              Preorder(T->right)
  1. if ch=2 then it traverse through
      Post order        postorder(T->left)
                              Postorder(T->right)
                              Print(T->data)
  1. Print the element
  2. Stop the process.

Logical Description       
The tree structures can be traversed in many different ways. Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed define the traversal type. These steps (in no particular order) are: performing an action on the current node (referred to as "visiting" the node), traversing to the left child node, and traversing to the right child node. Thus the process is most easily described through recursion.
To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:
  1. Visit the node.
  2. Traverse the left subtree.
  3. Traverse the right subtree.
To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node, starting with the root node:
  1. Traverse the left subtree.
  2. Visit the node.
  3. Traverse the right subtree.
To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node, starting with the root node:
  1. Traverse the left subtree.
  2. Traverse the right subtree.
  3. Visit the node.
Program Code
# include<stdio.h>
# include <conio.h>
# include <malloc.h>

struct node
{
            struct node *left;
            int data;
            struct node *right;
};

void main()
{
            void insert(struct node **,int);
            void inorder(struct node *);
            void postorder(struct node *);
            void preorder(struct node *);
            struct node *ptr;
            int will,i,num;
            ptr = NULL;
            ptr->data=NULL;
            clrscr();
            printf("Tree Traversal\n");
            printf("\nEnter the number of terms to add ");
            scanf("%d",&will);
            for(i=0;i<will;i++)
            {
                        printf("\nEnter the item");
                        scanf("%d",&num);
                        insert(&ptr,num);
            }

            getch();
            printf("\nINORDER TRAVERSAL");
            inorder(ptr);
            getch();
            printf("\nPREORDER TRAVERSAL");
            preorder(ptr);
            getch();
            printf("\nPOSTORDER TRAVERSAL");
            postorder(ptr);
            getch();
}
void insert(struct node  **p,int num)
{
            if((*p)==NULL)
            {
                        (*p)=malloc(sizeof(struct node));
                        (*p)->left = NULL;
                        (*p)->right = NULL;
                        (*p)->data = num;
                        return;
            }
            else
            {
                        if(num==(*p)->data)
                        {
                                    printf("\nREPEATED ENTRY ERROR VALUE REJECTED");
                                    return;
                        }
                        if(num<(*p)->data)
                        {
                                    insert(&((*p)->left),num);
                        }
                        else
                        {
                                    insert(&((*p)->right),num);
                        }
            }
            return;
}

void inorder(struct node *p)
{
            if(p!=NULL)
            {
                        inorder(p->left);
                        printf(" %d ",p->data);
                        inorder(p->right);
            }
            else
                        return;
}
void preorder(struct node *p)
{
            if(p!=NULL)
            {
                        printf(" %d ",p->data);
                        preorder(p->left);
                        preorder(p->right);
            }
            else
                        return;
}
void postorder(struct node *p)
{
            if(p!=NULL)
            {
                        postorder(p->left);
                        postorder(p->right);
                        printf(" %d ",p->data);
            }
            else
                        return;
}

No comments:

Post a Comment