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

Use this code, do not make any changes in this code, just add the functions to finish the program. Thank you.

#include

#include

#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;

n->left = n->right->left;

n->right->left = n->right->right;

n->right->right = tmp_node;

n->right->key = tmp_key;

}

object_t *find(tree_node_t *tree, key_t query_key)

{ tree_node_t *tmp_node;

if( tree->left == NULL )

return(NULL);

else

{ tmp_node = tree;

while( tmp_node->right != NULL )

{ if( query_key < tmp_node->key )

tmp_node = tmp_node->left;

else

tmp_node = tmp_node->right;

}

if( tmp_node->key == query_key )

return( (object_t *) tmp_node->left );

else

return( NULL );

}

}

int insert(tree_node_t *tree, key_t new_key, object_t *new_object)

{ tree_node_t *tmp_node;

int finished;

if( tree->left == NULL )

{ tree->left = (tree_node_t *) new_object;

tree->key = new_key;

tree->height = 0;

tree->right = NULL;

}

else

{ tree_node_t * path_stack[100]; int path_st_p = 0;

tmp_node = tree;

while( tmp_node->right != NULL )

{ path_stack[path_st_p++] = tmp_node;

if( new_key < tmp_node->key )

tmp_node = tmp_node->left;

else

tmp_node = tmp_node->right;

}

/* found the candidate leaf. Test whether key distinct */

if( tmp_node->key == new_key )

return( -1 );

/* key is distinct, now perform the insert */

{ tree_node_t *old_leaf, *new_leaf;

old_leaf = get_node();

old_leaf->left = tmp_node->left;

old_leaf->key = tmp_node->key;

old_leaf->right = NULL;

old_leaf->height = 0;

new_leaf = get_node();

new_leaf->left = (tree_node_t *) new_object;

new_leaf->key = new_key;

new_leaf->right = NULL;

new_leaf->height = 0;

if( tmp_node->key < new_key )

{ tmp_node->left = old_leaf;

tmp_node->right = new_leaf;

tmp_node->key = new_key;

}

else

{ tmp_node->left = new_leaf;

tmp_node->right = old_leaf;

}

tmp_node->height = 1;

}

/* rebalance */

finished = 0;

while( path_st_p > 0 && !finished )

{ int tmp_height, old_height;

tmp_node = path_stack[--path_st_p];

old_height= tmp_node->height;

if( tmp_node->left->height -

tmp_node->right->height == 2 )

{ if( tmp_node->left->left->height -

tmp_node->right->height == 1 )

{ right_rotation( tmp_node );

tmp_node->right->height =

tmp_node->right->left->height + 1;

tmp_node->height = tmp_node->right->height + 1;

}

else

{ left_rotation( tmp_node->left );

right_rotation( tmp_node );

tmp_height = tmp_node->left->left->height;

tmp_node->left->height = tmp_height + 1;

tmp_node->right->height = tmp_height + 1;

tmp_node->height = tmp_height + 2;

}

}

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<100000; i++)

{ insert(searchtree, i, insobj);

insert(searchtree, i+200000, insobj);

insert(searchtree, 400000-i, insobj);

}

depth_distribution(searchtree);

return(0);

}