public member function that returns the height of the tree and a function that r
ID: 3673369 • Letter: P
Question
public member function that returns the height of the tree and a function that return the number of the leaf nodes of the same tree
// Program for testing the Binary Search Tree (BST) implementation
#include "book.h"
// BST implementation
#include "BST.h"
// Warning: This test driver has horrible memory leaks.
// Everytime the program does a remove to "it", the next time "it"
// gets used, that previous Int object gets clobbered.
int main()
{
BST<int, Int*> tree;
Int* it;
cout << "Size: " << tree.size() << " ";
tree.insert(100, new Int(100));
tree.print();
cout << "Size: " << tree.size() << " ";
it = tree.remove(10);
tree.print();
cout << "Size: " << tree.size() << " ";
tree.clear();
cout << "Cleared. ";
cout << "Size: " << tree.size() << " ";
tree.insert(15, new Int(15));
cout << "Size: " << tree.size() << " ";
if ((it = tree.find(20)) != NULL)
cout << "Found " << it << endl;
else cout << "No key 20 ";
if ((it = tree.find(15)) != NULL)
cout << "Found " << it << endl;
else cout << "No key 15 ";
tree.print();
if ((it = tree.remove(20)) != NULL)
cout << "Removed " << it << endl;
else cout << "No key 20 ";
cout << "Now, insert 20 ";
tree.insert(20, new Int(20));
tree.print();
if ((it = tree.remove(20)) != NULL)
cout << "Removed " << it << endl;
else cout << "No key 20 ";
tree.print();
tree.insert(700, new Int(700));
cout << "Size: " << tree.size() << " ";
tree.insert(350, new Int(350));
tree.insert(201, new Int(201));
tree.insert(170, new Int(170));
tree.insert(151, new Int(151));
tree.insert(190, new Int(190));
tree.insert(1000, new Int(1000));
tree.insert(900, new Int(900));
tree.insert(950, new Int(950));
tree.insert(10, new Int(10));
tree.print();
if ((it = tree.find(1000)) != NULL)
cout << "Found " << it << endl;
else cout << "No key 1000 ";
if ((it = tree.find(999)) != NULL)
cout << "Found " << it << endl;
else cout << "No key 999 ";
if ((it = tree.find(20)) != NULL)
cout << "Found " << it << endl;
else cout << "No key 20 ";
cout << "Now do some delete tests. ";
tree.print();
if ((it = tree.remove(15)) != NULL)
cout << "Removed " << it << endl;
else cout << "No key 15 ";
tree.print();
if ((it = tree.remove(151)) != NULL)
cout << "Removed " << it << endl;
else cout << "No key 151 ";
tree.print();
if ((it = tree.remove(151)) != NULL)
cout << "Removed " << it << endl;
else cout << "No key 151 ";
if ((it = tree.remove(700)) != NULL)
cout << "Removed " << it << endl;
else cout << "No key 700 ";
tree.print();
tree.clear();
tree.print();
cout << "Size: " << tree.size() << " ";
cout << "Finally, test iterator ";
tree.insert(3500, new Int(3500));
tree.insert(2010, new Int(2010));
tree.insert(1700, new Int(1700));
tree.insert(1510, new Int(1510));
tree.insert(1900, new Int(1900));
tree.insert(10000, new Int(10000));
tree.insert(9000, new Int(9000));
tree.insert(9500, new Int(9500));
tree.insert(100, new Int(100));
tree.print();
cout << "Start: ";
Int* temp;
while (tree.size() > 0) {
temp = tree.removeAny();
cout << temp << " ";
}
cout << " ";
return 0;
}
Explanation / Answer
Hi, you have not provided BST.h, so i can not see the structure of BST Node.
I am providing you general methods to get Number of Leaf Node count and Height of tree.
You can use it in your program.
/* Function to get the count of leaf nodes in a binary tree*/
unsigned int getLeafCount(BST *node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
//Function to get height of BST
int height(BST *node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = height(node->left);
int rDepth = height(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.