In: Computer Science
You are given two classes for implementing a simple binary tree of capable of storing number, count the number of leaves and computes the height of a binary tree.
You can add on additional parameters or functions as you wish, but the program must apply the chapter objectives.
class BTreeNode { //node for the binary tree items
public:
BTreeNode(double x, BTreeNode *leftp = NULL, BTreNode *rightp = NULL) {
value = x;
left = leftp;
right = rightp;
}
private:
double value;
BTreeNode *left, *right;
friend class BST; //BST has friend status
};
class BST { //binary tree class
public:
int height() { //returns the tree height
return height(tree);
}
void insert(double x); //inserts numbers into the binary tree
void inorder(vector<double> &v) { //appends all nodes in subtree
inorder(v, tree);
}
int leafCounter() { //counts the number of leaves
return leafCounter(tree);
}
BST() {
tree = NULL;
}
private:
void inorder(vector<double>&tlist, BTreeNode *t); //storing nodes in a subtree
int leafCounter(BTreeNode *t); //counts the number of leaves
static int height(BTreeNode *t); //calculates the height of the tree
BTreeNode *tree;
}
class BTreeNode { //node for the binary tree items
public:
BTreeNode(double x, BTreeNode *leftp = NULL, BTreNode *rightp = NULL) {
value = x;
left = leftp;
right = rightp;
}
private:
double value;
BTreeNode *left, *right;
friend class BST; //BST has friend status so bst can directly access the private members left, right and value
};
class BST { //binary tree class
public:
int height() { //returns the tree height
return height(tree);
}
void insert(double x); //inserts numbers into the binary tree
void inorder(vector<double> &v) { //appends all nodes in subtree
inorder(v, tree);
}
int leafCounter() { //counts the number of leaves
return leafCounter(tree);
}
BST() {
tree = NULL;
}
private:
void inorder(vector<double>&tlist, BTreeNode *t); //storing nodes in a subtree
int leafCounter(BTreeNode *t); //counts the number of leaves
static int height(BTreeNode *t); //calculates the height of the tree
BTreeNode *tree;
};
// helper function to return the number of leaf nodes of the
tree
int BST::leafCounter(BTreeNode *t)
{
// if NULL node return 0
if(t == NULL)
return 0;
// if left and right pointers are NULL => t is a
left node , return 1
if(t->left == NULL &&
t->right==NULL)
return 1;
// return total number of left nodes in left subtree
and right subtree
return(leafCounter(t->left)+leafCounter(t->right));
}
// function function to return the height of the tree
int BST::height(BTreNode *t)
{
// if t is null, return 0
if(t == NULL)
return 0;
// add 1 for node t
int lHeight = 1+height(t->left); // get the height
of the left subtree
int rHeight = 1+height(t->right); // get the height
of right subtree
// if height of leaf subtree > height of right
subtree return left subtree height
if(lHeight > rHeight)
return lHeight;
return rHeight; // else return right
subtree height
}
// helper function to append the nodes as it would appear in
inorder traversal
void BST:: inorder(vector<double>&tlist, BTreeNode
*t)
{
// if t is not null
if(t != NULL)
{
inorder(tlist, t->left); //
perform inorder traversal for the left subtree
tlist.push_back(t->value); //
push the value of node t
inorder(tlist,t->right); //
perform inorder traversal for the right subtree
}
}