2 Replies - 7412 Views - Last Post: 11 August 2009 - 05:35 PM Rate Topic: -----

#1 nhubred  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 02-June 09

Counting Leafs in a Binary Tree

Posted 11 August 2009 - 04:09 PM

I was given code by my professor, and all I need to add to the code are functions to add the total number of leaves in a Binary Tree. I believe I have the code correct, but when I try to run it "count" always ends up being 0. Can anyone help me figure out what I am doing wrong?

For example, when a user inputs the numbers 5 4 2 9 0, a tree is created with "2" and "9" being the leaves, so the count should be 2; however it is printing as 0.

Any help is greatly appreciated!!

Main Code:

int main()
{
		BinaryTree T;
		int value,x;

		//BUILD A TREE FROM INOUT ENTERED

		cout<<"Enter an int...enter 0 when done ";
		cin>>value;

		while (value !=0)
		{
		  T.insert_tree(value);
		  cout<<"Enter an int...enter 0 when done ";
		  cin>>value;
		}

		// DO AN INORDER TRAVERSAL OF THE TREE
		T.preorder_traverse();
		cout << "Total number of leaves is: " << T.count_leaves() << endl;

		return 0;
}





count_leaves function:


int BinaryTree::count_leaves()
{
		return leaves(root_ptr);
}




leaves function:


int BinaryTree::leaves(BTnode * r_ptr)
{
		count = 0;

		if (r_ptr->left != NULL)
		{
		  count++;
		  leaves(r_ptr->left);
		}

		if (r_ptr->right != NULL)
		{
		  count++;
		  leaves(r_ptr->right);
		}
		return count;
}




Is This A Good Question/Topic? 0
  • +

Replies To: Counting Leafs in a Binary Tree

#2 GWatt  Icon User is offline

  • member icon

Reputation: 278
  • View blog
  • Posts: 3,078
  • Joined: 01-December 05

Re: Counting Leafs in a Binary Tree

Posted 11 August 2009 - 04:53 PM

Leaf nodes are nodes which have no children nodes.
In your code you increment the counter if a node is null.

int leaves(tnode *n)
{
	count = 0;
	if (n->left == NULL && n->right == NULL)
		count++;
	else
	{
		if (n->left != NULL)
			count += leaves(n->left);
		if (n->right != NULL)
			count += leaves(n->right);
	}

	return count;
}


Was This Post Helpful? 1
  • +
  • -

#3 nhubred  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 02-June 09

Re: Counting Leafs in a Binary Tree

Posted 11 August 2009 - 05:35 PM

View PostGWatt, on 11 Aug, 2009 - 03:53 PM, said:

Leaf nodes are nodes which have no children nodes.
In your code you increment the counter if a node is null.

int leaves(tnode *n)
{
	count = 0;
	if (n->left == NULL && n->right == NULL)
		count++;
	else
	{
		if (n->left != NULL)
			count += leaves(n->left);
		if (n->right != NULL)
			count += leaves(n->right);
	}

	return count;
}



Ah, silly mistake! Thank you so much!!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1