All about programming in GNU/LINUX

Implementation of Binary Tree in C

ImageImageImageImage//Enter the direction of the node to be inserted
//The direction will be validated and then the node will be inserted
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node* NODE;
struct node
{
    int info;
    NODE llink;
    NODE rlink;
};
NODE insert_node(int item,NODE root)
{
    NODE temp;
    NODE cur;
    NODE prev;
    char direction[100];
    int i;
    temp=(NODE)malloc(sizeof(struct node));
    temp->info=item;
    temp->llink=temp->rlink=NULL;
    if(root==NULL)
     return temp;
    printf(“\nEnter DIRECTION(Must be combination of (l/r)): “);
    scanf(“%s”,direction);//A Potential Bufferoverflow Vulnerablity , Use fgets instead
    prev=NULL;
    cur=root;
    for(i=0;i<strlen(direction) && cur!=NULL;i++)
    {
        prev=cur;
        if(direction[i]==’l’|| direction[i]==’L’)
         cur=cur->llink;
        else if(direction[i]==’r’ || direction[i]==’R’)
         cur=cur->rlink;
        else
        {
            printf(“\n\n\n****Invalid Direction Input:Please enter either ‘L’ or ‘R’****\n\n\n “);
            return root;
        }
    }
        if(cur!=NULL || i!=strlen(direction))
        {
            if(cur!=NULL)
            {
                printf(“\n\n***Element already exists in the node, Entered path too short****”);
                return root;
            }
            else
            {
                printf(“\n\n**The entered Direction is too long***”);
                return root;
            }
        }
        if(direction[i-1]==’l’ || direction[i-1]==’L’)
            prev->llink=temp;
        else
            prev->rlink=temp;
        return root;

    }
    void inorder(NODE root)
    {
        if(root==NULL)
            return ;
        inorder(root->llink);
        printf(“%d\t”,root->info);
        inorder(root->rlink);

    }
    void postorder(NODE root)
    {
        if(root==NULL)
            return ;
        postorder(root->llink);
        postorder(root->rlink);
        printf(“%d\t”,root->info);
    }
    void preorder(NODE root)
    {
        if(root==NULL)
            return ;
        printf(“%d\t”,root->info);
        preorder(root->llink);
        preorder(root->rlink);
    }
    void display(NODE root,int height)
    {
        int i=1;
        if(root==NULL)
          return ;
        display(root->rlink,height+1);
        while(i<=height)
        {
            printf(“**”);
            i++;
        }
        printf(“%d\n”,root->info);
        display(root->llink,height+1);
    }

int main()
{
    NODE root=NULL;
    int element,choice;
    while(1)
    {
        printf(“\n\n\t1.INSERT NODE\n\t2.INORDER\n\t3.POSTODER\n\t4.PREORDER\n\t5.DISPLAY\n\t6.EXIT”);
        printf(“\nEnter your choice: “);
        scanf(“%d”,&choice);
        switch(choice)
        {
            case 1:printf(“\nEnter the element: “);
                   scanf(“%d”,&element);
                   root=insert_node(element,root);
                   break ;
            case 2:if(root==NULL)
                     printf(“\n\n\n\t\t****Tree Empty***\n\n\n”);
                   else
                   {
                       printf(“\nThe INORDER: “);
                       inorder(root);

                   }
                   break ;
            case 3:if(root==NULL)
                     printf(“\n\n\n\t\t****Tree Empty***\n\n\n”);
                   else
                   {
                       printf(“\nThe POSTORDER: “);
                       postorder(root);

                   }
                    break ;
            case 4:if(root==NULL)
                     printf(“\n\n\n\t\t****Tree Empty***\n\n\n”);
                   else
                   {
                       printf(“\nThe PREORDER: “);
                       preorder(root);

                   }
                    break ;
            case 5:if(root==NULL)
                          printf(“\n\n\n\t\t***Tree Empty****\n\n\n\t”);
                   else
                          display(root,1);
                    break ;
             default : exit(0);

        }
    }
}

Advertisements

One response

  1. great ver hard work. i am the student of softwear enggnrring ….

    January 27, 2013 at 3:56 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s