SHARE
TWEET

Untitled

a guest Dec 9th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* TODO:
  2. 1) Width
  3. 2) WidthTraversal
  4. */
  5.  
  6. #include <stdio.h>
  7. #include <mm_malloc.h>
  8. #include <stdbool.h>
  9.  
  10. typedef struct _node Node;
  11.  
  12. struct _node {
  13.     int value;
  14.     Node* left;
  15.     Node* right;
  16. };
  17.  
  18. size_t sizeOfTree = 0;
  19. size_t maxHeight = 0;
  20.  
  21. void findHeight(Node* root, size_t curHeight) {
  22.     if (root -> left) {
  23.         findHeight(root -> left, curHeight + 1);
  24.     }
  25.     if (root -> right) {
  26.         findHeight(root -> right, curHeight + 1);
  27.     }
  28.     if (curHeight > maxHeight) {
  29.         maxHeight = curHeight;
  30.     }
  31. }
  32.  
  33. void infixTraversal(Node *root) {
  34.     if (root -> left) {
  35.         infixTraversal(root->left);
  36.     }
  37.     printf("%d ", root -> value);
  38.     if (root -> right) {
  39.         infixTraversal(root->right);
  40.     }
  41. }
  42. void prefixTraversal(Node *root) {
  43.     printf("%d ", root -> value);
  44.     if (root -> left) {
  45.         prefixTraversal(root->left);
  46.     }
  47.     if (root -> right) {
  48.         prefixTraversal(root->right);
  49.     }
  50. }
  51. void postfixTraversal(Node *root) {
  52.     if (root -> left) {
  53.         postfixTraversal(root->left);
  54.     }
  55.     if (root -> right) {
  56.         postfixTraversal(root->right);
  57.     }
  58.     printf("%d ", root -> value);
  59. }
  60.  
  61. bool exist(int value, Node* root) {
  62.     if (!root) {
  63.         return false;
  64.     } else if (value == root -> value) {
  65.         return true;
  66.     }
  67.  
  68.     return exist(value, root -> left) || exist(value, root -> right);
  69. }
  70.  
  71. void insert(int value, Node* root) {
  72.     if (exist(value, root)) {
  73.         return;
  74.     }
  75.  
  76.     if (sizeOfTree == 0) {
  77.         root -> value = value;
  78.         sizeOfTree++;
  79.         return;
  80.     }
  81.  
  82.     if (value < root -> value) {
  83.         if (root -> left) {
  84.             insert(value, root -> left);
  85.         } else {
  86.             root -> left = calloc(1, sizeof(Node));
  87.             root -> left -> value = value;
  88.             sizeOfTree++;
  89.             return;
  90.         }
  91.     } else {
  92.         if (root -> right) {
  93.             insert(value, root -> right);
  94.         } else {
  95.             root -> right = calloc(1, sizeof(Node));
  96.             root -> right -> value = value;
  97.             sizeOfTree++;
  98.             return;
  99.         }
  100.     }
  101. }
  102.  
  103. void run() {
  104.     Node* root = calloc(1, sizeof(Node));
  105.     int element;
  106.     FILE* fileIn = fopen("in.txt", "r");
  107.     while (!feof(fileIn)) {
  108.         if (fscanf(fileIn, "%d", &element) != 0) {
  109.             insert(element, root);
  110.         }
  111.     }
  112.     findHeight(root, 0);
  113.     printf("%zu\n", maxHeight);
  114.     infixTraversal(root);
  115.     printf("\n");
  116.     prefixTraversal(root);
  117.     printf("\n");
  118.     postfixTraversal(root);
  119. }
  120.  
  121. int main() {
  122.     run();
  123.     return 0;
  124. }
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