Take the height-balanced tree code, and add a function int depth.distribution (t
ID: 3597646 • Letter: T
Question
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 gt+ compiler. Please remove all dead code; try to program as clearly as possible, since I try to read it. Do not copy code from another student or from the web; this is an easy project, and must be all your own workExplanation / Answer
int depth_distribution(tree_node_t *tree)
{
int no_of_leaf = getLevelOrder(tree);
printf("No Of leaf Nodes : %d ", no_of_leaf);
return no_of_leaf;
}
int getLevelOrder(tree_node_t *tree)
{
// get the height of the tree
int height = getHeight(tree);
int i, count = 0;
// go through the tree level order
for (i = 1 ; i <= height; i++)
{
printf("Depth %d : ", i - 1);
// print the level i
getLevel(tree, i, &count);
printf(" ");
}
return count;
}
// traverse the tree in level order
void getLevel(tree_node_t *tree, int current_level, int *count)
{
// if current node is NULL
if (tree == NULL)
return;
// if it is the desired level
if (current_level == 1)
{
if(tree->left == NULL && tree->right == NULL)
{
printf("%d ", tree->data);
(*count)++;
}
}
// if it is not the desired level
else if (current_level > 1)
{
// go to left subtree
getLevel(tree->left, current_level - 1, count);
// go to right subtree
getLevel(tree->right, current_level - 1, count);
}
}
int getHeight(tree_node_t *tree)
{
// if the current node is NULL
if (tree == NULL)
return 0;
else
{
// get the left subtree height
int l = getHeight(tree->left);
// get the right subtree height
int r = getHeight(tree->right);
// return the larger height
if (l > r)
return(l + 1);
return(r + 1);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.