Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h>
- #include <stdio.h>
- #include "BSTree.h"
- #include <assert.h>
- #include <math.h>
- // Statiska hj‰lpfunktioner /////////////////////////////////////////////////////////////
- static void writeElement(const BSTree tree, int sortedArray[], int *index)
- {
- if(tree !=0)
- {
- writeElement(tree->left, sortedArray, index);
- sortedArray[*index] = tree->data;
- (*index)++;
- writeElement(tree->right, sortedArray, index);
- }
- }
- static BSTree* findMin(BSTree *tree)
- {
- if ((*tree)->left !=0)
- {
- return findMin(&(*tree)->left); // minsta värdet i högra trädet
- }
- return tree;
- }
- // Skapar en tr‰dnod med det givna datat samt allokerar minne fˆr det
- static struct treeNode* createNode(int data)
- {
- struct treeNode* newNode;
- newNode = (struct treeNode*) malloc(sizeof(struct treeNode));
- newNode->data = data;
- newNode->left = NULL;
- newNode->right = NULL;
- return newNode; // Ers‰tt med r‰tt returv‰rde
- }
- // Returnerar en dynamiskt allokerad array som innehÂller trädets data sorterat
- static int* writeSortedToArray(const BSTree tree)
- {
- int *sortedArray = malloc(sizeof(int)*numberOfNodes(tree));
- int index =0;
- writeElement(tree, sortedArray, &index);
- return sortedArray;
- }
- // Bygger upp ett sorterat balancerat tr‰d frÂn en sorterad array
- void buildTreeSortedFromArray(BSTree* tree, const int arr[], int size)
- {
- int start = arr[0];
- int end = arr[size -1];
- int mid = (start + end)/2;
- if(start > end)
- return;
- insertSorted(&(*tree), mid);
- // rekursivt konstuktera ett vänsterbarn och göra det vänsterbarn av roten
- if((*tree)->data < mid)
- buildTreeSortedFromArray(&(*tree)->left, &start, mid -1);
- // rekursivt konstuktera ett högerbarn och göra det högerbarn av roten
- else if((*tree)->data > mid)
- buildTreeSortedFromArray(&(*tree)->right, &start, mid +1);
- }
- // Implementation av tr‰det ////////////////////////////////////////////////////////
- BSTree emptyTree(void)
- {
- return NULL; // Denna funktion ‰r klar
- }
- int isEmpty(const BSTree tree)
- {
- if(tree != NULL)
- return 0;
- else
- return 1; // Ers‰tt med r‰tt returv‰rde
- }
- void insertSorted(BSTree* tree, int data)
- {
- if (*tree == NULL)
- {
- *tree = createNode(data);
- return;
- }
- else
- {
- if((*tree)->data > data)
- {
- insertSorted(&(*tree)->left, data);
- }
- else if((*tree)->data < data)
- {
- insertSorted(&(*tree)->right, data);
- }
- }
- //assert(isEmpty(*tree)==0); // post condition: trädet inte är tomt
- }
- void printPreorder(const BSTree tree)
- {
- if(tree != NULL)
- {
- printf("%d ", tree->data);
- printPreorder(tree->left);
- printPreorder(tree->right);
- }
- }
- void printInorder(const BSTree tree)
- {
- if(tree != NULL)
- {
- printInorder(tree->left);
- printf("%d", tree->data);
- printInorder(tree->right);
- }
- }
- void printPostorder(const BSTree tree)
- {
- printPostorder(tree->left);
- printPostorder(tree->right);
- printf("%d ", tree->data);
- }
- int find(const BSTree tree, int data)
- {
- if(tree == NULL)
- return 0;
- else if(tree->data == data)
- return 1;
- else if(tree->data > data)
- return find(tree->left, data);
- else
- return find(tree->right, data);
- }
- void removeElement(BSTree* tree, int data)
- {
- // basfall
- if((*tree) == NULL)
- {
- printf("Finns inget att ta bort");
- return;
- }
- else
- {
- // om datat finns i det vänsta sub-tree
- if (data < (*tree)->data)
- {
- removeElement(&(*tree)->left, data);
- }
- // om datat finns i det högra sub-tree
- else if (data > (*tree)->data)
- {
- removeElement(&(*tree)->right, data);
- }
- else
- {
- if((*tree)->left && (*tree)->right)
- {
- BSTree* temp = findMin(&(*tree)->right); // hitat minsta värdet av höger sub-träd
- (*tree)->data = (*temp)->data;
- removeElement(temp, (*temp)->data);
- }
- else if((*tree)->left != NULL)
- {
- BSTree *tmp = tree;
- *tree = (*tree)->left;
- free (*tmp);
- }
- else if((*tree)->right != NULL)
- {
- BSTree *tmp = tree;
- *tree = (*tree)->right;
- free (*tmp);
- }
- else
- {
- BSTree* tmp = tree;
- *tree = NULL;
- free(*tmp);
- }
- }
- }
- }
- int numberOfNodes(const BSTree tree)
- {
- int count = 1;
- if(tree == NULL)
- {
- printf("tradet ar tomt");
- count = 0;
- return count;
- }
- if(tree->left != NULL)
- {
- count +=numberOfNodes(tree->left);
- }
- if(tree->right !=NULL)
- {
- count +=numberOfNodes(tree->right);
- }
- return count;
- }
- int depth(const BSTree tree) //faktiska djupet
- {
- int x = 1, y = 1;
- if(tree == NULL)
- return 0;
- x += depth(tree->left);
- y += depth(tree->right);
- if(x >= y)
- return x;
- else
- return y;
- }
- int minDepth(const BSTree tree) // teoretiska djupet
- {
- int n = numberOfNodes(tree);
- int x = ceil(log2(n+1));
- return x;
- }
- void balanceTree(BSTree* tree)
- {
- int sortedArray;
- int size = numberOfNodes(*tree);
- sortedArray = *writeSortedToArray(*tree);
- freeTree(tree);
- buildTreeSortedFromArray(tree ,&sortedArray, size);
- free(*tree);
- assert(size == numberOfNodes(*tree));
- assert(depth(*tree)==minDepth(*tree));
- // Fˆrslag p algoritm:
- // - ÷verfˆr tr‰det till en dynamiskt allokerad array med writeSortedToArray()
- // - tˆm tr‰det med freeTree()
- // - bygg upp tr‰det rekursivt frÂn arrayen med buildTreeSortedFromArray()
- // - frigˆr minne fˆr den dynamiskt allokerade arrayen
- // Post-conditions:
- // - tree har lika mÂnga noder som tidigare
- // - djupet fˆr tr‰det ‰r samma som minimumdjupet fˆr tr‰det
- }
- void freeTree(BSTree* tree)
- {
- if(*tree !=0)
- {
- freeTree(&(*tree)->right);
- freeTree(&(*tree)->left);
- free(*tree);
- *tree = 0;
- }
- assert(isEmpty(*tree)==1);
- // Post-condition: tr‰det ‰r tomt
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement