C - Programming Guide

#include<conio.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct BSTnode
{
     char *data;
     struct BSTnode *left,*right;
}BSTnode;
typedef struct Q
  {
    BSTnode *data[40];
    int R,F;
  }Q;
void init(Q *q)
 {
    q->R=q->F=-1;
 }
BSTnode * dequeue(Q *q)
 {
    BSTnode *p;
    p=q->data[q->F];
    if(q->R==q->F)
        init(q);
    else
        q->F=q->F+1;
    return(p);
 }

void  enqueue(Q *q, BSTnode *p)
  {
    if(q->R==-1)
        q->R=q->F=0;
    else
        q->R=q->R+1;
    q->data[q->R]=p;
  }

int empty(Q *q)
 {
    if(q->R==-1)
        return(1);
    return(0);
 }

BSTnode *insert(BSTnode *,char *);
BSTnode *create();
BSTnode *mirror(BSTnode *T);
BSTnode *delet(BSTnode *T,char *x);
void leafnodes(BSTnode *T);
int height(BSTnode *T);
void level_wise(BSTnode *T);
void inorder(BSTnode *T);
BSTnode *find(BSTnode *root,char *x);

void main()
{
    BSTnode *root=NULL,*p;
    int op;
    char word[15],*wordp;
    clrscr();
    do
      {
        flushall();
        printf("\n\n1)Create");
        printf("\n2)Insert\n3)Delete\n4)Search");
        printf("\n5)Mirror");
        printf("\n6)Leaf Nodes");
        printf("\n7)Height(Depth)");
        printf("\n8)Quit");
        printf("\nEnter Your Choice :");
        scanf("%d",&op);
        switch(op)
          {
            case 1:    root=create();
                printf("\nInorder Traversal on the tree:\n");
                inorder(root);
                break;
            case 2: printf("\nEnter a Word : ");
                flushall();
                gets(word);
                root=insert(root,word);
                printf("\nInorder Traversal : ");
                inorder(root);
                break;
            case 3:    printf("\nEnter a word to be deleted :");
                flushall();
                gets(word);
                root=delet(root,word);
                printf("\nInorder Traversal : ");
                inorder(root);
                break;
            case 4:    printf("\nEnter a word to be searched :");
                flushall();
                gets(word);
                if(!find(root,word))
                    printf("\n ***** Not Found****");
                else
                    printf("\n ***** Found*****");
                break;
            case 5:    p=mirror(root);
                printf("\nLevel-wise traversal on original tree \n");
                level_wise(root);
                printf("\nLevel-wise traversal on mirror tree \n");
                level_wise(p);
                break;
            case 6: leafnodes(root);
                break;
            case 7: printf("\nHeight of the tree = %d",height(root));
                break;

          }
     }while(op!=8);
}

void inorder(BSTnode *T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        printf("%s\t",T->data);
        inorder(T->right);
    }
}


BSTnode *insert(BSTnode *T,char *x)
{
    BSTnode *p,*q,*r;
    int length;
    length=strlen(x);
    // acquire memory for the new node
    r=(BSTnode*)malloc(sizeof(BSTnode));
    r->data=(char*)malloc(length+1);
    strcpy(r->data,x);
    r->left=NULL;
    r->right=NULL;
    if(T==NULL)
        return(r);
    // find the leaf node for insertion
    p=T;
    while(p!=NULL)
    {
        q=p;
        if(strcmp(x,p->data)>0)
            p=p->right;
        else
            p=p->left;
    }
    if(strcmp(x,q->data)>0)
        q->right=r;  // x as right child of q
    else
        q->left=r;   //x as left child of q
    return(T);
}

BSTnode *create()
{       char x[15];
    int n,i;
    BSTnode *root;
    root=NULL;
    printf("\nEnter no. of nodes :");
    scanf("%d",&n);
    printf("\nEnter tree data(words): ");
    for(i=0;i<n;i++)
    {
        scanf("%s",x);
        root=insert(root,x);
    }
    return(root);
}
BSTnode *mirror(BSTnode *T)
 { BSTnode *p;
   int length;
   if(T!=NULL)
     {
    p=(BSTnode*)malloc(sizeof(BSTnode));
    length=strlen(T->data);
    p->data=(char*)malloc(length+1);
    strcpy(p->data,T->data);
    p->left=mirror(T->right);
    p->right=mirror(T->left);
    return(p);
     }
   else
    return(NULL);
 }

BSTnode *find(BSTnode *root,char *x)
{
    while(root!=NULL)
    {
        if(strcmp(x,root->data)==0)
            return(root);
        if(strcmp(x,root->data)>0)
            root=root->right;
        else
            root=root->left;
    }
    return(NULL);
}


void leafnodes(BSTnode *T)
 {
    if(T!=NULL)
      {
        if(T->left==NULL && T->right==NULL)
            printf("%s  ",T->data);
        else
          {
            leafnodes(T->left);
            leafnodes(T->right);
          }
      }
}

BSTnode *delet(BSTnode *T,char *x)
{
    BSTnode *temp;
    if(T==NULL)
    {
        printf("\nElement not found :");
        return(T);
    }
    if(strcmp(x,T->data)<0)                // delete in left subtree
    {
        T->left=delet(T->left,x);
        return(T);
    }
    if(strcmp(x,T->data)>0)                // delete in right subtree
    {
        T->right=delet(T->right,x);
        return(T);
    }

    // element is found
    if(T->left==NULL && T->right==NULL)   // a leaf node
    {
        temp=T;
        free(temp);
        return(NULL);
    }
    if(T->left==NULL)
    {
        temp=T;
        T=T->right;
        free(temp);
        return(T);
    }
    if(T->right==NULL)
    {
        temp=T;
        T=T->left;
        free(temp);
        return(T);
    }
    // node with two children
    //go to the inorder successor of the node
    temp=T->right;
    while(temp->left !=NULL)
      temp=temp->left;
    T->data=temp->data;
    T->right=delet(T->right,temp->data);
    return(T);
}


int height(BSTnode *T)
  {
    int lh,rh;
    if(T==NULL)
        return(0);
    if(T->left==NULL && T->right==NULL)
        return(0);
    return(max(height(T->left)+1,height(T->right)+1));
  }
void level_wise(BSTnode *T)
   {
    Q q,q1;
    init(&q);
    enqueue(&q,T);
    while(!empty(&q))
      { /*insert children of nodes at current level into q1*/
        init(&q1);
        printf("\n");
        while(!empty(&q))
           {
            T=dequeue(&q);
            printf("%s  ",T->data);
            if(T->left !=NULL)
                enqueue(&q1,T->left);
            if(T->right !=NULL)
                enqueue(&q1,T->right);
           }
        q=q1; /*next level is the current level */
      }
   }