Help with counting leaves in binary tree function

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 417 Views - Last Post: 07 November 2017 - 03:10 PM Rate Topic: -----

#1 dhect3  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 07-November 17

Help with counting leaves in binary tree function

Posted 07 November 2017 - 10:49 AM

I am having a problem with the output of my count leaves function. I am getting the output 1 when it shouldn't be. Any help or suggestions are welcome! Thank You:)


MY Binary Tree Header File

template<class T>       //Creating my template for my class to be able to hold any data type.
class BinaryTree        //Creating the class BinaryTree
{
private:
	struct TreeNode       //Creating the pointers for a Binary tree.
	{
		T value;
		TreeNode *left;
		TreeNode *right;
	};

	TreeNode *root;      //Creating the root pointer outside of the TreeNode struct.

	void insert(TreeNode *&, TreeNode *&);    //My list of private functions which will be able to insert, Count Nodes, Count Leaves,
	int countNodes(TreeNode *&nodePtr);       //get the tree height, and get the tree width.
	int countLeaves(TreeNode* nodePtr);       
	int getTreeHeight(TreeNode* nodePtr);    
	int width(TreeNode* nodePtr);
public:
	BinaryTree()                       //Creating mt dafault constructor which sets the root to NULL;
	{
		root = nullptr;
	}

	void insertNode(T);               //My public functions that allows the user to access the private functions by calling them inside the public functions.
	int numNodes();
	int numLeafNodes();
	int height();
	int getWidth();
};


My functions for the number of leaves

template <class T>
int BinaryTree<T>::numLeafNodes()     //The public version of the function which counts the number of leaves
{
	countLeaves(root);         //calling the private version of the function
	return countLeaves(root);      //returning the private function
}

template <class T>
int BinaryTree<T>::countLeaves(TreeNode* nodePtr)
{
	if (root == NULL)                       //If the there is nothing in the tree return 0.
		return 0;
	if (root->right && root->left)        // Seeing if the the node is a leaf or not, if it is to return 1
		return 1;
	return (countLeaves(root->right) + countLeaves(root->left)); //returng the number of times the countLeaves program will have to run to reach the leaves.
}



Is This A Good Question/Topic? 0
  • +

Replies To: Help with counting leaves in binary tree function

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13495
  • View blog
  • Posts: 53,911
  • Joined: 12-June 08

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 10:51 AM

What do you think this evaluates?
13    if (root->right && root->left)        // Seeing if the the node is a leaf or not, if it is to return 1

Was This Post Helpful? 0
  • +
  • -

#3 dhect3  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 07-November 17

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 10:54 AM

Doesn't it move through the tree until it hits null?

This post has been edited by Skydiver: 07 November 2017 - 02:26 PM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 0
  • +
  • -

#4 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13495
  • View blog
  • Posts: 53,911
  • Joined: 12-June 08

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 10:58 AM

Are you sure about that? Perhaps the arrow operator is only a pointer reference to an object. Not a particular action or method.

https://www.tutorial...r_operators.htm
Was This Post Helpful? 0
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 20,142
  • Joined: 05-May 12

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 10:59 AM

There is no need to quote the post above yours. Just use the big Reply button or the Fast Reply area.

Try stepping through your code with a debugger and see if your hypothesis is correct.
Was This Post Helpful? 0
  • +
  • -

#6 dhect3  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 07-November 17

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 11:03 AM

I used to have this code but it would not compile without an error

if (!root->right && !root->left) 
return 1;

Was This Post Helpful? 0
  • +
  • -

#7 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13495
  • View blog
  • Posts: 53,911
  • Joined: 12-June 08

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 11:10 AM

What is your thinking for doing that?
It helps folks to better help you when you copy/paste your error here.
Was This Post Helpful? 0
  • +
  • -

#8 dhect3  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 07-November 17

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 11:42 AM

It doesn't run through all the way it has a message saying exception unhandled
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 20,142
  • Joined: 05-May 12

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 11:59 AM

But that exception is not a compilation error. We are interested in the compilation error that you claimed that you were getting. For you to have gotten an exception would mean that you actually got the code to compile, and you were not getting a compilation error.

Anyway, the reason we are pushing on you so much about a single line is because it seems that you wrote it without much thought or understanding of why you wrote it.
Was This Post Helpful? 0
  • +
  • -

#10 dhect3  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 07-November 17

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 12:22 PM

It compiles but wont compile fully. It stops at the countLeaves function and says exception unhandeled. When I try to change anything about that line it pops up.
Was This Post Helpful? 0
  • +
  • -

#11 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13495
  • View blog
  • Posts: 53,911
  • Joined: 12-June 08

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 12:30 PM

What are you using to compile? Is it not giving you *ANY* error messages?
Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 20,142
  • Joined: 05-May 12

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 12:40 PM

There is a difference between compiling, linking, and running. It sounds like your code is compiling and linking, but when you run it, your are getting an exception.

Any which way, give us the exact error or exception. Do not summarize. Do not paraphrase. Just copy and paste the text. (If at all possible, avoid screen shots.)
Was This Post Helpful? 0
  • +
  • -

#13 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2014
  • View blog
  • Posts: 5,397
  • Joined: 27-December 05

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 01:52 PM

You really make it hard (and irritating) to help you when you refuse to answer questions fully. The error messages provide important information that helps diagnose a problem, but it's important to see all of the details in those messages.

I'll try anyway.

But if I'm going to give you an answer I have to know that you'll understand what it means. So, when you write this if statement
if (!root->right && !root->left) 

can you tell me when the conditional expression (!root->right && !root->left) is true and when it is false? In other words, under what condition or conditions will the code under the if statement be executed (whatever that code happens to be)?

Or looking at it slightly differently, what does it actually mean when that statement is true or false?
Was This Post Helpful? 0
  • +
  • -

#14 dhect3  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 07-November 17

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 02:17 PM

The code will be executed when the value that the root doesn't exist to the right and the left. The '!' means does not point to any node. The code will not execute until it reaches the end of the tree.

This post has been edited by Skydiver: 07 November 2017 - 02:25 PM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 0
  • +
  • -

#15 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2014
  • View blog
  • Posts: 5,397
  • Joined: 27-December 05

Re: Help with counting leaves in binary tree function

Posted 07 November 2017 - 02:46 PM

Close, but let's pin it down a little more precisely. Take just one part of the statement. Say,
if(!root->right)

Now you know that root->right is actually just a pointer, yes? Your root is a pointer to some node, and right is a pointer to that node's right child node, so root->right is just a pointer to the root node's right child node. But the conditional expression of an if statement must be either true or false. So how does root->right or !root->right become true or false?

It's because in the context of a conditional expression, the compiler interprets a null pointer as "false", and any other pointer as "true". (And of course the negation of a statement has the opposite truth value of the original statement.)

So in the if statement, the conditional (!root->right) is true if root->right is a null pointer. And in your if statement, the conditional
if(!root->right && !root->left)
is "true" if BOTH of the child pointers are null.

Got that? If you have any doubts about it, ask, otherwise we can proceed.
Was This Post Helpful? 2
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2