Question

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;

}

Answer 1

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
   }
}