Please write the complete program with the main function. Include the comments o
ID: 3598158 • Letter: P
Question
Please write the complete program with the main function. Include the comments of explanation. Thank you.
I need output like this: Depth, How many leaves in treenode and Total number of leaves. Thanks.
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.
Explanation / Answer
Here is program written in c++.
All code is commented where necessary. Output of the file also atttached.
#include <iostream>
struct node
{
int key;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)new (struct node);
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
//A utility function to insert a new node with given key in BST
struct node* insert(struct node* node, int key)
{
//If the tree is empty, return a new node
if (node == NULL) return newNode(key);
//Otherwise, recur down the tree
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
// return the (unchanged) node pointer
return node;
}
void inorder(struct node *root)
{
//if node is not null return
if (root != NULL)
{
inorder(root->left); //call on left subtree
std::cout << root->key << ", "; //print the root
inorder(root->right); // call on right subtree
}
}
void depth_distribution(struct node* node, int level=0)
{
//if node is null is null return
if(!node) return;
//if leaf node print the value and retrun
if(!node->left && !node->right)
{
std::cout << "Leaf at level: " << level
<< ", Key: " << node->key << std::endl;
return;
}
//call on left subtree
if(node->left) depth_distribution(node->left, level+1);
//call on right subtree
if(node->right) depth_distribution(node->right, level+1);
}
int main(int argc, char const *argv[])
{
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 10);
insert(root, 70);
insert(root, 60);
insert(root, 80);
insert(root, 40);
insert(root, 25);
std::cout << "Inorder: ";
inorder(root);
std::cout << std::endl;
depth_distribution(root);
return 0;
}
// end of code
Output