• Advertisement
Sign in to follow this  

Annoying Error when trying to get height of a binary tree, weird errors.

This topic is 2060 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

OK, this is officially pissing me off (Not sure if that's allowed, but anyways.) I have a binary tree like so:

[CODE]
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
#include <boost/lexical_cast.hpp>
#include "Exception.h"
#include "DoubleLinkedListNode.h"
#include <stdio.h>
#include <iostream>
using namespace std;
template<typename T>
class BinaryTree
{
public:
// assignment operator. over loaded.
const BinaryTree<T>& operator = (const BinaryTree<T>& otherList)
{
if(rootNode != NULL)
{
destroy(rootNode);

if(otherList.rootNode == NULL)
{
rootNode = NULL;
}
else
{
copyTree(rootNode,otherList.rootNode);
}
}
return *this;
}
// returns whether the tree is currently empty.
bool isTreeEmpty() const
{
return (rootNode == NULL);
}
// Inorder traversal.
// nodes are visited in order
// post-condition: Nodes are printed in inorder sequence.
void inorderTraverlsal()
{
inorderTraverlsal(rootNode);
}
// preorder traversal.
// traverse the binary tree in pre order.
void preorderTraversal()
{
preorderTraversal(rootNode);
}
// post order traversal
// traverse the binary tree in post order.
void postOrderTraversal()
{
postOrderTraversal(rootNode);
}
// function to return the tree hieght.
int getTreeHeight() const
{
return height(rootNode);
}
// get Leaf count.
int getLeafCount() const
{
return leafCount(rootNode);
}
// get the tree node count
int getTreeNodeCount() const
{
return nodeCount(rootNode);
}
// function to destroy the tree.
void destroyTree()
{
destroy(rootNode);
}
DListNode<T>* getRoot() const
{
return rootNode;
}
// virtual function to search for an item in the tree.
// returns a boolean
virtual bool search(const T& elem) const = 0;
// add item to tree
// post condition: inserted item does not already exist.
virtual void InsertNode(T& data) = 0;
// add node to tree.
// same as the insertNode but takes a pointer to a node rather then
// just the data
virtual void InsertNode(DListNode<T>* node) = 0;
// delete node.
// function to delete a node based on data infro.
virtual void deleteNode(const T& item) = 0;
// function to delete node based on a node input.
virtual void deleteNode(DListNode<T>* &node) = 0;
BinaryTree()
{
rootNode = NULL;
}
BinaryTree(const BinaryTree<T>& otherTree)
{
operator=(otherTree);
}
~BinaryTree()
{
destroyTree();
}
protected:
DListNode<T>* rootNode; // root node
private:
// function to copy a tree to another tree.
void copyTree(DListNode<T>* &copyRoot,
DListNode<T>* otherTreeRoot)
{
if(otherTreeRoot == NULL)
{
copyRoot = NULL;
}
else
{
copyRoot = new DListNode<T>();
copyRoot->setData(otherTreeRoot->getData());
copyTree(copyRoot->getFirstLink(), otherTreeRoot->getFirstLink());
copyTree(copyRoot->getLastLink(), otherTreeRoot->getLastLink());
}
}
// function to delete a node.
void destroy(DListNode<T>* Node)
{
if(Node != NULL)
{
destroy(Node->getFirstLink());
destroy(Node->getLastLink());
delete Node;
Node = NULL;
}
}
// inorder traversal function
void inorderTraverlsal(DListNode<T>* node)
{
if(node != NULL)
{
inorderTraverlsal(node->getFirstLink());
cout << node->getData() << " ";
inorderTraverlsal(node->getLastLink());
}
}
// pre-order traversal function
void preorderTraversal(DListNode<T>* node)
{
if(node != NULL)
{
cout << node->getData() << " ";
preorderTraversal(node->getFirstLink());
preorderTraversal(node->getLastLink());
}
}
// post-order traversal function
void postOrderTraversal(DListNode<T>* node)
{
if(node != NULL)
{
postOrderTraversal(node->getFirstLink());
postOrderTraversal(node->getLastLink());
cout << node->getData() << " ";
}
}

int height(DListNode<T>* &p)
{
if (p == NULL)
{
return 0;
}
else
{
int X = height(p->getFirstLink());
int Y = height(p->getLastLink());
return 1 + Max(X,Y);
}
}
// returns the bigger value of x or y depending which is bigger.
int Max(int x, int y)
{
if(x >= y)
return x;
else
return y;
}

// gets the node count
int nodeCount(DListNode<T>& node)
{
/*
if(node == NULL)
{
return 0;
}
else
{
if(node->getFirstLink() == NULL && node->getLastLink() == NULL)
{
return 1;
}
else
return (1 + nodeCount(node.getFirstLink()) + nodeCount(node.getLastLink()));
}*/
}
// get leaf count
int leafCount(const DListNode<T>* &p)
{
}
};
#endif
[/CODE]

Now, the functions height and getTreeheight return this weird error which makes no sense what so ever to me.:

[CODE]
1>c:\users\tim sweeny\documents\visual studio 2008\projects\x\datastructures\binarytree.h(66) : error C2662: 'BinaryTree<T>::height' : cannot convert 'this' pointer from 'const BinaryTree<T>' to 'BinaryTree<T> &'
[/CODE]

So yea, this is really making me angry like the hulk *Enerjak SMASH*

Share this post


Link to post
Share on other sites
Advertisement
This looks just like the problem I had when I took a data structures class at Full Sail.
The problem is that you're taking in a constant but returning a reference (or vise versa) it's hard to tell since this is your BST.cpp and I can't see where you're calling it in main.cpp or wherever you do the calling. But to be honest, the best way to solve this is by switching around some constants.

but yeah, whenever you see an error that says "cannot convert from (something) to (something different) it generally means you put a different object type in a parameter, or a return value is different, or something not matching a function. Like, if a function returns an integer, and you set a char pointer to it. or if the first parameter of a function takes in a string, and you give it an unsigned short. Not that extreme, but you get the point.

Wish I could help more, but I'd need to see wherever you're calling getTreeheight.

Share this post


Link to post
Share on other sites
[font=courier new,courier,monospace]int getTreeNodeCount() const[/font] is marked as [font=courier new,courier,monospace]const[/font] (i.e. it guarantees it won't modify the object). It attempts to call [font=courier new,courier,monospace]int nodeCount(DListNode<T>& node)[/font], which is not marked as [font=courier new,courier,monospace]const[/font], and therefore cannot guarantee the object isn't modified (thus it tries to convert a [font=courier new,courier,monospace]const this[/font] to a [font=courier new,courier,monospace]non-const this[/font]) ([font=courier new,courier,monospace]int getTreeHeight() const[/font] also has this problem, and other functions may too, which I don't have time to validate). If [font=courier new,courier,monospace]getTreeNodeCount()[/font] is to remain [font=courier new,courier,monospace]const[/font], [font=courier new,courier,monospace]nodeCount(DListNode<T>& node)[/font] needs to be marked as [font=courier new,courier,monospace]const[/font] (and should probably take a [font=courier new,courier,monospace]const DListNode<T>&[/font], or rather it should probably take a [font=courier new,courier,monospace]const DListNode<T>*[/font]).

Also, note that [font=courier new,courier,monospace]nodeCount()[/font] takes a [font=courier new,courier,monospace]DListNode<T>&[/font], but [font=courier new,courier,monospace]rootNode[/font] is a [font=courier new,courier,monospace]DListNode<T>*[/font]. They're not the same thing.

But that error doesn't match the file you posted. It says the error is on line 66 and is with [font=courier new,courier,monospace]BinaryTree<T>::height[/font], but line 66 is [font=courier new,courier,monospace]int getTreeNodeCount() const[/font][font=arial,helvetica,sans-serif].[/font]

[font=arial,helvetica,sans-serif]And there's no reason [/font][font=courier new,courier,monospace]int height(DListNode<T>* &p)[/font] should take a reference to a pointer. Just taking a pointer would suffice. Edited by Cornstalks

Share this post


Link to post
Share on other sites
OK, i fixed it, now I have a question: as you can see in the nodecount function, i count how many nodes are in the three. Now is the leaf counter the same as the node counter? or is it a little different? I mean seems it's just like the getTreeNodeCount(). thank you in advanced. to the guy whose going to full sail, You know Wendy Jones?

Share this post


Link to post
Share on other sites
[quote name='Enerjak' timestamp='1338261481' post='4944228']
OK, i fixed it, now I have a question: as you can see in the nodecount function, i count how many nodes are in the three. Now is the leaf counter the same as the node counter? or is it a little different?
[/quote]
They should be different. A node is just any node in the tree. A leaf is a special kind of node in a tree. A leaf is a node with no children.

Share this post


Link to post
Share on other sites
would this be a good way?

[CODE]
// get leaf count
int leafCount(DListNode<T>* p) const
{
int leaf = 0;
if(p != NULL)
{
if(p->getFirstLink() == NULL && p->getLastLink() == NULL)
{
leaf++;
}
else
{
return 1 + leafCount(p->getFirstLink()) + leafCount(p->getLastLink());
}
}
}
[/CODE]

Hmmm, what I'm doing is studying data structures my self so i will be better prepared when taking a class on them. thanks

Share this post


Link to post
Share on other sites
I won't give you code to fix this or tell you exactly what's wrong, because I want you to think about it. You'll learn more that way.

Look at [font=courier new,courier,monospace]leaf[/font]. Why is it there? What do you use it for? What does it [i]accomplish[/i]? You [i]write[/i] to it, but do you ever [i]read[/i] from it? What happens when [font=courier new,courier,monospace]leafCount()[/font] calls itself again? What does [font=courier new,courier,monospace]leaf++[/font] accomplish [i]in the end[/i]?

What happens if [font=courier new,courier,monospace]p[/font] is [font=courier new,courier,monospace]NULL[/font]? What does the function return?

What happens in the line [font=courier new,courier,monospace]1 + leafCount(p->getFirstLink()) + leafCount(p->getLastLink())[/font]? More specifically, why is there the [font=courier new,courier,monospace]1[/font] there? The [font=courier new,courier,monospace]if[/font] statement checks if the node is a leaf, and if it's not (the [font=courier new,courier,monospace]else[/font] part), why are you adding [font=courier new,courier,monospace]1[/font] as if it were a leaf?

Answer each of these questions as best as you can, revise your function, and post it again for more feedback :)

Share this post


Link to post
Share on other sites
[CODE]
// get leaf count
int leafCount(DListNode<T>* p) const
{
int leaf = 0;
if(p == NULL)
return 0;
if(p->getFirstLink() == NULL && p->getLastLink() == NULL)
{
return 1;
}
else
{
return leafCount(p->getFirstLink()) + leafCount(p->getLastLink());
}
[/CODE]

seems lagit

Share this post


Link to post
Share on other sites
Ok, there was this programming exercise in this book i got that asked me to create a function to return the number of nodes that have only one child. Now, i tried to do it off the time of my head and came up with this:

[CODE]
// gets the node count BUT only those nodes that have one leaf.
int getNodeCount(DListNode<T>* node) const
{
if(node == NULL)
{
return 0;
}
else
{
if(node->getFirstLink() != NULL && node->getLastLink() == NULL)
{
return 1;
}
else if(node->getFirstLink() == NULL && node->getLastLink() != NULL)
{
return 1;
}
else
{
int x = getNodeCount(node->getFirstLink());
int y = getNodeCount(node->getLastLink());
return (1 + x + y);
}
}
}
[/CODE]

not sure if it worked.

Share this post


Link to post
Share on other sites
In the first one, the variable [font=courier new,courier,monospace]leaf[/font] is unnecessary. It is never used, and can be taken out. Other than that, it looks correct.

The second one is not quite correct, however. There are two problems. First, a leaf is a node where [i]both[/i] children are [font=courier new,courier,monospace]NULL[/font] (that is, it has [i]no[/i] children). If a node has one or more children, it is [i]not[/i] a leaf. Your [font=courier new,courier,monospace]if[/font] statements ([font=courier new,courier,monospace](node->getFirstLink() != NULL && node->getLastLink() == NULL)[/font] and [font=courier new,courier,monospace](node->getFirstLink() == NULL && node->getLastLink() != NULL)[/font]) check if the node has one child. They do not check if it has [i]no[/i] children (which would be the proper check). You should check if [i]both[/i] children are [font=courier new,courier,monospace]NULL[/font], and if so [font=courier new,courier,monospace]return 1[/font]. You should not have two [font=courier new,courier,monospace]if[/font] statements either.

The second problem is the last return value, [font=courier new,courier,monospace]return (1 + x + y)[/font]. Why is that [font=courier new,courier,monospace]1[/font] there? If you reach this statement, it's clear the node is not a leaf, and so should not [font=courier new,courier,monospace]return (1 + x + y)[/font], but instead should just [font=courier new,courier,monospace]return x + y[/font].

Whenever I write an algorithm or data structure, I like to verify it on paper. So in your case, I would draw a binary tree on some paper, and then "run" the function by hand and see if I got the right answer.

[code]
A
/ \
B C
/ \ /
D E F
[/code]

Try running your function on that tree (by hand!) and see if you get the correct answer of 3. Edited by Cornstalks

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement