Hi everyone,

I've been assigned an implementation of a BST using arrays & pointers. This makes the implementation a lot different than what I've seen from examples online. The header files have been provided to us, listed below:

data.h

Code:typedef struct {char *key; int data;} Node; void print_node(Node node); char *key_dup(char *key);bst.h

I've inserted a few helper functions, but here's my current bst.c:Code:#include "data.h" typedef struct {Node *tree_nodes; unsigned char *is_free; int size;} BStree_struct; typedef BStree_struct* BStree; BStree bstree_ini(int size); void bstree_insert(BStree bst, char *key, int data); void bstree_traversal(BStree bst); void bstree_free(BStree bst);

bst.c

Here's a sample main program of 9 insertions, then a traversal & free:Code:#include <stdio.h> #include <stdlib.h> #include <string.h> #include "bst.h" // Input: ’size’: size of an array // Output: a pointer of type BStree, i.e. a pointer to an allocated memory of BStree_struct type // Effect: dynamically allocate memory of type BStree_struct // allocate memory for a Node array of size+1 for member tree_nodes // allocate memory for an unsigned char array of size+1 for member is_free // set all entries of is_free to 1 // set member size to ’size’; BStree bstree_ini(int size) { BStree bst; bst = (BStree_struct*)(malloc(sizeof(BStree_struct))); bst->tree_nodes = (Node*)(malloc((size+1)*sizeof(Node))); bst->is_free = (unsigned char*)(malloc((size + 1) * sizeof(unsigned char))); int i; for (i = 0; i<= size; i++){ bst->is_free[i] = '1'; } bst->size = size; return bst; } // Input: ’bst’: a binary search tree // ’key’: a string // ’data’: an integer // Effect: ’data’ with ’key’ is inserted into ’bst’; if ’key’ is already in ’bst’, do nothing void bstree_insert(BStree bst, char *key, int data) { int value; int index = 1; if (bst->is_free[index] == '1') { bst->tree_nodes[index].key = key_dup(key); bst->tree_nodes[index].data = data; bst->is_free[index] = '0'; } else { value = strcmp(key, bst->tree_nodes[index].key); insert_recursion(bst, key, data, value, index); } } // Input: ’bst’: a binary search tree // Effect: print all the nodes in bst using in order traversal void bstree_traversal(BStree bst) { int index; index = 1; traversal_recursion(bst, index); } // Input: ’bst’: a binary search tree // Effect: all memory used by bst are freed void bstree_free(BStree bst) { free(bst->tree_nodes); free(bst->is_free); free(bst); } // Input: 'bst', 'key', 'data', 'value': the value from strcmp, determines if , 'index': the current index of is_free & tree_nodes // Effect: recursively search for an array for the first appropriate branch for the given key, using the strcmp value from bstree_insert void insert_recursion(BStree bst, char *key, int data, int value, int index) { if(value == 0){ // if the key already exists printf("Sorry, this key already exists."); return; } else if(value < 0){ // if the key is less than the current node if(bst->is_free[leftNode(index)] == '1') // if the left node is free, append the node to it { bst->tree_nodes[leftNode(index)].key = key_dup(key); bst->tree_nodes[leftNode(index)].data = data; bst->is_free[leftNode(index)] = '0'; } else // else if the node is full, recall the function { value = strcmp(key, bst->tree_nodes[leftNode(index)].key); insert_recursion(bst, key, data, value, index + 1); } } else if(value > 0){ // if the key is greater than the current node if(bst->is_free[rightNode(index)] == '1') // if the right node is free, append the node to it { bst->tree_nodes[rightNode(index)].key = key_dup(key); bst->tree_nodes[rightNode(index)].data = data; bst->is_free[rightNode(index)] = '0'; } else // else if the node is full, recall the function { value = strcmp(key, bst->tree_nodes[rightNode(index)].key); insert_recursion(bst, key, data, value, index + 1); } } } // Input: bst, index // Effect: print_node for each node inorder traversal void traversal_recursion(BStree bst, int index) { if(bst->is_free[index] == '0') // if index is full { traversal_recursion(bst, leftNode(index)); // traverse the left nodes print_node(bst->tree_nodes[index]); // print the node traversal_recursion(bst, rightNode(index)); // traverse the right nodes } } // Input: index of the node // Effect: returns the index of the node left of index int leftNode(int index){ return (index * 2); } // Input: index of the node // Effect: returns the index of the node right of index int rightNode(int index){ return ((index * 2) + 1); }

However, here's the comparison between the expected display and what my program actually outputs (respectively):Code:int main(void) { BStree bst; bst = bstree_ini(1000); 4 bstree_insert(bst, "Once", 1); bstree_insert(bst, "Upon", 22); bstree_insert(bst, "a", 3); bstree_insert(bst, "Time", 4); bstree_insert(bst, "is", 5); bstree_insert(bst, "filmed", 6); bstree_insert(bst, "in", 7); bstree_insert(bst, "Vancouver", 8); bstree_insert(bst, "!", 99); bstree_traversal(bst); bstree_free(bst); }

! 99 | filmed 6

Once 1 | Time 4

Time 4 | ! 99

Upon 22 | a 3

Vancouver 8 | in 7

a 3 | Once 1

filmed 6 | Vancouver 8

in 7 | Upon 22

is 5 | is 5

My program seems to be failing to insert correctly. The only left node should be !, since ASCII values have '!' being the only one less than Once. My program for some reason is inserting 'filmed' & 'Time' keys to the to the left node of '!' however, and I haven't been able to figure out why.

Sorry if the code is excessive, and for my formatting in advance. Please let me know if there's anything I can do to make it easier to read.

Thanks!