-
-
Save PotatoPope/4b72b382d147a4fb49e5fce615038afb to your computer and use it in GitHub Desktop.
treei
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdlib.h> | |
#include "tree.h" | |
/* | |
*The type of trees. | |
*/ | |
//typedef struct treeiter treeiter_t; | |
/* | |
struct treeiter | |
{ | |
tree_t *tree; | |
};*/ | |
//Creates a new root for a new store_inorder | |
tree_t *tree_create(cmpfunc_t cmpfunc) { | |
tree_t *node = malloc(sizeof(tree_t)); | |
node -> data = NULL; | |
node -> height = 1; | |
node -> left = NULL; | |
node -> right = NULL; | |
node -> numitems = 2; | |
node ->cmpfunc = cmpfunc; | |
return node; | |
} | |
//Int compare function | |
int max(int a, int b) | |
{ | |
return a > b ? a : b; | |
} | |
//gets height of tree | |
int height(tree_t *node) | |
{ | |
return node ? node -> height : 0; | |
} | |
//updates height | |
void recalc(tree_t *node) | |
{ | |
node -> height = 1 + max(height(node -> left), height(node -> right)); | |
} | |
//rotates subtree right | |
tree_t *rotate_right(tree_t *node) | |
{ | |
tree_t *q = node -> left; | |
node -> left = q -> right; | |
q -> right = node; | |
recalc(node); | |
recalc(q); | |
return q; | |
} | |
//rotates subtree left | |
tree_t *rotate_left(tree_t *node) | |
{ | |
tree_t *q = node -> right; | |
node -> right = q -> left; | |
q -> left = node; | |
recalc(node); | |
recalc(q); | |
return q; | |
} | |
//balances the tree so that the max balance factor is no more than 1 | |
tree_t *balance(tree_t *node) | |
{ | |
recalc(node); | |
if ( height(node -> left) - height(node -> right) == 2 ) | |
{ | |
if ( height(node -> left -> right) > height(node -> left -> left) ) | |
node -> left = rotate_left(node -> left); | |
return rotate_right(node); | |
} | |
else if ( height(node -> right) - height(node -> left) == 2 ) | |
{ | |
if ( height(node -> right -> left) > height(node -> right -> right) ) | |
node -> right = rotate_right(node -> right); | |
return rotate_left(node); | |
} | |
return node; | |
} | |
//stores the traversal order of the tree in an array | |
void store_inorder(tree_t *tree, int inorder[], int *index_ptr) | |
{ | |
if (tree == NULL) | |
return; | |
int *p; | |
/*first recur on left child */ | |
store_inorder(tree->left, inorder, index_ptr); | |
p = tree->data; | |
inorder[*index_ptr] = *p; | |
(*index_ptr)++; // increase index for next entry | |
/*now recur on right child */ | |
store_inorder(tree->right, inorder, index_ptr); | |
} | |
/* | |
*Destroys the given tree. Subsequently accessing the tree | |
*will lead to undefined behavior. | |
*/ | |
void tree_destroy(tree_t *node) | |
{ | |
if ( !node ) | |
return; | |
//destroying the tree recursively | |
tree_destroy(node -> left); | |
tree_destroy(node -> right); | |
free(node); | |
} | |
/* | |
*Returns the size (cardinality) of the given tree. | |
*/ | |
int tree_size(tree_t *tree){ | |
return tree->numitems; | |
} | |
/* | |
*Adds the given element to the given tree. | |
*/ | |
tree_t *node_add(tree_t *node, void *data) { | |
if ( !node ) | |
return tree_create(data); | |
//conditionals to determine where to put the data | |
if ( data < node -> data ) | |
node -> left = node_add(node -> left, data); | |
else if ( data > node -> data ) | |
node -> right = node_add(node -> right, data); | |
else | |
node -> data = data; | |
node->numitems++; | |
return balance(node); | |
} | |
/* | |
*Returns 1 if the given element is contained in | |
*the given tree, 0 otherwise. | |
*/ | |
int tree_contains(tree_t *node, void *data){ | |
if( node == NULL ) | |
return 0; | |
if( data < node->data ) | |
return tree_contains(node->left, data ); | |
else if( data > node->data ) | |
return tree_contains(node->right, data ); | |
else | |
return 1; | |
} | |
//coverts a sorted array to a balanced binary tree | |
tree_t *sortedArrayToBST(int arr[], int start, int end) | |
{ | |
if (start > end) | |
return NULL; | |
cmpfunc_t cmpfunc; | |
//get the middle element and make it root | |
arr[0] = (start + end)/2; | |
tree_t *root = tree_create(cmpfunc); | |
root->data = arr; | |
//recursively construct the left subtree and make it | |
//left child of root | |
root->left = sortedArrayToBST(arr, start, arr[0]-1); | |
//recursively construct the right subtree and make it | |
//right child of root | |
root->right = sortedArrayToBST(arr, arr[0]+1, end); | |
return root; | |
} | |
//function to remove duplicate elements in an array | |
int remove_dup(int arr[], int m) | |
{ | |
int i, j, k; | |
for (i = 0; i < m; i++) { | |
for (j = i + 1; j < m;) { | |
if (arr[j] == arr[i]) { | |
for (k = j; k < m; k++) { | |
arr[k] = arr[k + 1]; | |
} | |
m--; | |
} else | |
j++; | |
} | |
} | |
} | |
//counts the number of intersections in two arrays | |
int *intersc_count(int arr1[], int arr2[], int m, int n) | |
{ | |
int i = 0, j = 0, k = 0, s = 0; | |
int *node; | |
node = &s; | |
// Traverse through both arrays | |
while (i < m && j < n) | |
{ | |
// nodeick the smaler element and nodeut it in mergedArr | |
if (arr1[i] < arr2[j]) | |
{ | |
i++; | |
} | |
else if (arr2[j] < arr1[i]) | |
{ | |
j++; | |
} | |
else if (arr1[i] == arr2[j]) | |
{ | |
printf("arr1[%d]\n", arr1[i]); | |
s++; | |
i++; | |
j++; | |
} | |
} | |
return node; | |
} | |
//find similiar elements in two arrays and puts them in a third array | |
int *intersc_init(int arr1[], int arr2[], int m, int n) | |
{ | |
int i = 0, j = 0, k = 0, s = 0; | |
int *size; | |
size = intersc_count(arr1, arr2, m, n); | |
printf("\nS: %d\n", *size); | |
int *arr3 = malloc(sizeof(*size)); | |
if(arr3 == NULL) | |
return NULL; | |
while (i < m && j < n) | |
{ | |
if (arr1[i] < arr2[j]) | |
{ | |
i++; | |
} | |
else if (arr2[j] < arr1[i]) | |
{ | |
j++; | |
} | |
else if (arr1[i] == arr2[j]) | |
{ | |
arr3[s] = arr1[i]; | |
s++; | |
i++; | |
j++; | |
} | |
} | |
return arr3; | |
} | |
//counts the number of differences in two arrays | |
int *difference_count(int arr1[], int arr2[], int m, int n) | |
{ | |
int i = 0, j = 0, s = 0; | |
int *p; | |
p = &s; | |
// Traverse through both arrays | |
for(int i = 0; i < m; i++) | |
{ | |
for(int j = 0; j < n; j++) | |
{ | |
if(arr1[i]!=arr2[j]) | |
{ | |
++j; | |
++i; | |
++*p; | |
} | |
} | |
} | |
printf("\ndiff_size: %d\n", *p); | |
return p; | |
} | |
//all elements of tree a that is not in tree b, are put in an array | |
int *difference_init(int arr1[], int arr2[], int m, int n) | |
{ | |
int i = 0, j = 0, k = 0, s = 0; | |
int *size; | |
size = difference_count(arr1, arr2, m, n); | |
printf("\ndiff_size: %d\n", *size); | |
int *arr3 = malloc(sizeof(*size)); | |
if(arr3 == NULL) | |
return 0; | |
for(int i = 0; i < m; i++) | |
{ | |
for(int j = 0; j < n; j++) | |
{ | |
if(arr1[i]!=arr2[j]) | |
{ | |
arr3[s] = arr1[i]; | |
++i; | |
++j; | |
++s; | |
} | |
} | |
} | |
return arr3; | |
} | |
//merges two arrays, combined with the duplicate delete | |
//the union of two arrays can be found | |
int *merge(int arr1[], int arr2[], int m, int n) | |
{ | |
//mergedArr[] is going to contain result | |
int *mergedArr = malloc(sizeof(int[m + n])); | |
if(mergedArr == NULL) | |
return NULL; | |
int i = 0, j = 0, k = 0; | |
//traverse through both arrays | |
while (i < m && j < n) | |
{ | |
//pick the smaler element and put it in mergedArr | |
if (arr1[i] < arr2[j]) | |
{ | |
mergedArr[k] = arr1[i]; | |
i++; | |
} | |
else | |
{ | |
mergedArr[k] = arr2[j]; | |
j++; | |
} | |
k++; | |
} | |
//if there are more elements in first array | |
while (i < m) | |
{ | |
mergedArr[k] = arr1[i]; | |
i++; k++; | |
} | |
//if there are more elements in second array | |
while (j < n) | |
{ | |
mergedArr[k] = arr2[j]; | |
j++; k++; | |
} | |
remove_dup(mergedArr, m+n); | |
return mergedArr; | |
} | |
/* | |
*Returns the union of the two given trees; the returned | |
*tree contains all elements that are contained in either | |
*a or b. | |
*/ | |
//converts trees to arrays, merges the arrays, then converts | |
//the merged array back into a tree | |
tree_t *tree_union(tree_t *a, tree_t *b, int m, int n) | |
{ | |
//store inorder traversal of first tree in arr1[] | |
int arr1[m]; | |
int i = 0; | |
store_inorder(a, arr1, &i); | |
//store inorder traversal of second tree in arr2[] | |
int arr2[n]; | |
int j = 0; | |
store_inorder(b, arr2, &j); | |
// Merge the two sorted array into one | |
int *mergedArr = merge(arr1, arr2, m, n); | |
//construct a tree from the merged array and return root of the tree | |
return sortedArrayToBST (mergedArr, 0, m+n-1); | |
} | |
/* | |
*Returns the intersection of the two given trees; the | |
*returned tree contains all elements that are contained | |
*in both a and b. | |
*/ | |
tree_t *tree_intersection(tree_t *a, tree_t *b, int m, int n) | |
{ | |
//store inorder traversal of first tree in arr1[] | |
int arr1[m]; | |
int i = 0; | |
store_inorder(a, arr1, &i); | |
//store inorder traversal of second tree in arr2[] | |
int arr2[n]; | |
int j = 0; | |
store_inorder(b, arr2, &j); | |
//calls the intersection function | |
int *arr3 = intersc_init(arr1, arr2, m, n); | |
//gets the size of the intersection count, so memory isn't wasted | |
int *size; | |
size = intersc_count(arr1, arr2, m, n); | |
return sortedArrayToBST (arr3, 0, *size-1); | |
} | |
/* | |
*Returns the tree difference of the two given trees; the | |
*returned tree contains all elements that are contained | |
*in a and not in b. | |
*/ | |
tree_t *tree_difference(tree_t *a, tree_t *b, int m, int n) | |
{ | |
//store inorder traversal of first tree in arr1[] | |
int arr1[m]; | |
int i = 0; | |
store_inorder(a, arr1, &i); | |
//store inorder traversal of second tree in arr2[] | |
int arr2[n]; | |
int j = 0; | |
store_inorder(b, arr2, &j); | |
int *arr3 = difference_init(arr1, arr2, m, n); | |
int *size; | |
size = difference_count(arr1, arr2, m, n); | |
return sortedArrayToBST (arr3, 0, *size-1); | |
} | |
/* | |
*Returns a copy of the given tree. | |
*/ | |
//copies the contents of one tree to another tree | |
tree_t *tree_copy(tree_t *tree, int m, int n) | |
{ | |
int arr1[m], arr2[m]; | |
int b = 0, i; | |
store_inorder(tree, arr1, &b); | |
for (i = 0; i < m; i++) | |
arr2[i] = arr1[i]; | |
return sortedArrayToBST (arr2, 0, m-1); | |
} | |
void go_left(tree_t *root) | |
{ | |
if(!root) | |
return; | |
go_left(root->left); | |
} | |
void go_right(tree_t *root) | |
{ | |
if(!root) | |
return; | |
go_left(root->right); | |
} | |
void preorder(tree_t *root){ | |
if(!root) | |
return; | |
printf("%d\t",root->data); | |
preorder(root->left); | |
preorder(root->right); | |
} | |
//function for printing the in-order of tree | |
void inorder_print(tree_t *root){ | |
if(!root) | |
return; | |
inorder_print(root->left); | |
printf("%d\t",root->data); | |
inorder_print(root->right); | |
} | |
void inorder(tree_t *root){ | |
if(!root) | |
return; | |
inorder(root->left); | |
inorder(root->right); | |
} | |
void postorder(tree_t *root) | |
{ | |
if(root == NULL) | |
return; | |
else { | |
postorder(root ->left); | |
postorder(root ->right); | |
printf("%d\t",root ->data); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment