Counting leaves in a Binary Tree

SnackMan78 · #1 06-Oct-2005, 11:29

I have an assignment that requires me to count the number of leaves in a binarytree. I am using recursion to solve this, but my leafCnt algorithm keeps coming up with zeros and it shouldn't. I'd appreciate any insight as to where I am going wrong.

In this assignment, the bulk of the ADT is given. I created the ::leavesCount function of binarysearch.h, and added the protected variable leafCnt.

The p->link code should process the left side elements of the tree, and the p->rlink should process the right side elements.

Included is my main. and the course provide ADT's binaryTree.h and binarySearchTree.h

Here is the main:

CPP / C++ / C Code:

 

#include<iostream>
    using namespace std;

#include "binarySearchTree.h"

const int MAXSIZE = 14;

int main()
{
	int inputArray[MAXSIZE] = {60,50,70,30,53,80,35,57,75,32,40,77,48,45};	// load array
	char inChoice;

	bSearchTreeType<int> myTree;

	for (int i = 0; i < MAXSIZE; i++)		// load unsorted list 
		myTree.insert(inputArray[i]);

	cout<<"Display output using:\na) inorder traversal \nb) preorder traversal" 
		<<"\nc) postorder traversal\n\nEnter choice: ";	
	cin>> inChoice;

	cout<<"\n\n";

	switch (inChoice)
	{
	case 'a': case 'A':
		myTree.inorderTraversal();
		break;

	case 'b': case 'B':
		myTree.preorderTraversal();
		break;

	case 'c': case 'C':
		myTree.postorderTraversal();
		break;

	default : 
		cout<<"\nDefaulting to inorder Traversal";
		myTree.inorderTraversal();
	}

	cout<< endl;

	cout<<"\nThe number of nodes in the tree is/are: " << myTree.treeNodeCount() <<"\n";

	cout<<"\nThe number of leaves in the tree is/are: " << myTree.treeLeavesCount() <<"\n";
		
	cout<<endl;
	return 0;
}

binaryTree.h:

CPP / C++ / C Code:

//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree

#include <iostream>

using namespace std;

     //Definition of the node
template<class elemType>
struct nodeType
{
   elemType	           info;
   nodeType<elemType>  *llink;
   nodeType<elemType>  *rlink;
};

    //Definition of the class
template <class elemType>
class binaryTreeType
{
public:
    const binaryTreeType<elemType>& operator=
                 (const binaryTreeType<elemType>&); 
      //Overload the assignment operator.
    bool isEmpty();
      //Function to determine if the binary tree is empty.
      //Postcondition: Returns true if the binary tree is empty;
      //               otherwise, returns false.
    void inorderTraversal();
      //Function to do an inorder traversal of the binary tree.
      //Postcondition: The nodes of the binary tree are output
      //               in the inorder sequence.
    void preorderTraversal();
      //Function to do a preorder traversal of the binary tree.
      //Postcondition: The nodes of the binary tree are output
      //               in the preorder sequence.
    void postorderTraversal();
      //Function to do a postorder traversal of the binary tree.
      //Postcondition: The nodes of the binary tree are output
      //               in the postorder sequence.

    int treeHeight();
      //Function to deteremine the height of the binary tree.
      //Postcondition: The height of the binary tree is returned.
    int treeNodeCount();
      //Function to determine the number of nodes in the 
      //binary tree.
      //Postcondition: The number of nodes in the binary tree
      //               is returned.
    int treeLeavesCount();
      //Function to determine the number of leaves in the 
      //binary tree.
      //Postcondition: The number of leaves in the binary tree
      //               is returned.
    void destroyTree();
      //Deallocates the memory space occupied by the binary tree.
      //Postcondition: root = NULL;

    binaryTreeType(const binaryTreeType<elemType>& otherTree); 
      //copy constructor

    binaryTreeType();   
      //default constructor

    ~binaryTreeType();   
      //destructor

protected:
    nodeType<elemType> *root;
	int nodeCnt;
	int leafCnt;

private:
    void copyTree(nodeType<elemType>* &copiedTreeRoot,
                  nodeType<elemType>* otherTreeRoot);
      //Function to make a copy of the binary tree to 
      //which otherTreeRoot points. 
      //Postcondition: The pointer copiedTreeRoot points to
      //               the root of the copied binary tree.

    void destroy(nodeType<elemType>* &p);
      //Function to destroy the binary tree to which p points. 
      //Postcondition: The nodes of the binary tree to which
      //               p points are deallocated.
      //               p = NULL.

    void inorder(nodeType<elemType> *p);
      //Function to do an inorder traversal of the binary
      //tree to which p points.  
      //Postcondition: The nodes of the binary tree to which p
      //               points are output in the inorder sequence.
    void preorder(nodeType<elemType> *p);
      //Function to do a preorder traversal of the binary
      //tree to which p points.  
      //Postcondition: The nodes of the binary tree to which p
      //               points are output in the preorder sequence.
    void postorder(nodeType<elemType> *p);
      //Function to do a postorder traversal of the binary
      //tree to which p points.  
      //Postcondition: The nodes of the binary tree to which p
      //               points are output in the postorder sequence.

    int height(nodeType<elemType> *p);
      //Function to determine the height of the binary tree
      //to which p points. 
      //Postcondition: The height of the binary tree to which p
      //               points is returned.

    int max(int x, int y);
      //Function to determine the larger of x and y.
      //Postcondition: The larger of x and y is returned.

    int nodeCount(nodeType<elemType> *p);
      //Function to determine the number of nodes in the binary 
      //tree to which p points. 
      //Postcondition: The number of nodes in the binary tree
      //               to which p points is returned.

    int leavesCount(nodeType<elemType> *p);
      //Function to determine the number of leaves in the binary 
      //tree to which p points.
      //Postcondition: The number of nodes in the binary tree
      //               to which p points is returned.
};

	//Definition of member functions

template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
	root = NULL;
	nodeCnt = 0;
	leafCnt = 0;
}

template<class elemType>
bool binaryTreeType<elemType>::isEmpty()
{
	return (root == NULL);
}

template<class elemType>
void binaryTreeType<elemType>::inorderTraversal()
{
	inorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::preorderTraversal()
{
	preorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::postorderTraversal()
{
	postorder(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeHeight()
{
	return height(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeNodeCount()
{
	return nodeCount(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount()
{
	return leavesCount(root);
}

template <class elemType>
void  binaryTreeType<elemType>::copyTree
                      (nodeType<elemType>* &copiedTreeRoot,
		               nodeType<elemType>* otherTreeRoot)
{
	if(otherTreeRoot == NULL)
		copiedTreeRoot = NULL;
	else
	{
		copiedTreeRoot = new nodeType<elemType>;
		copiedTreeRoot->info = otherTreeRoot->info;
		copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
		copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
	}
} //end copyTree

template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		inorder(p->llink);
		cout<<p->info<<" ";
		inorder(p->rlink);
		nodeCnt++;
	}
}

template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		cout<<p->info<<" ";
		preorder(p->llink);
		preorder(p->rlink);
		nodeCnt++;
	}
}

template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		postorder(p->llink);
		postorder(p->rlink);
		cout<<p->info<<" ";
		nodeCnt++;
	}		
}

   //Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
           operator=(const binaryTreeType<elemType>& otherTree)
{ 
     
	if(this != &otherTree) //avoid self-copy
	{
		if(root != NULL)  //if the binary tree is not empty, 
			              //destroy the binary tree
			destroy(root);

		if(otherTree.root == NULL) //otherTree is empty
			root = NULL;
		else
			copyTree(root, otherTree.root);
	}//end else

   return *this; 
}

template <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
	if(p != NULL)
	{
		destroy(p->llink);
		destroy(p->rlink);
		delete p;
		p = NULL;
		nodeCnt--;
	}
}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
{
	destroy(root);
}

	//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
              (const binaryTreeType<elemType>& otherTree)
{
	if(otherTree.root == NULL) //otherTree is empty
		root = NULL;
	else
		copyTree(root, otherTree.root);
}

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
	destroy(root);
}

template<class elemType>
int binaryTreeType<elemType>::height(nodeType<elemType> *p)
{
	if(p == NULL)
		return 0;
	else
		return 1 + max(height(p->llink), height(p->rlink));
}

template<class elemType>
int binaryTreeType<elemType>::max(int x, int y)
{
	if(x >= y)
		return x;
	else
		return y;
}

template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p)
{
	return nodeCnt;
}

template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
{
	cout<<"\n\tDebug: The top element is: " << p->info;

	//if (p->llink == NULL  && p->rlink == NULL)	// end of the line for both sides of tree
	//	leafCnt = -999;

	 if (p->llink != NULL)
		leafCnt += leavesCount(p->llink);	// tot leaves in the left nodes

	 if (p->rlink != NULL)
		leafCnt += leavesCount(p->rlink);	// tot leaves in the right nodes

	return leafCnt;

}

#endif

binarySearchTree.h:

CPP / C++ / C Code:

//Header File Binary Search Tree

#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>
#include "binaryTree.h"

