Advertisement
Arnab_Manna

Binary tree

Jan 6th, 2023 (edited)
1,038
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.70 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. int count=0,max=0,min=0,len=0;
  5. int pre[100],post[100],in[100],ic=0,pc=0,poc=0;
  6. typedef struct node
  7. {
  8.     int info;
  9.     struct node *lc,*rc;
  10. }bst;
  11.  
  12. void create(bst *root)
  13. {  
  14.     len++;
  15.     char ans;
  16.     bst *ptr;
  17.     printf("\nDo you want to create the left child of %d? ",root->info);
  18.     fflush(stdin);
  19.     scanf("%c",&ans);
  20.     if(ans=='Y' || ans=='y')
  21.     {
  22.         ptr=(bst*)malloc(sizeof(bst));
  23.         printf("\nenter the information for the left child: ");
  24.         scanf("%d",&ptr->info);
  25.         ptr->lc=ptr->rc=NULL;
  26.         root->lc=ptr;
  27.         create(root->lc);
  28.     }
  29.     else
  30.         root->lc=NULL;
  31.     printf("\nDo you want to create the right child of %d? ",root->info);
  32.     fflush(stdin);
  33.     scanf("%c",&ans);
  34.     if(ans=='Y' || ans=='y')
  35.     {
  36.         ptr=(bst*)malloc(sizeof(bst));
  37.         printf("\nenter the information for the right child: ");
  38.         scanf("%d",&ptr->info);
  39.         ptr->lc=ptr->rc=NULL;
  40.         root->rc=ptr;
  41.         create(root->rc);
  42.     }
  43.     else
  44.         root->rc=NULL;
  45. }
  46.  
  47. void preorder(bst *root)
  48. {
  49.     if(root==NULL)
  50.         return;
  51.     printf("%d ",root->info);
  52.     preorder(root->lc);
  53.     preorder(root->rc);
  54. }
  55.  
  56. void inorder(bst *root)
  57. {
  58.     if(root==NULL)
  59.         return;
  60.     inorder(root->lc);
  61.     printf("%d ",root->info);
  62.     inorder(root->rc);
  63. }
  64.  
  65. void postorder(bst *root)
  66. {
  67.     if(root==NULL)
  68.         return;
  69.     postorder(root->lc);
  70.     postorder(root->rc);
  71.     printf("%d ",root->info);
  72. }
  73.  
  74. void cntleaf(bst *root)
  75. {
  76.    
  77.     if(root==NULL)
  78.         return;
  79.     if(root->lc==NULL && root->rc==NULL)
  80.     {
  81.         count++;
  82.         printf("leaf=%d\n",root->info);
  83.     }
  84.            
  85.     cntleaf(root->lc);
  86.     cntleaf(root->rc);
  87.      
  88. }
  89. void Search(bst *root,int n)
  90. {
  91.    
  92.     if(root==NULL)
  93.         return;
  94.     if(root->info==n)
  95.     {
  96.         count=1;
  97.         return;
  98.     }
  99.     Search(root->lc,n);
  100.     Search(root->rc,n);
  101. }
  102.  
  103. void min_max(bst *root)
  104. {
  105.    
  106.     if(root==NULL)
  107.         return;
  108.     if(root->info>=max)
  109.     {
  110.         max=root->info;
  111.     }
  112.     if(root->info<=min)
  113.     {
  114.         min=root->info;
  115.     }  
  116.     min_max(root->lc);
  117.     min_max(root->rc);
  118. }
  119.  
  120. void inSuc(bst *root)
  121. {
  122.     if(root==NULL)
  123.         return;
  124.     inSuc(root->lc);
  125.     //printf("%d ",root->info);
  126.     in[ic++]=root->info;
  127.     inSuc(root->rc);
  128. }
  129.  
  130. void posSuc(bst *root)
  131. {
  132.     if(root==NULL)
  133.         return;
  134.     posSuc(root->lc);
  135.     posSuc(root->rc);
  136.     //printf("%d ",root->info);
  137.     post[poc++]=root->info;
  138. }
  139.  
  140. void preSuc(bst *root)
  141. {
  142.     if(root==NULL)
  143.         return;
  144.     //printf("%d ",root->info);
  145.     pre[pc++]=root->info;
  146.     preSuc(root->lc);
  147.     preSuc(root->rc);
  148. }
  149.  
  150.  
  151. int main()
  152. {
  153.     bst *root=NULL,*ptr;
  154.     int ch,n,i,j=0,len=0;
  155.     printf("\nenter the information for the root: ");
  156.     ptr=(bst*)malloc(sizeof(bst));
  157.     scanf("%d",&ptr->info);
  158.     ptr->lc=ptr->rc=NULL;
  159.     root=ptr;
  160.     create(root);
  161.     while(1)
  162.     {
  163.         printf("\n**MENU**");
  164.         printf("\n1. Preorder\n2. Inorder\n3. Postorder\n4. no of leafs \n5. search\n6. max min\n7. inorder Successor \n8. postorder Successor \n9. preorder successor \n10. exit");
  165.         printf("\nenter your choice: ");
  166.         scanf("%d",&ch);
  167.         switch(ch)
  168.         {
  169.             case 1: preorder(root);
  170.                     break;
  171.             case 2: inorder(root);
  172.                     break;
  173.             case 3: postorder(root);
  174.                     break;
  175.             case 4:
  176.                     cntleaf(root);
  177.                     printf("no of leafs =%d",count);
  178.                     break;
  179.             case 5:
  180.                 printf("\nenter element to be searched: ");
  181.                 scanf("%d",&n);
  182.                 Search(root,n);
  183.                 if(count==1){
  184.                     printf("found");
  185.                 }
  186.                 else
  187.                 {
  188.                     printf("not found");
  189.                 }
  190.                 count=0;
  191.                 break;
  192.             case 6:
  193.                 max=root->info;
  194.                 min=root->info;
  195.                 min_max(root);
  196.                 printf("max =%d  min =%d",max,min);
  197.                 break;
  198.             case 7:
  199.                 printf("enter the value :");
  200.                 scanf("%d",&n);
  201.                  inSuc(root);
  202.                  j=0;
  203.                  len=ic;
  204.                  //printf("%d",len);
  205.                  for(i=0;i<len;i++)
  206.                  {
  207.                    
  208.                     if(in[i]==n)
  209.                     {
  210.                         j=1;
  211.                         break;
  212.                     }
  213.                  }
  214.                  if(j==1)
  215.                  {
  216.                     printf("%d",i);
  217.                     if(i==len-1)
  218.                         printf("no Successor");
  219.                     else
  220.                         printf("the successor of %d is %d",n,in[i+1]);
  221.                  }
  222.                  else
  223.                     printf("no successor");
  224.                  break;
  225.             case 8:
  226.                 printf("enter the value :");
  227.                 scanf("%d",&n);
  228.                  posSuc(root);
  229.                  j=0;
  230.                  len=poc;
  231.                  for(i=0;i<len;i++)
  232.                  {
  233.                     if(post[i]==n)
  234.                     {
  235.                         j=1;
  236.                          break;
  237.                     }
  238.                  }
  239.                  if(j==1){
  240.                     if(i==len-1)
  241.                     printf("no Successor");
  242.                     else
  243.                     printf("the successor of %d is %d",n,post[i+1]);
  244.                  }
  245.                  else
  246.                  printf("no node");
  247.                  break;
  248.             case 9:
  249.                 printf("enter the value :");
  250.                 scanf("%d",&n);
  251.                  preSuc(root);
  252.                  j=0;
  253.                  len=pc;
  254.                  for(i=0;i<len;i++)
  255.                  {
  256.                     if(pre[i]==n)
  257.                     {
  258.                         j=1;
  259.                          break;
  260.                     }
  261.                  }
  262.                  if(j==1){
  263.                     if(i==len-1)
  264.                     printf("no Successor");
  265.                     else
  266.                     printf("the successor of %d is %d",n,pre[i+1]);
  267.                  }
  268.                  else
  269.                  printf("no node");
  270.                  break;
  271.             case 10:exit(0);
  272.         }
  273.     }
  274. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement