SHARE
TWEET

Binary Tree

Sharif4896 Mar 26th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # include <stdio.h>
  2. # include <malloc.h>
  3.  
  4. struct node
  5. {
  6.     int info;
  7.     struct node *lchild;
  8.     struct node *rchild;
  9. }*root;
  10.  
  11.  
  12.  
  13. void find(int item,struct node **par,struct node **loc)
  14. {
  15.     struct node *ptr,*ptrsave;
  16.  
  17.     if(root==NULL)  /*tree empty*/
  18.     {
  19.         *loc=NULL;
  20.         *par=NULL;
  21.         return;
  22.     }
  23.     if(item==root->info) /*item is at root*/
  24.     {
  25.         *loc=root;
  26.         *par=NULL;
  27.         return;
  28.     }
  29.     /*Initialize ptr and ptrsave*/
  30.     if(item<root->info)
  31.         ptr=root->lchild;
  32.     else
  33.         ptr=root->rchild;
  34.     ptrsave=root;
  35.  
  36.     while(ptr!=NULL)
  37.     {
  38.         if(item==ptr->info)
  39.         {       *loc=ptr;
  40.             *par=ptrsave;
  41.             return;
  42.         }
  43.         ptrsave=ptr;
  44.         if(item<ptr->info)
  45.             ptr=ptr->lchild;
  46.         else
  47.             ptr=ptr->rchild;
  48.      }/*End of while */
  49.      *loc=NULL;   /*item not found*/
  50.      *par=ptrsave;
  51. }/*End of find()*/
  52.  
  53. void insert(int item)
  54. {       struct node *tmp,*parent,*location;
  55.     find(item,&parent,&location);
  56.     if(location!=NULL)
  57.     {
  58.         printf("Item already present");
  59.         return;
  60.     }
  61.  
  62.     tmp=(struct node *)malloc(sizeof(struct node));
  63.     tmp->info=item;
  64.     tmp->lchild=NULL;
  65.     tmp->rchild=NULL;
  66.  
  67.     if(parent==NULL)
  68.         root=tmp;
  69.     else
  70.         if(item<parent->info)
  71.             parent->lchild=tmp;
  72.         else
  73.             parent->rchild=tmp;
  74. }/*End of insert()*/
  75.  
  76.  
  77. void case_a(struct node *par,struct node *loc )
  78. {
  79.     if(par==NULL) /*item to be deleted is root node*/
  80.         root=NULL;
  81.     else
  82.         if(loc==par->lchild)
  83.             par->lchild=NULL;
  84.         else
  85.             par->rchild=NULL;
  86. }/*End of case_a()*/
  87.  
  88. void case_b(struct node *par,struct node *loc)
  89. {
  90.     struct node *child;
  91.  
  92.     /*Initialize child*/
  93.     if(loc->lchild!=NULL) /*item to be deleted has lchild */
  94.         child=loc->lchild;
  95.     else                /*item to be deleted has rchild */
  96.         child=loc->rchild;
  97.  
  98.     if(par==NULL )   /*Item to be deleted is root node*/
  99.         root=child;
  100.     else
  101.         if( loc==par->lchild)   /*item is lchild of its parent*/
  102.             par->lchild=child;
  103.         else                  /*item is rchild of its parent*/
  104.             par->rchild=child;
  105. }/*End of case_b()*/
  106.  
  107. void case_c(struct node *par,struct node *loc)
  108. {
  109.     struct node *ptr,*ptrsave,*suc,*parsuc;
  110.  
  111.     /*Find inorder successor and its parent*/
  112.     ptrsave=loc;
  113.     ptr=loc->rchild;
  114.     while(ptr->lchild!=NULL)
  115.     {
  116.         ptrsave=ptr;
  117.         ptr=ptr->lchild;
  118.     }
  119.     suc=ptr;
  120.     parsuc=ptrsave;
  121.  
  122.     if(suc->lchild==NULL && suc->rchild==NULL)
  123.         case_a(parsuc,suc);
  124.     else
  125.         case_b(parsuc,suc);
  126.  
  127.     if(par==NULL) /*if item to be deleted is root node */
  128.         root=suc;
  129.     else
  130.         if(loc==par->lchild)
  131.             par->lchild=suc;
  132.         else
  133.             par->rchild=suc;
  134.  
  135.     suc->lchild=loc->lchild;
  136.     suc->rchild=loc->rchild;
  137. }/*End of case_c()*/
  138. int del(int item)
  139. {
  140.     struct node *parent,*location;
  141.     if(root==NULL)
  142.     {
  143.         printf("Tree empty");
  144.         return 0;
  145.     }
  146.  
  147.     find(item,&parent,&location);
  148.     if(location==NULL)
  149.     {
  150.         printf("Item not present in tree");
  151.         return 0;
  152.     }
  153.  
  154.     if(location->lchild==NULL && location->rchild==NULL)
  155.         case_a(parent,location);
  156.     if(location->lchild!=NULL && location->rchild==NULL)
  157.         case_b(parent,location);
  158.     if(location->lchild==NULL && location->rchild!=NULL)
  159.         case_b(parent,location);
  160.     if(location->lchild!=NULL && location->rchild!=NULL)
  161.         case_c(parent,location);
  162.     free(location);
  163. }/*End of del()*/
  164.  
  165. int preorder(struct node *ptr)
  166. {
  167.     if(root==NULL)
  168.     {
  169.         printf("Tree is empty");
  170.         return 0;
  171.     }
  172.     if(ptr!=NULL)
  173.     {
  174.         printf("%d  ",ptr->info);
  175.         preorder(ptr->lchild);
  176.         preorder(ptr->rchild);
  177.     }
  178. }/*End of preorder()*/
  179.  
  180. void inorder(struct node *ptr)
  181. {
  182.     if(root==NULL)
  183.     {
  184.         printf("Tree is empty");
  185.         return;
  186.     }
  187.     if(ptr!=NULL)
  188.     {
  189.         inorder(ptr->lchild);
  190.         printf("%d  ",ptr->info);
  191.         inorder(ptr->rchild);
  192.     }
  193. }/*End of inorder()*/
  194.  
  195. void postorder(struct node *ptr)
  196. {
  197.     if(root==NULL)
  198.     {
  199.         printf("Tree is empty");
  200.         return;
  201.     }
  202.     if(ptr!=NULL)
  203.     {
  204.         postorder(ptr->lchild);
  205.         postorder(ptr->rchild);
  206.         printf("%d  ",ptr->info);
  207.     }
  208. }/*End of postorder()*/
  209.  
  210. void display(struct node *ptr,int level)
  211. {
  212.     int i;
  213.     if ( ptr!=NULL )
  214.     {
  215.         display(ptr->rchild, level+1);
  216.         printf("\n");
  217.         for (i = 0; i < level; i++)
  218.             printf("    ");
  219.         printf("%d", ptr->info);
  220.         display(ptr->lchild, level+1);
  221.     }/*End of if*/
  222. }/*End of display()*/
  223. main()
  224. {
  225.     int choice,num;
  226.     root=NULL;
  227.     while(1)
  228.     {
  229.         printf("\n");
  230.         printf("1.Insert\n");
  231.         printf("2.Delete\n");
  232.         printf("3.Inorder Traversal\n");
  233.         printf("4.Preorder Traversal\n");
  234.         printf("5.Postorder Traversal\n");
  235.         printf("6.Display\n");
  236.         printf("7.Quit\n");
  237.         printf("Enter your choice : ");
  238.         scanf("%d",&choice);
  239.  
  240.         switch(choice)
  241.         {
  242.          case 1:
  243.             printf("Enter the number to be inserted : ");
  244.             scanf("%d",&num);
  245.             insert(num);
  246.             break;
  247.          case 2:
  248.             printf("Enter the number to be deleted : ");
  249.             scanf("%d",&num);
  250.             del(num);
  251.             break;
  252.          case 3:
  253.             inorder(root);
  254.             break;
  255.          case 4:
  256.             preorder(root);
  257.             break;
  258.          case 5:
  259.             postorder(root);
  260.             break;
  261.          case 6:
  262.             display(root,1);
  263.             break;
  264.          case 7:
  265.             break;
  266.          default:
  267.             printf("Wrong choice\n");
  268.         }/*End of switch */
  269.     }/*End of while */
  270. }/*End of main()*/
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top