using namespace std;

template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
    bool search(const elemType& searchItem);
      //Function to determine if searchItem is in the binary 
      //search tree.
      //Postcondition: Returns true if searchItem is found in the 
      //             binary search tree; otherwise, returns false.

    void insert(const elemType& insertItem);
      //Function to insert insertItem in the binary search tree.
      //Postcondition: If no node in the binary search tree has 
      //           the same info as insertItem, a node with the 
      //           info insertItem is created and inserted in the
      //binary search tree.

    void deleteNode(const elemType& deleteItem);
      //Function to delete deleteItem from the binary search tree 
      //Postcondition: If a node with the same info as deleteItem 
      //               is found, it is deleted from the binary 
      //               search tree.

private:
    void deleteFromTree(nodeType<elemType>* &p);
      //Function to delete the node, to which p points, from the 
      //binary search tree.
      //Postcondition: The node to which p points is deleted
      //               from the binary search tree.
};


template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
    nodeType<elemType> *current;
    bool found = false;

    if(root == NULL)
       cerr<<"Cannot search the empty tree."<<endl;
    else
    { 
       current = root;

       while(current != NULL && !found)
       {
             if(current->info == searchItem)
                found = true;
              else
                  if(current->info > searchItem)
                     current = current->llink;
                  else
                     current = current->rlink;
       }//end while
    }//end else

    return found;
}//end search

template<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
    nodeType<elemType> *current;  //pointer to traverse the tree
    nodeType<elemType> *trailCurrent; //pointer behind current
    nodeType<elemType> *newNode;  //pointer to create the node

    newNode = new nodeType<elemType>;
    assert(newNode != NULL);
    newNode->info = insertItem;
    newNode->llink = NULL;
    newNode->rlink = NULL;

    if(root == NULL)
       root = newNode;
    else
    {
       current = root;
 
       while(current != NULL)
       {
           trailCurrent = current;

           if(current->info == insertItem)
           {
              cerr<<"The insert item is already in the list -- ";
              cerr<<"duplicates are not allowed."<<endl;
              return;
           }
           else
              if(current->info > insertItem)
                 current = current->llink;
              else
                 current = current->rlink;

       }//end while

       if(trailCurrent->info > insertItem)
          trailCurrent->llink = newNode;
       else
          trailCurrent->rlink = newNode;
   }
}//end insert



template<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	bool found = false;

	if(root == NULL)
		cerr<<"Cannot delete from the empty tree."<<endl;
	else
	{
		current = root;
		trailCurrent = root;

		while(current != NULL && !found)
		{
			if(current->info == deleteItem)
				found = true;
			else
			{
				trailCurrent = current;

				if(current->info > deleteItem)
					current = current->llink;
				else
					current = current->rlink;
			}
		}//end while

		if(current == NULL)
			cout<<"The delete item is not in the tree."<<endl;
		else
			if(found)
			{
				if(current == root)
					deleteFromTree(root);
				else
					if(trailCurrent->info > deleteItem)
						deleteFromTree(trailCurrent->llink);
					else
						deleteFromTree(trailCurrent->rlink);
			}//end if
	}
}//end deleteNode

template<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
                                 (nodeType<elemType>* &p)
{
     nodeType<elemType> *current;    //pointer to traverse 
                                     //the tree
     nodeType<elemType> *trailCurrent;   //pointer behind current
     nodeType<elemType> *temp;        //pointer to delete the node

     if(p == NULL)
        cerr<<"Error: The node to be deleted is NULL."
            <<endl;
     else if(p->llink == NULL && p->rlink == NULL)
          {
             temp = p;
             p = NULL;
             delete temp;
          }
     else if(p->llink == NULL)
          {
             temp = p;
             p = temp->rlink;
             delete temp;
          }
     else if(p->rlink == NULL)
          {
             temp = p;
             p = temp->llink;
             delete temp;
          }
     else
     {
        current = p->llink;
        trailCurrent = NULL;

        while(current->rlink != NULL)
        {
            trailCurrent = current;
            current = current->rlink;
        }//end while

        p->info = current->info;

        if(trailCurrent == NULL) //current did not move; 
                                 //current == p->llink; adjust p
           p->llink = current->llink;
        else
           trailCurrent->rlink = current->llink;
 
        delete current;
     }//end else
}//end deleteFromTree


#endif

kobi_hikri · #2 06-Oct-2005, 12:11

CPP / C++ / C Code:

int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
{
	cout<<"\n\tDebug: The top element is: " << p->info;

	//if (p->llink == NULL  && p->rlink == NULL)	// end of the line for both sides of tree
	//	leafCnt = -999;

	 if (p->llink != NULL)
		leafCnt += leavesCount(p->llink);	// tot leaves in the left nodes

	 if (p->rlink != NULL)
		leafCnt += leavesCount(p->rlink);	// tot leaves in the right nodes

	return leafCnt;

}

I don't see where you increment the counter when a leaf id encountered.
Notice that leafCnt initial value is 0 (and you should initialize it explicitly, in my opinion ...) and wherever you call recursively to the function leavesCount, you actually don't increment your counter.
You can solve this by adding an if statement that adds 1 to your counter if a leaf is encountered. I'll leave this up to you as you display high capabilities :->

Kobi Hikri.

davekw7x · #3 06-Oct-2005, 12:24

Quote:

Originally Posted by SnackMan78

I have an assignment that requires me to count the number of leaves in a binarytree.

You have a debug cout<< statement in your leavesCount. Good idea; now put some more. Something like the following (but change it according to your taste):

CPP / C++ / C Code:

int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
{
	cout<<"\n\tDebug: The top element is: " << p->info << endl;

	//if (p->llink == NULL  && p->rlink == NULL)	// end of the line for both sides of tree
	//	leafCnt = -999;

	 if (p->llink != NULL) {
                cout << "Old leafCnt = " << leafCnt << endl;
		leafCnt += leavesCount(p->llink);	// tot leaves in the left nodes
                cout << "New leafCnt = " << leafCnt << endl;
         }
         else {
           cout << "p->llink == NULL" << endl;
         }

	 if (p->rlink != NULL){
                cout << "Old leafCnt = " << leafCnt << endl;
		leafCnt += leavesCount(p->rlink);	// tot leaves in the right nodes
                cout << "New leafCnt = " << leafCnt << endl;
         }
         else {
           cout << "p->rlink == NULL" << endl;
         }

	return leafCnt;

}

If the ending count is zero, why? Where should the links should have been set? Look at that code. If you can't see the problem, some cout<< statements there should lead to enlightenment.

Regards,

Dave
--------------------------------
Trivia test for today:

Who was it who said the following?

"Putting debug statements in code is faster, I claim, than posting a
request for help and waiting for a helpful response."

kobi_hikri · #4 06-Oct-2005, 12:29

Quote:

Originally Posted by davekw7x

--------------------------------
Trivia test for today:

Who was it who said the following?

"Putting debug statements in code is faster, I claim, than posting a
request for help and waiting for a helpful response."

Now, I think it was rhetorical but I know this guy, Dave,
who always say stuff like this

SnackMan78 · #5 06-Oct-2005, 14:19

Thanks for the replies from both davekw7x and kobi hikri. From the 2 of you a think I have a resolution.

To kobi: I thought the presence of code:

CPP / C++ / C Code:

leafCnt += leavesCount(p-llink);

was incrementing leafCnt. Testing shows that it wasn't, but I did not see why.

Davekw7x's suggestion of expanding my debug displays gave a better clue of what was happening. There are many solutions, but the one I have chosen is:

CPP / C++ / C Code:

if (p->llink != NULL)
{
    ++leafCnt;
    leavesCount(p-llink);
}

Also, how would I explicitly initialize leafCnt if the variable is within a recursive loop, except in the default constructor like I've done?

kobi_hikri · #6 06-Oct-2005, 15:53

Quote:

Originally Posted by SnackMan78

Also, how would I explicitly initialize leafCnt if the variable is within a recursive loop, except in the default constructor like I've done?

You can initialize a counter outside the function and pass a pointer to it as an argument.
But, actually, what I ment was :
When you enter the recursion, it means that you didnt have any leaves at the previous level (do you understand why ?), therefore the current value of leafCnt (per this instance of the recursion) is 0. I recommend showing that you understand this point by assigning leafCnt the value 0 when you start the current instance of the recursion. It is also more readable.

Best regards,
Kobi Hikri.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
printing binary search tree	nkhambal	C Programming Language	2	26-Mar-2005 04:01
Please help! Dynamic binary tree problem	robsmith	C Programming Language	3	15-Mar-2005 22:20
Displaying node attributes in an XML tree display	njp01u	MS Visual C++ / MFC Forum	2	07-Feb-2005 18:42
Binary Tree Trouble	neufunk	C Programming Language	4	06-Dec-2004 10:52

Counting leaves in a Binary Tree

Re: Counting leaves in a BinaryTree

Re: Counting leaves in a BinaryTree

Re: Counting leaves in a BinaryTree

Re: Counting leaves in a BinaryTree

Re: Counting leaves in a BinaryTree