Click here to Skip to main content
15,847,427 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
C++
//Create a starter and a recursive function for each of following: (function declarations are already done in BST.h)

//count the leaves

//determine the height
// Create a starter and a recursive function counts the number of nodes at each level. Uses a vector parameter sent by reference. (function declarations are already done in BST.h)

BST.H

#ifndef BST_H
#define BST_H

#include
#include
using namespace std;

template
class TreeNode
{
public:
   T element; // Element contained in the node
   TreeNode* left; // Pointer to the left child
   TreeNode* right; // Pointer to the right child

   TreeNode(const T& e) // Constructor
   {
       this->element = e;
       left = nullptr;
       right = nullptr;
   }
};


template
class BST
{
public:
   BST(); // No-arg constructor
   BST(vector elements[]);
  
   ~BST(); // Destructor
   int getSize() const;
   bool search(const T& e) const;
   bool insert(const T& e);
   bool remove(const T& e);
   void inorder() const;
   void clear();
   void printTree() const;


   //Question = 1 : uncomment the following and these definitions, the recursive overloaded functions, and test:
   /*
   int getNumberOfLeaves() const;
   int height() const;
   */

   //Question -2: uncomment the following and these definitions, the recursive overloaded functions, and test:


   //Note: the vector is declared and initialized (clear() ) here, the recurisive call is made, and then the vector is printed out
   //void nodesPerLevel() const;


protected:
   TreeNode* root;
   int size;
  
private:
   void inorder(const TreeNode* root) const;
   void clear(const TreeNode* root);

   void printTree(const TreeNode* root, int indent) const;

   //Question =1: uncomment the following, and add the definitions (code them)
   /*
   int getNumberOfLeaves(const TreeNode* root) const;
   int height(const TreeNode* root, int level) const;
   */

   //Question =2 :uncomment the following, and add the definition (code it)


   //void nodesPerLevel(vector& nodes, const TreeNode* root, int l) const;
};

template
BST::BST()
{
   root = nullptr;
   size = 0;
}

template
BST::BST(vector elements[])
{
   root = nullptr;
   size = 0;
   for (int i = 0; i < elements->size(); i++)
       insert(elements[i]);
}


/* Destructor */
template
BST::~BST()
{
   clear();
}

/* Get the number of nodes in the tree */
template
int BST::getSize() const
{
   return size;
}

/* Return true if the element is in the tree */
template
bool BST::search(const T& e) const
{
   TreeNode* current = root; // Start from the root

   while (current != nullptr)
       if (e < current->element)
       {
           current = current->left; // Go left
       }
       else if (e > current->element)
       {
           current = current->right; // Go right
       }
       else // Element e matches current.element
           return true; // Element e is found

   return false; // Element e is not in the tree
}

// Insert element e into the binary tree
// Return true if the element is inserted successfully
// Return false if the element is already in the list
template
bool BST::insert(const T& e)
{
   if (root == nullptr)
       root = new TreeNode(e); // Create a new root
   else
   {
       // Locate the parent node
       TreeNode* parent = nullptr;
       TreeNode* current = root;
       while (current != nullptr)
           if (e < current->element)
           {
               parent = current;
               current = current->left;
           }
           else if (e > current->element)
           {
               parent = current;
               current = current->right;
           }
           else
               return false; // Duplicate node not inserted

                           // Create the new node and attach it to the parent node
       if (e < parent->element)
           parent->left = new TreeNode(e);
       else
           parent->right = new TreeNode(e);
   }

   size++;
   return true; // Element inserted
}


/* Delete an element e from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
template
bool BST::remove(const T& e)
{
   // Locate the node to be deleted and also locate its parent node
   TreeNode* parent = nullptr;
   TreeNode* current = root;
   while (current != nullptr)
   {
       if (e < current->element)
       {
           parent = current;
           current = current->left;
       }
       else if (e > current->element)
       {
           parent = current;
           current = current->right;
       }
       else
           break; // Element e is in the tree pointed by current
   }

   if (current == nullptr)
       return false; // Element e is not in the tree

                   // Case 1: current has no left children
   if (current->left == nullptr)
   {
       // Connect the parent with the right child of the current node
       if (parent == nullptr)
       {
           root = current->right;
       }
       else
       {
           if (e < parent->element)
               parent->left = current->right;
           else
               parent->right = current->right;
       }

       delete current; // Delete current
   }
   else
   {
       // Case 2: The current node has a left child
       // Locate the rightmost node in the left subtree of
       // the current node and also its parent
       TreeNode* parentOfRightMost = current;
       TreeNode* rightMost = current->left;

       while (rightMost->right != nullptr)
       {
           parentOfRightMost = rightMost;
           rightMost = rightMost->right; // Keep going to the right
       }

       // Replace the element in current by the element in rightMost
       current->element = rightMost->element;

       // Eliminate rightmost node
       if (parentOfRightMost->right == rightMost)
           parentOfRightMost->right = rightMost->left;
       else
           // Special case: parentOfRightMost->right == current
           parentOfRightMost->left = rightMost->left;

       delete rightMost; // Delete rightMost
   }

   size--;
   return true; // Element inserted
}

/* Inorder traversal Note: we use a public "starter" method, and a private recursive method called from the starter*/
//starter
template
void BST::inorder() const
{
   inorder(root);
   cout << endl;
}

/* recursive Inorder traversal from a subtree */

template
void BST::inorder(const TreeNode* root) const
{
   if (root == nullptr)
       return;
   inorder(root->left);
   cout << root->element << " ";
   inorder(root->right);
}

/* Remove all nodes from the tree. Two methods, same design as inorder */
template
void BST::clear()
{
   clear(root);
   size = 0;
   root = nullptr;
}

template
void BST::clear(const TreeNode* root)
{
   if (root == nullptr)
       return;
   clear(root->left);
   clear(root->right);
   delete root;
   return;
}


template
void BST::printTree() const {
   printTree(root, 0);
}


template
void BST::printTree(const TreeNode* root, int indent) const {
   if (root == nullptr)
       return;

   // Uses a reverse inorder traversal. print the right side first
   printTree(root->right, indent + 1);
   //print the current node
   for (int i = 0; i < indent; i++)
       cout << " ";
   cout << root->element << endl;
   // print the left side last
   printTree(root->left, indent + 1);
}


#endif


What I have tried:

I am trying to write the starter and recursive function to get the number of leaves, height of tree and number of nodes in each level. However, I did not figure it out, that how to do this. Could anyone here please help me in complete my code. I did overall code, you just have to help me in getting these three.
Posted
Updated 28-Oct-19 22:24pm
v2

1 solution

This is your homework and you should do it yourself. But I will give you some tips.

Recursive functions are calling themself, but have some stopping logic. The result than you have to provide. This is a plain example
C++
int sumsup(TreeNode *node) {
  if( node == 0) return 0; // exit condition

  //working code
  int left = sumup(node->left);
  int right = sumup(node->right);

   return left + right; 
}
Read the binary tree example for further information.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900