Advertisement
Guest User

Untitled

a guest
Dec 8th, 2016
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 6.69 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include "BSTree.h"
  4. #include <assert.h>
  5. #include <math.h>
  6. // Statiska hj‰lpfunktioner /////////////////////////////////////////////////////////////
  7.  
  8. static void writeElement(const BSTree tree, int sortedArray[], int *index)
  9. {
  10.     if(tree !=0)
  11.     {
  12.         writeElement(tree->left, sortedArray, index);
  13.         sortedArray[*index] = tree->data;
  14.         (*index)++;
  15.         writeElement(tree->right, sortedArray, index);
  16.     }
  17.    
  18.    
  19. }
  20.  
  21. static BSTree* findMin(BSTree *tree)
  22. {
  23.     if ((*tree)->left !=0)
  24.     {
  25.         return findMin(&(*tree)->left); // minsta värdet i högra trädet
  26.     }
  27.    
  28.     return tree;
  29. }
  30.  
  31.  
  32.  
  33.  
  34. // Skapar en tr‰dnod med det givna datat samt allokerar minne fˆr det
  35. static struct treeNode* createNode(int data)
  36. {
  37.     struct treeNode* newNode;
  38.     newNode = (struct treeNode*) malloc(sizeof(struct treeNode));
  39.    
  40.    
  41.     newNode->data = data;
  42.     newNode->left = NULL;
  43.     newNode->right = NULL;
  44.    
  45.    
  46.     return newNode; // Ers‰tt med r‰tt returv‰rde
  47. }
  48.  
  49.  
  50.  
  51. // Returnerar en dynamiskt allokerad array som innehÂller trädets data sorterat
  52. static int* writeSortedToArray(const BSTree tree)
  53. {
  54.     int *sortedArray = malloc(sizeof(int)*numberOfNodes(tree));
  55.     int index =0;
  56.    
  57.     writeElement(tree, sortedArray, &index);
  58.    
  59.     return sortedArray;
  60.    
  61. }
  62.  
  63.  
  64.  
  65. // Bygger upp ett sorterat balancerat tr‰d frÂn en sorterad array
  66. void buildTreeSortedFromArray(BSTree* tree, const int arr[], int size)
  67. {
  68.     int start = arr[0];
  69.     int end = arr[size -1];
  70.     int mid = (start + end)/2;
  71.    
  72.     if(start > end)
  73.         return;
  74.    
  75.     insertSorted(&(*tree), mid);
  76.    
  77.     // rekursivt konstuktera ett vänsterbarn och göra det vänsterbarn av roten
  78.     if((*tree)->data < mid)
  79.     buildTreeSortedFromArray(&(*tree)->left, &start, mid -1);
  80.    
  81.    
  82.    
  83.      // rekursivt konstuktera ett högerbarn och göra det högerbarn av roten
  84.     else if((*tree)->data > mid)
  85.     buildTreeSortedFromArray(&(*tree)->right, &start, mid +1);
  86.    
  87.    
  88.    
  89. }
  90.  
  91. // Implementation av tr‰det ////////////////////////////////////////////////////////
  92.  
  93. BSTree emptyTree(void)
  94. {
  95.     return NULL; // Denna funktion ‰r klar
  96. }
  97.  
  98. int isEmpty(const BSTree tree)
  99. {
  100.     if(tree != NULL)
  101.         return 0;
  102.     else
  103.         return 1; // Ers‰tt med r‰tt returv‰rde
  104. }
  105.  
  106. void insertSorted(BSTree* tree, int data)
  107. {
  108.     if (*tree == NULL)
  109.     {
  110.         *tree = createNode(data);
  111.         return;
  112.     }
  113.     else
  114.     {
  115.         if((*tree)->data > data)
  116.         {
  117.             insertSorted(&(*tree)->left, data);
  118.         }
  119.         else if((*tree)->data < data)
  120.         {
  121.             insertSorted(&(*tree)->right, data);
  122.         }
  123.     }
  124.    
  125.    
  126.     //assert(isEmpty(*tree)==0);              // post condition: trädet inte är tomt
  127.    
  128.    
  129. }
  130.  
  131. void printPreorder(const BSTree tree)
  132. {
  133.     if(tree != NULL)
  134.     {
  135.         printf("%d ", tree->data);
  136.         printPreorder(tree->left);
  137.         printPreorder(tree->right);
  138.     }
  139.  
  140.    
  141. }
  142.  
  143. void printInorder(const BSTree tree)
  144. {
  145.     if(tree != NULL)
  146.     {
  147.         printInorder(tree->left);
  148.         printf("%d", tree->data);
  149.         printInorder(tree->right);
  150.     }
  151. }
  152.  
  153. void printPostorder(const BSTree tree)
  154. {
  155.     printPostorder(tree->left);
  156.     printPostorder(tree->right);
  157.     printf("%d ", tree->data);
  158.    
  159.    
  160. }
  161.  
  162. int find(const BSTree tree, int data)
  163. {
  164.    
  165.     if(tree == NULL)
  166.         return 0;
  167.    
  168.         else if(tree->data == data)
  169.             return 1;
  170.         else if(tree->data > data)
  171.              return find(tree->left, data);
  172.         else
  173.              return find(tree->right, data);
  174.  
  175. }
  176.  
  177.  
  178. void removeElement(BSTree* tree, int data)
  179. {
  180.    
  181.     // basfall
  182.     if((*tree) == NULL)
  183.     {
  184.         printf("Finns inget att ta bort");
  185.         return;
  186.     }
  187.     else
  188.     {
  189.     // om datat finns i det vänsta sub-tree
  190.     if (data < (*tree)->data)
  191.     {
  192.         removeElement(&(*tree)->left, data);
  193.     }
  194.    
  195.     // om datat finns i det högra sub-tree
  196.     else if (data > (*tree)->data)
  197.     {
  198.         removeElement(&(*tree)->right, data);
  199.     }
  200.    
  201.     else
  202.     {
  203.        
  204.         if((*tree)->left && (*tree)->right)
  205.         {
  206.             BSTree* temp = findMin(&(*tree)->right); // hitat minsta värdet av höger sub-träd
  207.             (*tree)->data = (*temp)->data;
  208.             removeElement(temp, (*temp)->data);
  209.         }
  210.         else if((*tree)->left != NULL)
  211.         {
  212.             BSTree *tmp = tree;
  213.             *tree = (*tree)->left;
  214.             free (*tmp);
  215.         }
  216.         else if((*tree)->right != NULL)
  217.         {
  218.             BSTree *tmp = tree;
  219.             *tree = (*tree)->right;
  220.             free (*tmp);
  221.         }
  222.         else
  223.         {
  224.             BSTree* tmp = tree;
  225.             *tree = NULL;
  226.             free(*tmp);
  227.         }
  228.     }
  229.     }
  230. }
  231.  
  232. int numberOfNodes(const BSTree tree)
  233. {
  234.     int count = 1;
  235.    
  236.     if(tree == NULL)
  237.     {
  238.         printf("tradet ar tomt");
  239.         count = 0;
  240.         return count;
  241.     }
  242.    
  243.     if(tree->left != NULL)
  244.     {
  245.         count +=numberOfNodes(tree->left);
  246.     }
  247.    
  248.     if(tree->right !=NULL)
  249.     {
  250.         count +=numberOfNodes(tree->right);
  251.     }
  252.    
  253.    
  254.    
  255.     return count;
  256. }
  257.  
  258. int depth(const BSTree tree)            //faktiska djupet
  259. {
  260.     int x = 1, y = 1;
  261.     if(tree == NULL)
  262.         return 0;
  263.     x += depth(tree->left);
  264.     y += depth(tree->right);
  265.     if(x >= y)
  266.         return x;
  267.     else
  268.         return y;
  269. }
  270.  
  271. int minDepth(const BSTree tree)         // teoretiska djupet
  272. {
  273.     int n = numberOfNodes(tree);
  274.     int x = ceil(log2(n+1));
  275.     return x;
  276. }
  277.  
  278. void balanceTree(BSTree* tree)
  279. {
  280.     int sortedArray;
  281.     int size = numberOfNodes(*tree);
  282.     sortedArray = *writeSortedToArray(*tree);
  283.     freeTree(tree);
  284.     buildTreeSortedFromArray(tree ,&sortedArray, size);
  285.     free(*tree);
  286.    
  287.     assert(size == numberOfNodes(*tree));
  288.     assert(depth(*tree)==minDepth(*tree));
  289.    
  290.    
  291.    
  292.    
  293.     // Fˆrslag p algoritm:
  294.     // - ÷verfˆr tr‰det till en dynamiskt allokerad array med writeSortedToArray()
  295.     // - tˆm tr‰det med freeTree()
  296.     // - bygg upp tr‰det rekursivt frÂn arrayen med buildTreeSortedFromArray()
  297.     // - frigˆr minne fˆr den dynamiskt allokerade arrayen
  298.  
  299.  
  300.     // Post-conditions:
  301.     // - tree har lika mÂnga noder som tidigare
  302.     // - djupet fˆr tr‰det ‰r samma som minimumdjupet fˆr tr‰det
  303. }
  304.  
  305. void freeTree(BSTree* tree)
  306. {
  307.     if(*tree !=0)
  308.     {
  309.         freeTree(&(*tree)->right);
  310.         freeTree(&(*tree)->left);
  311.         free(*tree);
  312.         *tree = 0;
  313.    
  314.     }
  315.     assert(isEmpty(*tree)==1);
  316.     // Post-condition: tr‰det ‰r tomt
  317. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement