SHARE
TWEET

BINARY TREE DONE

allekco May 30th, 2018 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5. #include <stddef.h>
  6. #include <time.h>
  7.  
  8. int k = 0;
  9.  
  10. int randomazer (int min, int max){
  11.     float random;
  12.     random = rand();
  13.     random = (random / RAND_MAX) * (max-min) + min;
  14.     return((int)random);
  15. }
  16.  
  17. typedef struct fff {
  18.     int key;
  19.     int lengh;
  20.     struct fff *left;
  21.     struct fff *right;
  22.     struct fff *parent;
  23. } node;
  24.  
  25.  
  26. node* new_node (int key, node *parent){
  27.     node *tmp = (node*)malloc(sizeof(node));
  28.     tmp -> left = tmp -> right = NULL;
  29.     tmp -> key = key;
  30.     tmp -> parent = parent;
  31.     tmp -> lengh = 1;
  32.     if (parent!=NULL) {
  33.         tmp -> lengh = tmp -> parent -> lengh +1;
  34.     }
  35.     if (k<tmp->lengh) k=tmp->lengh;
  36.     return tmp;
  37. }
  38.  
  39. void add_node (node **head, int key){
  40.     if (*head == NULL){ //if tree empty
  41.         *head = new_node (key, NULL);
  42.     }
  43.     else{
  44.         node *iter = *head;
  45.         while (iter){
  46.             if (key >= (iter -> key)){
  47.                 if (iter -> right){
  48.                     iter = iter -> right;
  49.                 }
  50.                 else{
  51.                     iter -> right = new_node (key, iter);
  52.                     break;
  53.                 }
  54.             }
  55.             else{
  56.                 if (iter -> left){
  57.                     iter = iter -> left;
  58.                 }
  59.                 else{
  60.                     iter -> left = new_node (key, iter);
  61.                     break;
  62.                 }
  63.             }  
  64.         }
  65.     }
  66. }
  67.  
  68. node* tree_search (node* head, int key){
  69.     if (head == NULL)
  70.         return NULL; //not founded     
  71.     if (key == head->key)
  72.         return head;
  73.     if (key < head->key)   
  74.         return tree_search (head->left, key);
  75.     else
  76.         return tree_search (head->right, key); 
  77. }
  78.  
  79. void output_tree (node *head) {
  80.     node *iter = head;
  81.     if (iter) {
  82.         output_tree (iter -> left);
  83.         printf("%d ", iter -> key);
  84.         output_tree (iter -> right);
  85.     }  
  86. }
  87.  
  88. int tree_minimum (node *head){
  89.     while (head->left != NULL){
  90.         head = head->left;
  91.     }
  92.     return head->key;
  93. }
  94.  
  95. int tree_maximum (node *head){
  96.     while (head->right != NULL){
  97.         head = head->right;
  98.     }
  99.     return head->key;  
  100. }
  101.  
  102. int tree_successor (node *head, int key){
  103.     int max;
  104.     max = tree_maximum (head);
  105.     if (key == max){
  106.         printf ("This element has max value\n");
  107.         return 0;
  108.     }
  109.     node *x;
  110.     x = tree_search (head, key);
  111.     if (x == NULL)
  112.         return -1;
  113.     if (x->right != NULL)
  114.         return tree_minimum (x->right);
  115.     node *iter;
  116.     iter = x->parent;
  117.     while ((iter != NULL)&&(iter->right)){
  118.         head = iter;
  119.         iter = iter->parent;
  120.     }
  121.     return iter->key;
  122. }
  123.  
  124. int tree_predecessor (node *head, int key){
  125.     int min;
  126.     min = tree_minimum (head);
  127.     if (key == min){
  128.         printf ("This element has min value\n");
  129.         return 0;
  130.     }
  131.     node *x;
  132.     x = tree_search (head, key);
  133.     if (x == NULL)
  134.         return -1;
  135.     if (x->left != NULL)
  136.         return tree_maximum (x->left);
  137.     node *iter;
  138.     iter = x->parent;
  139.     while ((iter != NULL)&&(iter->left)){
  140.         head = iter;
  141.         iter = iter->parent;
  142.     }
  143.     return iter->key;
  144. }
  145.  
  146. void transplant (node **head, node *uu, node *v){
  147.     if (uu->parent == NULL){
  148.         *head = v;
  149.     }
  150.     else{
  151.         if(uu == uu->parent->left)
  152.             uu->parent->left = v;
  153.         else
  154.             uu->parent->right = v;
  155.     }
  156.     if (v != NULL)
  157.         v->parent = uu->parent;
  158.         free (uu);
  159. }
  160.  
  161. void tree_delete (node **head, int key){
  162.     node *z;
  163.     z = tree_search (*head, key);
  164.     if (z->left == NULL)
  165.         transplant (&*head, z, z->right);
  166.     else{
  167.         if (z->right == NULL)
  168.             transplant (head, z, z->left);
  169.         else{
  170.             node *y;
  171.             int tmp;           
  172.             tmp = tree_minimum (z->right);
  173.             y = tree_search (*head, tmp);
  174.             if (y->parent != z){
  175.                 transplant (&*head, y, y->right);
  176.                 y->right = z->right;
  177.                 y->right->parent = y;              
  178.             }
  179.             transplant (&*head, z, y);
  180.             y->left = z->left;
  181.             y->left->parent = y;
  182.         }
  183.     }  
  184. }
  185.  
  186.  
  187. int main (void){
  188.     int min, max, max_h, r;
  189.     srand(time(NULL));
  190.     printf ("Input min, max value and max hight of tree: ");
  191.     scanf ("%d %d %d", &min, &max, &max_h);
  192.     node *head = NULL;
  193.    
  194.     printf ("filling with random elements: \n");
  195.     while (k < max_h){
  196.         r = randomazer (min, max);
  197.         printf ("%d ", r);
  198.         add_node(&head, r);
  199.     }
  200.     printf ("\n");
  201.     output_tree (head);
  202.     printf ("\n\n");
  203.    
  204.     int behavior=1, behavior2=1, variety, variety2;
  205.     int add_key, search_key, delete_key, max_key, min_key, key_6, key_7, next_key, previous_key;
  206.     node *iter;
  207.     iter = head;
  208.     node *tmp_search;
  209.    
  210.     while (behavior2){
  211.         printf ("Choose what u want:\n1-SEARCH\n2-ADD\n3-DELETE\n4-OUTPUT TREE\n5-MAX & MIN VALUE\n6-NEXT IN VALUE\n7-PREVIOUS IN VALUE\n8-WALK IN TREE\n0-If you want stop this\n");
  212.         printf ("Your choice: ");
  213.         scanf ("%d", &variety2);
  214.         switch (variety2){
  215.  
  216.             case 1:
  217.                 printf ("Key, what you search: ");
  218.                 scanf ("%d", &search_key);
  219.                 tmp_search = tree_search (head, search_key);
  220.                 if (tmp_search == NULL)
  221.                     printf ("No this key in tree\n");
  222.                 else
  223.                     printf ("This key was founded\n");
  224.                 break;
  225.             case 2:
  226.                 printf ("Added element:");
  227.                 scanf ("%d", &add_key);
  228.                 add_node (&head, add_key);
  229.                 printf ("\n");
  230.                 break;
  231.             case 3:
  232.                 printf ("Key, which delete: ");
  233.                 scanf ("%d", &delete_key);
  234.                 tree_delete (&head, delete_key);
  235.                 printf ("Element was deleted\n");
  236.                 break;
  237.             case 4:
  238.                 output_tree (head);
  239.                 printf ("\n");
  240.                 break;
  241.             case 5:
  242.                 max_key = tree_maximum (head);
  243.                 min_key = tree_minimum (head);
  244.                 printf ("Min = %d, Max = %d\n", min_key, max_key);
  245.                 break;
  246.             case 6:
  247.                 printf ("Input key: ");
  248.                 scanf ("%d", &key_6);
  249.                 next_key = tree_successor (head, key_6);
  250.                 if (next_key == -1)
  251.                     printf ("No this element in tree\n");
  252.                 else{
  253.                     if (next_key != 0)
  254.                         printf ("Next key: %d\n", next_key);                   
  255.                 }
  256.                 break;
  257.             case 7:
  258.                 printf ("Input key: ");
  259.                 scanf ("%d", &key_7);
  260.                 previous_key = tree_predecessor (head, key_7);
  261.                 if (previous_key == -1)
  262.                     printf ("No this element in tree\n");
  263.                 else{
  264.                     if (previous_key != 0)
  265.                         printf ("Next key: %d\n", previous_key);                   
  266.                 }              
  267.                 break;
  268.             case 8:
  269.                 printf ("\n");
  270.                 while (behavior){
  271.                     printf("Current node: %d\n", iter->key);
  272.                     if(iter->left != NULL)
  273.                         printf("Left child: %d\n", iter->left->key);
  274.                     if(iter->right != NULL)
  275.                         printf("Right child: %d\n", iter->right->key);
  276.                     printf ("Choose what u want:\n1-Higher level\n2-To left son\n3-To right son\n0-If you want stop this\n");
  277.                     printf ("Your choice: ");
  278.                     scanf ("%d", &variety);
  279.                     switch (variety){
  280.                     case 1:
  281.                         if(iter->parent != NULL)
  282.                             iter = iter->parent;
  283.                         else
  284.                             printf("No parent node\n");
  285.                         break;
  286.                     case 2:
  287.                         if (iter->left != NULL)
  288.                             iter = iter->left;
  289.                         else
  290.                             printf ("The left child node is missing\n");    
  291.                         break;
  292.                     case 3:
  293.                         if (iter->right != NULL)
  294.                             iter = iter->right;
  295.                         else
  296.                             printf ("The right child node is missing\n");
  297.                         break;
  298.                     case 0:
  299.                         behavior = 0;
  300.                         break;
  301.                     default:
  302.                         printf("Wrong input1\n" );
  303.                         break;
  304.                     }
  305.                     printf ("\n");
  306.                 }      
  307.                 break;
  308.             case 0:
  309.                 behavior2 = 0;
  310.                 break;
  311.             default:
  312.                 printf("Wrong input2\n" );
  313.                 break;
  314.         }
  315.         printf ("\n");
  316.     }
  317.      
  318.     return 0;
  319. }
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