Facebook
From Sole Gibbon, 2 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 603
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <string.h>
  5.  
  6. char MAX_NAME_SIZE = 30;
  7.  
  8. typedef struct node {
  9.     struct node *left, *right, *parent;
  10.     int number;
  11.     char* name;
  12. } node;
  13.  
  14. node* create_node(int number, char* name) {
  15.     struct node *temp =  (struct node *)malloc(sizeof(struct node));
  16.     temp->number = number;
  17.     temp->left = NULL;
  18.     temp->right = NULL;
  19.     temp->parent = NULL;
  20.     strcpy(temp->name,name);
  21.     return temp;
  22. }
  23.  
  24. void delete_tree(node* root) {
  25.     if (root == NULL) return;
  26.  
  27.     /* first delete both subtrees */
  28.     delete_tree(root->left);
  29.     delete_tree(root->right);
  30.     free(root);
  31. }
  32.  
  33. node* insert (node* root, node* to_insert) {
  34. //jezeli drzewo jest puste to dodaj korzen
  35. if (root == NULL){
  36.     root = to_insert;
  37.     root->number = to_insert->number;
  38.     root->name = to_insert->name;
  39.     root->left = NULL;
  40.     root->right = NULL;
  41.     root->parent = NULL;
  42. }
  43. //jezeli zadana wartosc jest mniejsza od korzenia idz do lewego poddrzewa
  44. else if(to_insert->number < root->number) {
  45. //jezeli lewe poddrzewo istnieje wywolaj dla niego ta funkcje rekurencyjnie
  46.     if(root->left != NULL) {
  47.         insert(root->left,to_insert);
  48. }
  49. //jezeli lewe poddrzewo nie istnieje dodaj nowy wezel o zadanej wartosci
  50.     else {
  51.         to_insert->left = NULL;
  52.         to_insert->right = NULL;
  53.         to_insert->parent = root;
  54.         root->left=to_insert;
  55. }
  56. }
  57. //jezeli zadana wartosc jest wieksza lub rowna korzeniowi idz do prawego poddrzewa
  58. else {
  59. //jezeli prawe poddrzewo istnieje wywolaj dla niego ta funkcje rekurencyjnie
  60.     if(root->right!=NULL) {
  61.         insert(root->right,to_insert);
  62. }
  63. //jezeli prawe poddrzewo nie istnieje dodaj nowy wezel o zadanej wartosci
  64.     else {
  65.         to_insert->left = NULL;
  66.         to_insert->right = NULL;
  67.         to_insert->parent = root;
  68.         root->right=to_insert;
  69. }
  70. }
  71.    return root;
  72. }
  73.  
  74. node* find (node* root, int number) {
  75. if(root==NULL || root->number==number) //if root->data is x then the element is found
  76.         return root;
  77.     else if(number>root->number) // x is greater, so we will search the right subtree
  78.         return find(root->right, number);
  79.     else //x is smaller than the data, so we will search the left subtree
  80.         return find(root->left,number);
  81. }
  82.  
  83. node* FindMin(node* root) {
  84.     struct node *current =  (struct node *)malloc(sizeof(struct node));
  85.   current = root;
  86.     /* loop down to find the leftmost leaf */
  87.     while (current && current->left != NULL)
  88.         current = current->left;
  89.  
  90.     return current;
  91. }
  92.  
  93. node* Delete (node* root, int number) {
  94.      if (root == NULL) {
  95.      return NULL;
  96.   }
  97.   if (number < root->number) {  // data is in the left sub tree.
  98.       root->left = Delete(root->left, number);
  99.   } else if (number > root->number) { // data is in the right sub tree.
  100.       root->right = Delete(root->right, number);
  101.   } else {
  102.      // case 1: no children
  103.      if (root->left == NULL && root->right == NULL) {
  104.         free(root); // wipe out the memory, in C, use free function
  105.         root = NULL;
  106.      }
  107.      // case 2: one child (right)
  108.      else if (root->left == NULL) {
  109.         struct node *temp = root; // save current node as a backup
  110.         root = root->right;
  111.         free(temp);
  112.      }
  113.      // case 3: one child (left)
  114.      else if (root->right == NULL) {
  115.         struct node *temp = root; // save current node as a backup
  116.         root = root->left;
  117.         free(temp);
  118.      }
  119.      // case 4: two children
  120.      else {
  121.         struct node *temp = FindMin(root->right); // find minimal value of right sub tree
  122.         root->number = temp->number; // duplicate the node
  123.         root->right = Delete(root->right, temp->number); // delete the duplicate node
  124.      }
  125.   }
  126.   return root; // parent node can update reference
  127. }
  128. void print_in_order(node* root) {
  129.     if (root != NULL)
  130.     {
  131.         print_in_order(root->left);
  132.         printf("%d \n", root->number);
  133.         printf("%s \n", root->name);
  134.         print_in_order(root->right);
  135.     }
  136. }
  137. int main() {
  138.     int n, r, f;
  139.     scanf("%d", &n);
  140.     scanf("%d", &r);
  141.     scanf("%d", &f);
  142.  
  143.     node* root = NULL;
  144.     int number;
  145.     char* name = malloc(MAX_NAME_SIZE*sizeof(char));
  146.  
  147.     while (n-- > 0) {
  148.         scanf("%d", &number);
  149.         scanf("%s", name);
  150.         root = insert(root, create_node(number, name));
  151.         print_in_order(root);
  152.     }
  153.  
  154.     while (r-- > 0) {
  155.         scanf("%d", &number);
  156.         root = Delete(root, number);
  157.         print_in_order(root);
  158.     }
  159.  
  160.     while (f-- > 0) {
  161.         scanf("%d", &number);
  162.         node* x = find(root, number);
  163.         printf("%s\n", x == NULL ? "NOTFOUND" : x->name);
  164.         print_in_order(root);
  165.     }
  166.  
  167.     delete_tree(root);
  168.     free(name);
  169. }