Solution to Recall that a full binary tree is a binary tree where each level of the … - Sikademy
Author Image

Archangel Macsika

Recall that a full binary tree is a binary tree where each level of the tree has the maximum number of nodes possible. a. If the level of the root of a non-empty full binary tree is level 1, the level of the root's children is level 2, etc., how many nodes are on level i, i ≥ 1? b. If a non-empty full binary tree has n levels (or a height of n), how many nodes does the tree have in total? Express your answer in closed form (i.e. do not use "..." in your final answer). c. Prove that the number of leaves in a non-empty full binary tree is 1 more than the number of non-leaves. When you prove this, don't just show an example. Write your proof in general for ANY non-empty full binary tree.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

#include <iostream> using namespace std; struct node{ int value; node *left; node *right; }; class btree{ public: btree(); ~btree(); void insert(int key); node *search(int key); void destroy_tree(); void inorder_print(); void postorder_print(); void preorder_print(); private: void destroy_tree(node *leaf); void insert(int key, node *leaf); node *search(int key, node *leaf); void inorder_print(node *leaf); void postorder_print(node *leaf); void preorder_print(node *leaf); node *root; }; btree::btree(){ root = NULL; } btree::~btree(){ destroy_tree(); } void btree::destroy_tree(node *leaf){ if(leaf != NULL){ destroy_tree(leaf->left); destroy_tree(leaf->right); delete leaf; } } void btree::insert(int key, node *leaf){ if(key < leaf->value){ if(leaf->left != NULL){ insert(key, leaf->left); }else{ leaf->left = new node; leaf->left->value = key; leaf->left->left = NULL; leaf->left->right = NULL; } }else if(key >= leaf->value){ if(leaf->right != NULL){ insert(key, leaf->right); }else{ leaf->right = new node; leaf->right->value = key; leaf->right->right = NULL; leaf->right->left = NULL; } } } void btree::insert(int key){ if(root != NULL){ insert(key, root); }else{ root = new node; root->value = key; root->left = NULL; root->right = NULL; } } node *btree::search(int key, node *leaf){ if(leaf != NULL){ if(key == leaf->value){ return leaf; } if(key < leaf->value){ return search(key, leaf->left); }else{ return search(key, leaf->right); } }else{ return NULL; } } node *btree::search(int key){ return search(key, root); } void btree::destroy_tree(){ destroy_tree(root); } void btree::inorder_print(){ inorder_print(root); cout << "\n"; } void btree::inorder_print(node *leaf){ if(leaf != NULL){ inorder_print(leaf->left); cout << leaf->value << ","; inorder_print(leaf->right); } } void btree::postorder_print(){ postorder_print(root); cout << "\n"; } void btree::postorder_print(node *leaf){ if(leaf != NULL){ inorder_print(leaf->left); inorder_print(leaf->right); cout << leaf->value << ","; } } void btree::preorder_print(){ preorder_print(root); cout << "\n"; } void btree::preorder_print(node *leaf){ if(leaf != NULL){ cout << leaf->value << ","; inorder_print(leaf->left); inorder_print(leaf->right); } } int main(){ //btree tree; btree *tree = new btree(); tree->insert(10); tree->insert(6); tree->insert(14); tree->insert(5); tree->insert(8); tree->insert(11); tree->insert(18); tree->preorder_print(); tree->inorder_print(); tree->postorder_print(); delete tree; }

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-3-stid-44-sqid-1043-qpid-39