Facebook
From Gracious Hamerkop, 1 Month ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 326
  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.     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.     //jezeli wezel ma szukana wartosc to odnalezlismy go
  76. if (root->number == number) return root;
  77.         //jezeli szukana wartosc jest mniejsza to szukamy w lewym poddrzewie o ile istnieje
  78. else if (number < root->number && root->left != NULL) return find(root->left, number);
  79.     //jezeli szukana wartosc jest wieksza to szukamy w prawym poddrzewie o ile istnieje    
  80. else if (number > root->number && root->right != NULL) return find(root->right, number);
  81. return NULL;
  82. }
  83.  
  84. struct node * minValueNode(struct node* node)
  85. {
  86.     struct node* current = node;
  87.  
  88.     /* loop down to find the leftmost leaf */
  89.     while (current && current->left != NULL)
  90.         current = current->left;
  91.  
  92.     return current;
  93. }
  94.  
  95. node* delete(node* root, int number) {
  96.     // base case
  97.     if (root == NULL) return root;
  98.  
  99.     // If the key to be deleted is smaller than the root's key,
  100.     // then it lies in left subtree
  101.     if (number < root->number)
  102.         root->left = delete(root->left, number);
  103.  
  104.     // If the key to be deleted is greater than the root's key,
  105.     // then it lies in right subtree
  106.     else if (number > root->number)
  107.         root->right = delete(root->right, number);
  108.  
  109.     // if key is same as root's key, then This is the node
  110.     // to be deleted
  111.     else
  112.     {
  113.         // node with only one child or no child
  114.         if (root->left == NULL)
  115.         {
  116.             struct node *temp = root->right;
  117.             free(root);
  118.             return temp;
  119.         }
  120.         else if (root->right == NULL)
  121.         {
  122.             struct node *temp = root->left;
  123.             free(root);
  124.             return temp;
  125.         }
  126.  
  127.         // node with two children: Get the inorder successor (smallest
  128.         // in the right subtree)
  129.         struct node* temp = minValueNode(root->right);
  130.  
  131.         // Copy the inorder successor's content to this node
  132.         root->number = temp->number;
  133.  
  134.         // Delete the inorder successor
  135.         root->right = delete(root->right, temp->number);
  136.     }
  137.     return root;
  138. }
  139.  
  140. int main() {
  141.     int n, r, f;
  142.     scanf("%d", &n);
  143.     scanf("%d", &r);
  144.     scanf("%d", &f);
  145.  
  146.     node* root = NULL;
  147.     int number;
  148.     char* name = malloc(MAX_NAME_SIZE*sizeof(char));
  149.  
  150.     while (n-- > 0) {
  151.         scanf("%d", &number);
  152.         scanf("%s", name);
  153.         root = insert(root, create_node(number, name));
  154.     }
  155.  
  156.     while (r-- > 0) {
  157.         scanf("%d", &number);
  158.         root = delete(root, number);
  159.     }
  160.  
  161.     while (f-- > 0) {
  162.         scanf("%d", &number);
  163.         node* x = find(root, number);
  164.         printf("%s\n", x == NULL ? "NOTFOUND" : x->name);
  165.     }
  166.  
  167.     delete_tree(root);
  168.     free(name);
  169. }