Question

In: Computer Science

You are given two classes for implementing a simple binary tree of capable of storing number,...

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;

}

Solutions

Expert Solution


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


Related Solutions

I was trying to implement a simple binary search tree using this given class of bst...
I was trying to implement a simple binary search tree using this given class of bst in c++ public: BST(); ~BST(); void insertKey(int newKey); bool hasKey(int searchKey); std::vector<int> inOrder(); int getHeight(); however; i am still required to use another class for the nodes as a pointer and i need to manage memory leak. in main we should ask for the numbers we need to insert in the binary search tree and also let the user end it with a letter...
Binary Tree Create a binary search tree using the given numbers in the order they’re presented....
Binary Tree Create a binary search tree using the given numbers in the order they’re presented. State if the resulting tree is FULL and/or BALANCED. 37, 20, 18, 56, 40, 42, 12, 5, 6, 77, 20, 54
There are plenty of examples of Binary Search Tree classes written in Java available on the...
There are plenty of examples of Binary Search Tree classes written in Java available on the Internet. Find one. Either download or copy and paste the code into an appropriately named Java class file. Compile that file. Then, create the class BinarySrcTree, which will inherit from the class you downloaded from the Internet. Place a comment in the class that states where you obtained your base class (URL or Web page or site name). You will then overwrite or overload...
Write a simple Java code to make a Binary Tree for the following tree: Don’t use...
Write a simple Java code to make a Binary Tree for the following tree: Don’t use serializable interface implantation /** Class to encapsulate a tree node. */ protected static class Node implements Serializable {
You are given a reference to the root node of a binary search tree, that implements...
You are given a reference to the root node of a binary search tree, that implements a dictionary data structure. Please print all the elements in depths 500 through 510, all in sorted order. A node in a binary search tree is at depth x, if it takes x hops to get from the root. So the root is at depth 0, the children of the root are at depth 1, and so on. The class TreeNode defines a single...
You are given a reference to the root node of a binary search tree, that implements...
You are given a reference to the root node of a binary search tree, that implements a dictionary data structure. Please print all the elements in depths 500 through 510, all in sorted order. A node in a binary search tree is at depth x, if it takes x hops to get from the root. So the root is at depth 0, the children of the root are at depth 1, and so on. The class TreeNode defines a single...
C++ tree program (do NOT use STRUCT, use classes)    Program 1 Implement a Binary tree...
C++ tree program (do NOT use STRUCT, use classes)    Program 1 Implement a Binary tree using an array    Program 2 Implement a tree using linked list - pointer Binary Tree    Program 3 - Convert program 1 to a template
Write a solution to return the count of the number of nodes in a binary tree....
Write a solution to return the count of the number of nodes in a binary tree. Your method will be passed one parameter, a copy of a pointer to the root node of the tree (Node *) and will return an int that is the count of nodes. If the tree is empty, return 0 (this is the recursive base case).
Give a proof by induction that the number of nodes of a full binary tree with...
Give a proof by induction that the number of nodes of a full binary tree with a height of "h" is: (2^(h+1))-1.
Given a binary search tree T with n elements. For any two keys k1 and k2...
Given a binary search tree T with n elements. For any two keys k1 and k2 such that k1 < k2, there is an algorithm to print all elements x in T such that k1 ≤x ≤k2 in O(K + log n) time on average, where K is the number of the elements printed out.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT