Please answer in C language(not cpp nor c#). void tree_init(), void tree_init_with_array(), double tree_key_find(), void tree_free() are done and correct, other are not done. You are going to implement the binary tree abstract data type using array implementation. Your program should not contain main(). #include #include #include #include #include

/* Binary tree data structure with array implementation */ /* The first element is stored in (key[0], value[0]) */ /* If key is unused, set key = INT_MAX, value = -2100 */ typedef struct _btree{ int *key; /* An array of keys for the nodes */ double *value; /* An array of values for the nodes */ int max_size; /* The max number of nodes */ } BTree;

/* Initialize the tree with a root #1 */ /* Create an empty BTree first */ /* The root (key, value) is stored at (key[0], value[0]) */ /* If key is unused, set key = INT_MAX, value = -2100 */

void tree_init(BTree **T, int key, double value, int max_size){ (*T) = (BTree*)malloc(sizeof(BTree)); (*T)->key = (int*)malloc(max_size*sizeof(int)); (*T)->value = (double*)malloc(max_size*sizeof(double)); (*T)->max_size = max_size; int i; for(i=0; ikey[i] = INT_MAX; (*T)->value[i] = -2100; } (*T)->key[0] = key; (*T)->value[0] = value; }

/* Initialize the tree with arrays #2 */ /* Create an empty BTree first */ /* n defines the number of (key,value) pairs of the array */ /* If key is unused, set key = INT_MAX, value = -2100 */

void tree_init_with_array(BTree **T, int *key, double *value, int n, int max_size) { tree_init(T, key[0], value[0], max_size); int i; for (i = 1; i < n; i++) { if (i >= max_size) { break; } (*T)->key[i] = key[i]; (*T)->value[i] = value[i]; } }

/* Initialize the empty tree with height of root #3 */ /* Based on the height, calculate the max_size */ /* Create an empty BTree with max_size */ /* If key is unused, set key = INT_MAX, value = -2100 */ void tree_init_with_height(BTree **T, int height){ // You code here }

/* Get the index of parent #4 */ /* Return the index of the parent */ /* Return -2100 if the parent index is invalid or unused */ int tree_parent(BTree *T, int child_index){ // You code here return 0; }

/* Get the index of left child #5 */ /* Return the index of the left child */ /* Return -2100 if the left child index is invalid or unused */ int tree_lchild(BTree *T, int parent_index) { // You code here return 0; }

/* Get the index of right child #6 */ /* Return the index of the right child */ /* Return -2100 if the right child index is invalid or unused */ int tree_rchild(BTree *T, int parent_index){ // You code here }

/* Insert or update a node #7 */ /* If key exists in T, update the value */ /* If key not in T, insert (key, double) as left child of parent_index*/ /* If the left child cannot be inserted, then do nothing */ /* If the left child is used by other key, then do nothing */ void tree_insert_lchild(BTree *T, int parent_index, int key, double value){ // You code here }

/* Insert or update a node #8 */ /* If key exists in T, update the value */ /* If key not in T, insert (key,double) as right child of parent_index*/ /* If the right child cannot be inserted, then do nothing */ /* If the right child is used by other key, then do nothing */ void tree_insert_rchild(BTree *T, int parent_index, int key, double value){ // You code here }

/* Find the value based on the key in the tree T or not #9 */ /* If key in T, return the corresponding value */ /* If key not in T, return -2100.00 */ double tree_key_find(BTree *T, int key) { for (int i = 0; i < T->max_size; i++) { if (T->key[i] == key) { return T->value[i]; } } return -2100.00; }

/* Find the value based on the index in the tree T or not #10 */ /* If index is used, return the corresponding value */ /* If index is unused or exceeding the max_size, return -2100.00 */ double tree_index_find(BTree *T, int index){ // You code here return 0.; }

/* Free the tree *T, if *T is not NULL #11 */ /* Assign NULL to *T after free */ void tree_free(BTree **T) { if (*T != NULL) { free((*T)->key); free((*T)->value); free(*T); *T = NULL; } }

/* The print function print the tree in an output string using postorder traversal #12 */ /* The number in the bracket is key, number after bracket is value */ /* If the tree looks like */ /* (0)1.7 */ /* | \ */ /* (1)1.2 (2)1.8 */ /* | | \ */ /* (4)0 (3)2 (6)5 */ /* Then, the output string is "(4)0.00 (1)1.20 (3)2.00 (6)5.00 (2)1.80 (0)1.70 " */ /* You can assume the number of nodes is not more than 100 */ char *tree_print(BTree *T){ char *output = malloc(sizeof(char)*3000); // You code here return output; } If you now sure how to print, here is the code in the another program that you can refer to:

/* The print function print the tree in an output string using preorder traversal #10 */ /* The number in the bracket is key, number after bracket is value */ /* If the tree looks like */ /* (0)17 */ /* | \ */ /* (1)12 (2)18 */ /* | | \ */ /* (4)0 (3)2 (8)5 */ /* Then, the output string is "(0)17 (1)12 (4)0 (2)18 (3)2 (8)5 " */ /* You can assume the number of nodes is not more than 100 */ void tree_print_recursive(Tree_CS *T, char *output){ if (T == NULL) return; sprintf(output, "%s(%d)%d \0", output, T->key, T->value); tree_print_recursive(T->first_child, output); tree_print_recursive(T->next_sibling, output); } char * tree_print(Tree_CS *T){ char *output = malloc(sizeof(char)*2500); memset(output, 0, sizeof(char)*2500); tree_print_recursive(T, output); return output; }