Take the height-balanced tree code, and add a function int depth distribution(tr
ID: 3601519 • 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 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);
}
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Function to get the count of leaf nodes in a binary tree*/
unsigned int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/*Driver program to test above functions*/
int main()
{
/*create a tree*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/*get leaf count of the above created tree*/
printf("Leaf count of the tree is %d", getLeafCount(root));
getchar();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Function to get the count of leaf nodes in a binary tree*/
unsigned int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/*Driver program to test above functions*/
int main()
{
/*create a tree*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/*get leaf count of the above created tree*/
printf("Leaf count of the tree is %d", getLeafCount(root));
getchar();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.