Guest User

Binary Tree Take 2

a guest
Jul 14th, 2018
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.65 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4.  
  5. struct node
  6. {
  7.   float data;
  8.   int count;
  9.   struct node *left;
  10.   struct node *right;
  11. };
  12.  
  13. struct node* newNode(float data)
  14. {
  15.   struct node* node = (struct node*)malloc(sizeof(struct node));
  16.  
  17.   node->data = data;
  18.   node->count = 1;
  19.  
  20.   node->left = NULL;
  21.   node->right = NULL;
  22.   return node;
  23. }
  24.  
  25. int addNode(struct node *root, struct node *add)
  26. {
  27.   struct node *currentNode = root;
  28.   while(1)
  29.   {
  30.     if(abs(add->data - currentNode->data) < 0.0000001)
  31.     {
  32.       currentNode->count += 1;
  33.       free(add);
  34.       add = NULL;
  35.       return 0;
  36.     }
  37.     else if(add->data > currentNode->data)
  38.     {
  39.       if(currentNode->right == NULL)
  40.       {
  41.         currentNode->right = add;
  42.         return 1;
  43.       }
  44.       else
  45.       {
  46.         currentNode = currentNode->right;
  47.         continue;
  48.       }
  49.     }
  50.     else if(add->data < currentNode->data)
  51.     {
  52.       if(currentNode->left == NULL)
  53.       {
  54.         currentNode->left = add;
  55.         return 1;
  56.       }
  57.       else
  58.       {
  59.         currentNode = currentNode->left;
  60.         continue;
  61.       }
  62.     }
  63.   }
  64. }
  65.  
  66. struct node* removeNode(struct node *root, float removeData)
  67. {
  68.   if(abs(root->data - removeData) < 0.000001)
  69.   {
  70.     root->count -= 1;
  71.     if(root->count < 1)
  72.     {
  73.       struct node *left = root->left;
  74.       struct node *right = root->right;
  75.       if(left == NULL && right != NULL)
  76.       {
  77.         free(root);
  78.         root = NULL;
  79.         return right;
  80.       }
  81.       else if(right == NULL && left != NULL)
  82.       {
  83.         free(root);
  84.         root = NULL;
  85.         return left;
  86.       }
  87.       else if(right != NULL && left != NULL)
  88.       {
  89.         free(root);
  90.         root = NULL;
  91.         addNode(left, right);
  92.         return left;
  93.       }
  94.       else
  95.       {
  96.         free(root);
  97.         root = NULL;
  98.         return NULL;
  99.       }
  100.     }
  101.     else
  102.     {
  103.       return root;
  104.     }
  105.   }
  106.   else if((root->data < removeData) && (root->right != NULL))
  107.   {
  108.     root->right = removeNode(root->right, removeData);
  109.     return root;
  110.   }
  111.   else if((root->data > removeData) && (root->left != NULL))
  112.   {
  113.     root->left = removeNode(root->left, removeData);
  114.     return root;
  115.   }
  116.   else
  117.   {
  118.     return root;
  119.   }
  120. }
  121.  
  122. void displayTree(struct node *root)
  123. {
  124.   if(root->left != NULL && root->right != NULL)
  125.   {
  126.     displayTree(root->left);
  127.     printf("Node Value: %f Node Count: %d\n", root->data, root->count);
  128.     displayTree(root->right);
  129.   }
  130.   else if(root->right != NULL)
  131.   {
  132.     printf("Node Value: %f Node Count: %d\n", root->data, root->count);
  133.     displayTree(root->right);
  134.   }
  135.   else if(root->left != NULL)
  136.   {
  137.     displayTree(root->left);
  138.     printf("Node Value: %f Node Count: %d\n", root->data, root->count);
  139.   }
  140.   else
  141.   {
  142.     printf("Node Value: %f Node Count: %d\n", root->data, root->count);
  143.   }
  144.   return;
  145. }
  146.  
  147. void deleteTree(struct node *root)
  148. {
  149.   if(root->left != NULL)
  150.   {
  151.     deleteTree(root->left);
  152.   }
  153.   if(root->right != NULL)
  154.   {
  155.     deleteTree(root->right);
  156.   }
  157.   free(root);
  158.   root = NULL;
  159.   return;
  160. }
  161.  
  162. int main(const int argc, const char *argv[])
  163. {
  164.  
  165.   srand(time(NULL));
  166.   float randMax = 1000;
  167.   struct node* root = newNode(0.0);
  168.   for(int i = -10000 ; i <= 10000 ; i++ )
  169.   {
  170.     addNode(root, newNode(((float)rand()/(float)(RAND_MAX)) * randMax - 500.0));
  171.   }
  172.  
  173.   int test = addNode(root, newNode(1.0));
  174.   displayTree(root);
  175.   root = removeNode(root, 1.0);
  176.  
  177.   printf("\n\n");
  178.  
  179.   for(int i = -5000; i <= 5000 ; i++)
  180.   {
  181.     root = removeNode(root, ((float)rand()/(float)(RAND_MAX)) * randMax - 500.0);
  182.   }
  183.  
  184.   displayTree(root);
  185.  
  186.   deleteTree(root);
  187.  
  188. }
Add Comment
Please, Sign In to add comment