#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 */
      }
   }

 #include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct treenode
{
     char data;
     struct treenode *left,*right;
}treenode;
typedef struct stack
  {
    treenode *data[20];
    int top;
  }stack;
void init(stack *s)
 {
    s->top=-1;
 }
treenode * pop(stack *s)
 {
    treenode *p;
    p=s->data[s->top];
    s->top=s->top-1;
    return(p);
 }
void  push(stack *s, treenode *p)
  {
    s->top=s->top+1;
    s->data[s->top]=p;
  }
int empty(stack *s)
 {
    if(s->top==-1)
        return(1);
    return(0);
 }
int full(stack *s)
  {
    if(s->top==19)
        return(1);
    return(0);
  }

treenode *create();
void inorder(treenode *T);
void preorder(treenode *T);
void postorder(treenode *T);
void non_rec_preorder(treenode *T);
void non_rec_inorder(treenode *T);
void non_rec_postorder(treenode *T);
void main()
{
    treenode *root=NULL,*p;
    int x,op;
    clrscr();
    do
      {
        printf("\n\n1)Create\n2)Preorder(recursive)");
        printf("\n3)Inorder(recursive)\n4)Posorder(Recursive)");
        printf("\n5)Preorder(Non-Recursive)\n6)Inorder(Non-Recursive)");
        printf("\n7)Postorder(Non-Recursive\n8)Quit");
        printf("\nEnter Your Choice :");
        scanf("%d",&op);
        switch(op)
          {
            case 1: root=create();break;
            case 2:    preorder(root);break;
            case 3:    inorder(root);break;
            case 4: postorder(root);break;
            case 5: non_rec_preorder(root);break;
            case 6: non_rec_inorder(root);break;
            case 7: non_rec_postorder(root);break;

          }
     }while(op!=8);
}


void inorder(treenode *T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        printf("%c",T->data);
        inorder(T->right);
    }
}

void preorder(treenode *T)
 {         if(T!=NULL)
      { printf("%c",T->data);
        preorder(T->left);
        preorder(T->right);
      }
 }
void postorder(treenode *T)
 {        if(T!=NULL)
      {
        postorder(T->left);
        postorder(T->right);
        printf("%c",T->data);
      }
 }
void non_rec_preorder(treenode *T)
 {
    stack s;
    init(&s);
    printf("\n");
    if(T==NULL)
        return;
    while(T!=NULL)
      {
        printf("%c",T->data);
        push(&s,T);
        T=T->left;
      }
      while(!empty(&s))
     {
        T=pop(&s);
        T=T->right;
        while(T!=NULL)
          {
            printf("%c",T->data);
            push(&s,T);
            T=T->left;
          }
     }

 }

void non_rec_inorder(treenode *T)
 {
    stack s;
    init(&s);
    printf("\n");
    if(T==NULL)
        return;
    while(T!=NULL)
      {
        push(&s,T);
        T=T->left;
      }
    while(!empty(&s))
      {
        T=pop(&s);
        printf("%c",T->data);
        T=T->right;
        while(T!=NULL)
           {
            push(&s,T);
            T=T->left;
           }
      }
 }

 void non_rec_postorder(treenode *T)
  {
    stack s,s1;
    treenode *flag;
    init(&s);init(&s1);
    printf("\n");
    if(T==NULL)
        return;
    while(T!=NULL)
       {
        push(&s,T);push(&s1,NULL);
        T=T->left;
       }
    while(!empty(&s))
       {
        T=pop(&s);flag=pop(&s1);
        if(flag!=NULL)
            printf("%c",T->data);
        else
          {
            push(&s,T);push(&s1,(treenode*)1);
            T=T->right;
            while(T!=NULL)
               {
                push(&s,T);push(&s1,NULL);
                T=T->left;
               }
         }
       }
  }

treenode * create()
 {
    char a[50];
    int i;
    treenode *p,*q,*root;
    stack s;
    init(&s);
    flushall();
    printf("\nEnter a postfix expression : ");
    gets(a);
    for(i=0;a[i]!='\0';i++)
       {
        if(isalnum(a[i]))
           {
            p=(treenode*)malloc(sizeof(treenode));
            p->left=p->right=NULL;
            p->data=a[i];
            push(&s,p);
           }
        else
           {
            q=pop(&s);
            p=pop(&s);
            root=(treenode*)malloc(sizeof(treenode));
            root->left=p;
            root->right=q;
            root->data=a[i];
            push(&s,root);
       }
    }
  root=pop(&s);
  return(root);
 }

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

typedef struct node
{
    int priority;
    char name[20];
    struct node *next;
}node;

void initialize(node **h)
{
    *h=NULL;
}
int empty(node *h)
{
    if(h==NULL)
        return 1;
    return 0;
}
void insert(node **h,char name[], int priority)
{
    node *p,*q;
    p=(node*)malloc(sizeof(node));
    strcpy(p->name,name);
    p->priority=priority;
    p->next=NULL;
    if(*h==NULL)//if the queue is empty
        *h=p;
    else
      {
        if(priority > (*h)->priority)//highest priority element
             {
            p->next=*h;
            *h=p;
             }
        else
             { //locate the point of insertion
            q=*h;
            while(q->next !=NULL && priority<=q->next->priority)
                q=q->next;
            //insert
            p->next=q->next;
            q->next=p;
             }
      }
 }
node *Delete(node **h)
 {
    node *p;
    p=*h;
    *h=p->next;
    return(p);
 }
void display(node *h)
  {
    printf("\n               Name      Priority");
    while(h!=NULL)
       {
        printf("\n%20s       %d",h->name,h->priority);
        switch(h->priority)
            {
            case 1: printf("   General Checkup");break;
            case 2: printf("   Non-serious");break;
            case 3: printf("   Serious");break;
            default:printf("   Unknown");
            }

        h=h->next;
      }
  }

void main()
 {
    node *head=NULL;
    node *p;
    int priority,op;
    char name[20];
    clrscr();
    do
       {
        printf("\n\n1)Enter a New Patient");
        printf("\n2)Service the next patient");
        printf("\n3)Display the list of patients");
        printf("\n4)Quit");
        printf("\nEnter Your Choice : ");
        scanf("%d",&op);
        switch(op)
           {
            case 1: printf("\nName of the patient : ");
                flushall();
                gets(name);
                printf("\nPriority(1- General checkup,2- non-serious,3- serious ): ");
                scanf("%d",&priority);
                insert(&head,name,priority);
                break;
            case 2: if(!empty(head))
                   {
                    p=Delete(&head);
                    printf("\n%s            %d",p->name,p->priority);
                    switch(p->priority)
                      {
                        case 1: printf("   General Checkup");break;
                        case 2: printf("   Non-serious");break;
                        case 3: printf("   Serious");break;
                        default:printf("   Unknown");
                      }
                    }
                else
                    printf("\nQueue is empty");
                break;
            case 3: display(head);break;
            }
    }while(op!=4);
}