Question
Please, read carefully. Thank you.
Take the height-balanced tree code, and add a function
int depth distribution(tree node t *tree);
which prints the total number of leaves, and a table giving the number of leaves at
different depths. The depth of a tree node is the distance from the root, so the root
has depth 0. Send only the code of your function, do not include my height-balanced
tree code. The programming language is C or C++; test your code before submission
using the gcc or g++ compiler.
Please use the code below, dont make any changes in the code. I need to add functions to that code to get this output:
depth: 13 14 15 16 17 18 19 20 21 22 23
count: 9 168 1798 11113 36291 67735 79899 62443 31144 8576 824
Explanation / Answer
#define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = free_list -> left; } else { if( currentblock == NULL || size_left == 0) { currentblock = (tree_node_t *) malloc( BLOCKSIZE * sizeof(tree_node_t) ); size_left = BLOCKSIZE; } tmp = currentblock++; size_left -= 1; } return( tmp ); } void return_node(tree_node_t *node) { node->left = free_list; free_list = node; } tree_node_t *create_tree(void) { tree_node_t *tmp_node; tmp_node = get_node(); tmp_node->left = NULL; return( tmp_node ); } void left_rotation(tree_node_t *n) { tree_node_t *tmp_node; key_t tmp_key; tmp_node = n->left; tmp_key = n->key; n->left = n->right; n->key = n->right->key; n->right = n->left->right; n->left->right = n->left->left; n->left->left = tmp_node; n->left->key = tmp_key; } void right_rotation(tree_node_t *n) { tree_node_t *tmp_node; key_t tmp_key; tmp_node = n->right; tmp_key = n->key; n->right = n->left; n->key = n->left->key; } } else if ( tmp_node->left->height - tmp_node->right->height == -2 ) { if( tmp_node->right->right->height - tmp_node->left->height == 1 ) { left_rotation( tmp_node ); tmp_node->left->height = tmp_node->left->right->height + 1; tmp_node->height = tmp_node->left->height + 1; } else { right_rotation( tmp_node->right ); left_rotation( tmp_node ); tmp_height = tmp_node->right->right->height; tmp_node->left->height = tmp_height + 1; tmp_node->right->height = tmp_height + 1; tmp_node->height = tmp_height + 2; } } else /* update height even if there was no rotation */ { if( tmp_node->left->height > tmp_node->right->height ) tmp_node->height = tmp_node->left->height + 1; else tmp_node->height = tmp_node->right->height + 1; } if( tmp_node->height == old_height ) finished = 1; } } return( 0 ); } void depth_distribution(tree_node_t *t); int main() { tree_node_t *searchtree; char nextop; int i; int * insobj; searchtree = create_tree(); insobj = (int *) malloc(sizeof(int)); *insobj = 654321; printf("Made Tree: Height-Balanced Tree "); for(i=0; i