SHARE
TWEET

lab10

ailuro Dec 14th, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4. #include <stdlib.h>
  5. #include <math.h>
  6. #include <locale.h>
  7. #define SIZE 10
  8.  
  9. struct node
  10. {
  11.     int data; //node will store an integer
  12.     struct node *right_child; // right child
  13.     struct node *left_child; // left child
  14. };
  15.  
  16.  
  17.  
  18. //function to find the minimum value in a node
  19. struct node* find_minimum(struct node *root)
  20. {
  21.     if(root == NULL)
  22.         return NULL;
  23.     else if(root->left_child != NULL) // node with minimum value will have no left child
  24.         return find_minimum(root->left_child); // left most element will be minimum
  25.     return root;
  26. }
  27.  
  28. //function to create a node
  29. struct node* new_node(int x)
  30. {
  31.     struct node *p;
  32.     p = malloc(sizeof(struct node));
  33.     p->data = x;
  34.     p->left_child = NULL;
  35.     p->right_child = NULL;
  36.  
  37.     return p;
  38. }
  39.  
  40. struct node* insert(struct node *root, int x)
  41. {
  42.     //searching for the place to insert
  43.     if(root==NULL)
  44.         return new_node(x);
  45.     else if(x>root->data) // x is greater. Should be inserted to right
  46.         root->right_child = insert(root->right_child, x);
  47.     else // x is smaller should be inserted to left
  48.         root->left_child = insert(root->left_child,x);
  49.     return root;
  50. }
  51.  
  52. // funnction to delete a node
  53. struct node* delete(struct node *root, int x)
  54. {
  55.     //searching for the item to be deleted
  56.     if(root==NULL)
  57.         return NULL;
  58.     if (x>root->data)
  59.         root->right_child = delete(root->right_child, x);
  60.     else if(x<root->data)
  61.         root->left_child = delete(root->left_child, x);
  62.     else
  63.     {
  64.         //No Children
  65.         if(root->left_child==NULL && root->right_child==NULL)
  66.         {
  67.             free(root);
  68.             return NULL;
  69.         }
  70.  
  71.         //One Child
  72.         else if(root->left_child==NULL || root->right_child==NULL)
  73.         {
  74.             struct node *temp;
  75.             if(root->left_child==NULL)
  76.                 temp = root->right_child;
  77.             else
  78.                 temp = root->left_child;
  79.             free(root);
  80.             return temp;
  81.         }
  82.  
  83.         //Two Children
  84.         else
  85.         {
  86.             struct node *temp = find_minimum(root->right_child);
  87.             root->data = temp->data;
  88.             root->right_child = delete(root->right_child, temp->data);
  89.         }
  90.     }
  91.     return root;
  92. }
  93.  
  94. void display(struct node *root)
  95. {
  96.  
  97.  
  98.     if(root!=NULL) // checking if the root is not null
  99.     {
  100.         display(root->left_child); // visiting left child
  101.         printf(" %d ", root->data); // printing data at root
  102.  
  103.         display(root->right_child);// visiting right child
  104.  
  105.     }
  106.  
  107.  
  108. }
  109.  
  110. int main()
  111. {
  112.  
  113.     struct node *root;
  114.     int y;
  115.     printf("Введите вершину дерева\n");
  116.     scanf("%d", &y);
  117.     root = new_node(y);
  118.  
  119.     int choice = 10, x;
  120.  
  121.     while(choice!=4)
  122.     {
  123.         printf("\n1.Добавить элемент\n2.Удалить элемент\n3.Показать элементы очереди\n4.Выход\n");
  124.         scanf("%d", &choice);
  125.         switch (choice)
  126.         {
  127.         case 1:
  128.             printf("Введите элемент\n");
  129.  
  130.             scanf("%d", &x);
  131.             insert(root,x);
  132.             break;
  133.  
  134.         case 2:
  135.             printf("Введите элемент\n");
  136.  
  137.             scanf("%d", &x);
  138.             delete(root, x);
  139.             break;
  140.  
  141.         case 3:
  142.  
  143.             display(root);
  144.             break;
  145.  
  146.  
  147.         case 4:
  148.             exit(-1);
  149.         default:
  150.             printf("\nПовторите ввод\n");
  151.         }
  152.  
  153.     }
  154.  
  155.  
  156.     return 0;
  157. }
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