Advertisement
allekco

Binary tree

May 30th, 2018
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.59 KB | None | 0 0
  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.    
  36.     if (k<tmp->lengh) k=tmp->lengh;
  37. //  printf("\n lengh: %d \n", tmp -> lengh);
  38. //  printf("3");
  39.     return tmp;
  40. }
  41.  
  42. void add_node (node **head, int key){
  43.     if (*head == NULL){ //if tree empty
  44.         *head = new_node (key, NULL);
  45.     //  printf("4");
  46.     }
  47.     else{
  48.         node *iter = *head;
  49.     //  printf("5");
  50.         while (iter){
  51.         //  printf("6");
  52.             if (key >= (iter -> key)){
  53.             //  printf("7");
  54.                 if (iter -> right){
  55.                 //  printf("8");
  56.                     iter = iter -> right;
  57.                 }
  58.                 else{
  59.                 //  printf("9");
  60.                     iter -> right = new_node (key, iter);
  61.                     break;
  62.                 }
  63.             }
  64.             else{
  65.             //  printf("10");
  66.                 if (iter -> left){
  67.                 //  printf("11");
  68.                     iter = iter -> left;
  69.                
  70.                 }
  71.                 else{
  72.                 //  printf("12");
  73.                     iter -> left = new_node (key, iter);
  74.                     break;
  75.                 }
  76.             }  
  77.         }
  78.     }
  79. }
  80.  
  81. node* tree_search (node* head, int key){
  82.     if (head == NULL)
  83.         return NULL; //not founded     
  84.     if (key == head->key)
  85.         return head;
  86.     if (key < head->key)   
  87.         return tree_search (head->left, key);
  88.     else
  89.         return tree_search (head->right, key); 
  90. }
  91.  
  92.  
  93.  
  94. void output_tree (node *head) {
  95.     node *iter = head;
  96.     if (iter) {
  97.         output_tree (iter -> left);
  98.         printf("%d ", iter -> key);
  99.         output_tree (iter -> right);
  100.     }  
  101. }
  102.  
  103.  
  104.  
  105. int main (void){
  106.     int min, max, max_h, r;
  107.     srand(time(NULL));
  108.     printf ("Input min, max value and max hight of tree: ");
  109.     scanf ("%d %d %d", &min, &max, &max_h);
  110.     node *head = NULL;
  111.    
  112.     printf ("filling with random elements: \n");
  113.     while (k < max_h){
  114.         r = randomazer (min, max);
  115.         printf ("%d ", r);
  116.         add_node(&head, r);
  117.     }
  118.     printf ("\n");
  119.     output_tree (head);
  120.     printf ("\n\n");
  121.    
  122.     int behavior=1, behavior2=1, variety, variety2;
  123.     int add_key, search_key, delete_key;
  124.     node *iter;
  125.     iter = head;
  126.     node *tmp_search;
  127.    
  128.     while (behavior2){
  129.         printf ("Choose what u want:\n1-SEARCH\n2-ADD\n3-DELETE\n4-OUTPUT TREE\n5-WALK IN TREE\n0-If you want stop this\n");
  130.         printf ("Your choice: ");
  131.         scanf ("%d", &variety2);
  132.         switch (variety2){
  133.  
  134.             case 1:
  135.                 printf ("Key, what you search: ");
  136.                 scanf ("%d", &search_key);
  137.                 tmp_search = tree_search (head, search_key);
  138.                 if (tmp_search == NULL)
  139.                     printf ("No this key in tree\n");
  140.                 else
  141.                     printf ("This key was founded\n");
  142.                 break;
  143.             case 2:
  144.                 printf ("Added element:");
  145.                 scanf ("%d", &add_key);
  146.                 add_node (&head, add_key);
  147.                 printf ("\n");
  148.                 break;
  149.             case 3:
  150.                 printf ("Key, which delete: ");
  151.                 scanf ("%d", &delete_key);
  152.                 int tmp2;
  153.         //      tmp2 = delete_node (head, delete_key);
  154.                 if (tmp2 == -1)
  155.                     printf ("Error\n");
  156.                 else
  157.                     printf ("Element was deleted\n");
  158.                 break;
  159.             case 4:
  160.                 output_tree (head);
  161.                 printf ("\n");
  162.                 break;
  163.             case 5:
  164.                 printf ("\n");
  165.                 while (behavior){
  166.                     printf("Current node: %d\n", iter->key);
  167.                     if(iter->left != NULL)
  168.                         printf("Left child: %d\n", iter->left->key);
  169.                     if(iter->right != NULL)
  170.                         printf("Right child: %d\n", iter->right->key);
  171.                     printf ("Choose what u want:\n1-Higher level\n2-To left son\n3-To right son\n0-If you want stop this\n");
  172.                     printf ("Your choice: ");
  173.                     scanf ("%d", &variety);
  174.                     switch (variety){
  175.                     case 1:
  176.                         if(iter->parent != NULL)
  177.                             iter = iter->parent;
  178.                         else
  179.                             printf("No parent node\n");
  180.                         break;
  181.                     case 2:
  182.                         if (iter->left != NULL)
  183.                             iter = iter->left;
  184.                         else
  185.                             printf ("The left child node is missing\n");    
  186.                         break;
  187.                     case 3:
  188.                         if (iter->right != NULL)
  189.                             iter = iter->right;
  190.                         else
  191.                             printf ("The right child node is missing\n");
  192.                         break;
  193.                     case 0:
  194.                         behavior = 0;
  195.                         break;
  196.                     default:
  197.                         printf("Wrong input1\n" );
  198.                         break;
  199.                     }
  200.                 }      
  201.                 break;
  202.             case 0:
  203.                 behavior2 = 0;
  204.                 break;
  205.             default:
  206.                 printf("Wrong input2\n" );
  207.                 break;
  208.         }
  209.         printf ("\n");
  210.     }
  211.      
  212.      return 0;
  213. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement