CS236 Binary Trees

You are given two classes for implementing a simple binary tree 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.

// Node for the binary tree items
class BTreeNode
{
public:
BTreeNode(double x, BTreeNode *leftp = NULL, BTreeNode *rightp = NULL)
{
value = x;
left = leftp;
right = rightp;
}

private:
double value;
BTreeNode *left, *right;
friend class BST; // BST has friend status
};

// Binary tree class itself
class BST
{
public:
int height() { return height(tree); } // return the tree height
void insert(double x); // insert numbers into the binary tree
void inorder(vector< double>& v) { inorder(v, tree); } // appens all nodes in tree
int leafCounter() { return leafCounter(tree); } // count the number of leaves
BST() { tree = NULL; }

private:
void inorder(vector< double>& tlist, BTreeNode *t); // storing nodes in subtree
int leafCounter(BTreeNode *t); // count number of leaves
static int height(BTreeNode *t); // calculate the height of the tree
BTreeNode *tree;
};

Sample Output:

This program allows you to insert some numbers in binary search tree.
It prints out the numbers in the tree in inorder.
It computes and prints the number of leaves in the tree.
and the height of the tree.
Enter 10 numbers:
8 20 6 4 23 30 29 33 7 45

The items in the tree inorder are:
4 6 7 8 20 23 29 30 33 45
The height of the tree is 6
The number of leaves is 4