SHARE
TWEET

lab9

a guest May 23rd, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4. #define COUNT 10
  5.  
  6. struct tree_node
  7. {
  8.     int key;
  9.     char value;
  10.     struct tree_node *left_child, *right_child;
  11. } *root;
  12.  
  13. void add_node(struct tree_node **root, int key, char value)
  14. {
  15.     if(*root==NULL)
  16.     {
  17.         *root = (struct tree_node *)malloc(sizeof(struct tree_node));
  18.         if(*root)
  19.         {
  20.             (*root)->key = key;
  21.             (*root)->value = value;
  22.             (*root)->left_child = (*root)->right_child = NULL;
  23.         }
  24.     }
  25.     else if ((*root)->key >= key)
  26.         add_node(&(*root)->left_child,key,value);
  27.     else
  28.         add_node(&(*root)->right_child,key,value);
  29. }
  30.  
  31. void add_node_iteratively(struct tree_node **root, int key, char value)
  32. {
  33.     while(*root!=NULL)
  34.     {
  35.         if((*root)->key>=key)
  36.             root = &(*root)->left_child;
  37.         else
  38.             root = &(*root)->right_child;
  39.     }
  40.     *root = (struct tree_node *)
  41.             malloc(sizeof(struct tree_node));
  42.     if(*root)
  43.     {
  44.         (*root)->key = key;
  45.         (*root)->value = value;
  46.         (*root)->left_child = (*root)->right_child = NULL;
  47.     }
  48. }
  49.  
  50. void print_inorder(struct tree_node *root)
  51. {
  52.     if(root)
  53.     {
  54.         print_inorder(root->left_child);
  55.         printf("klucz: %d, wartosc: %c\n",root->key, root->value);
  56.         print_inorder(root->right_child);
  57.     }
  58. }
  59.  
  60. void print_inorder_reverse(struct tree_node *root)
  61. {
  62.     if(root)
  63.     {
  64.         print_inorder_reverse(root->right_child);
  65.         printf("klucz: %d, wartosc: %c\n",root->key, root->value);
  66.         print_inorder_reverse(root->left_child);
  67.     }
  68. }
  69.  
  70. void print_preorder(struct tree_node *root)
  71. {
  72.     if(root)
  73.     {
  74.         printf("klucz: %d, wartosc: %c\n",root->key, root->value);
  75.         print_preorder(root->left_child);
  76.         print_preorder(root->right_child);
  77.     }
  78. }
  79.  
  80. void print_postorder(struct tree_node *root)
  81. {
  82.     if(root)
  83.     {
  84.         print_postorder(root->left_child);
  85.         print_postorder(root->right_child);
  86.         printf("klucz: %d, wartosc: %c\n",root->key, root->value);
  87.     }
  88. }
  89.  
  90. int height(struct tree_node* root)
  91. {
  92.     if (root==NULL)
  93.         return 0;
  94.     else
  95.     {
  96.         int lheight = height(root->left_child);
  97.         int rheight = height(root->right_child);
  98.  
  99.         if (lheight > rheight)
  100.             return(lheight+1);
  101.         else
  102.             return(rheight+1);
  103.     }
  104. }
  105.  
  106. struct tree_node *find_node(struct tree_node *root, int key)
  107. {
  108.     if(root && root->key > key)
  109.         return find_node(root->left_child,key);
  110.     else if(root && root->key < key)
  111.         return find_node(root->right_child,key);
  112.     else
  113.         return root;
  114. }
  115.  
  116. // wyswietlanie danego poziomu
  117. void print_level(struct tree_node* root, int level)
  118. {
  119.     if (root == NULL)
  120.         return;
  121.     if (level == 1)
  122.         printf("%d ", root->key);
  123.     else if (level > 1)
  124.     {
  125.         print_level(root->left_child, level-1);
  126.         print_level(root->right_child, level-1);
  127.     }
  128. }
  129.  
  130. // wyswietlanie wszystkich poziomow
  131. void print_levelorder(struct tree_node* root)
  132. {
  133.     int h = height(root);
  134.     int i;
  135.     for (i=1; i<=h; i++){
  136.         print_level(root, i);
  137.         puts("");
  138.     }
  139. }
  140.  
  141. void print_graphic(struct tree_node *root, int space)
  142. {
  143.     int i;
  144.     // Base case
  145.     if (root == NULL)
  146.         return;
  147.  
  148.     // Increase distance between levels
  149.     space += COUNT;
  150.  
  151.     // Process right child first
  152.     print_graphic(root->right_child, space);
  153.  
  154.     // Print current node after space
  155.     // count
  156.     printf("\n");
  157.     for (i = COUNT; i < space; i++)
  158.         printf(" ");
  159.     printf("%d\n", root->key);
  160.  
  161.     // Process left child
  162.     print_graphic(root->left_child, space);
  163. }
  164.  
  165. void menu()
  166. {
  167.     int key;
  168.     int pick;
  169.     puts("\n1. Wyswietlanie drzewa inorder");
  170.     puts("2. Wyswietlanie drzewa inorder od tylu");
  171.     puts("3. Wyswietlanie drzewa preorder");
  172.     puts("4. Wyswietlanie drzewa postorder");
  173.     puts("5. Wysokosc drzewa");
  174.     puts("6. Wyszukiwanie danego elementu");
  175.     puts("7. Wyswietlanie levelorder");
  176.     puts("8. Wyswietlanie drzewa w postaci semi-graficznej");
  177.     puts("0. Koniec");
  178.     scanf("%d", &pick);
  179.     system("cls");
  180.  
  181.     switch(pick)
  182.     {
  183.     case 1:
  184.         print_inorder(root);
  185.         puts("\n");
  186.         menu();
  187.         system("cls");
  188.         break;
  189.     case 2:
  190.         print_inorder_reverse(root);
  191.         puts("\n");
  192.         menu();
  193.         system("cls");
  194.         break;
  195.     case 3:
  196.         print_preorder(root);
  197.         puts("\n");
  198.         menu();
  199.         system("cls");
  200.         break;
  201.     case 4:
  202.         print_postorder(root);
  203.         puts("\n");
  204.         menu();
  205.         system("cls");
  206.         break;
  207.     case 5:
  208.         printf("Wysokosc drzewa: %d\n", height(root));
  209.         puts("");
  210.         menu();
  211.         system("cls");
  212.         break;
  213.     case 6:
  214.         printf("Podaj klucz: ");
  215.         scanf("%d", &key);
  216.         struct tree_node *result = find_node(root,key);
  217.         if(result){
  218.             printf("\nSzukana wartosc dla klucza %d wynosi %c", result->key, result->value);
  219.         }
  220.         menu();
  221.     case 7:
  222.         print_levelorder(root);
  223.         menu();
  224.     case 8:
  225.         print_graphic(root,0);
  226.         menu();
  227.     case 0:
  228.         return;
  229.     default:
  230.         puts("Niepoprawny wybor");
  231.         menu();
  232.         break;
  233.     }
  234. }
  235.  
  236. int main()
  237. {
  238.     int i;
  239.     char value;
  240.     int key;
  241.     srand(time(0));
  242.     for(i=0; i<10; i++)
  243.     {
  244.         key = rand()%100;
  245.         value = 'a' + rand() % ('z'-'a'+1);
  246.         add_node(&root, key, value);
  247.     }
  248.  
  249.     menu();
  250.  
  251.     return 0;
  252. }
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
 
Top