Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 Enerjak   Members   -  Reputation: 233

Like
0Likes
Like

Posted 28 May 2012 - 08:03 PM

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

#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

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

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> &'

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

Sponsor:

#2 kbenderoth89   Members   -  Reputation: 123

Like
1Likes
Like

Posted 28 May 2012 - 08:51 PM

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.

#3 Cornstalks   Crossbones+   -  Reputation: 6991

Like
3Likes
Like

Posted 28 May 2012 - 09:01 PM

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

Also, note that nodeCount() takes a DListNode<T>&, but rootNode is a DListNode<T>*. 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 BinaryTree<T>::height, but line 66 is int getTreeNodeCount() const.

And there's no reason int height(DListNode<T>* &p) should take a reference to a pointer. Just taking a pointer would suffice.

Edited by Cornstalks, 28 May 2012 - 09:14 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#4 Enerjak   Members   -  Reputation: 233

Like
0Likes
Like

Posted 28 May 2012 - 09:18 PM

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?

#5 Cornstalks   Crossbones+   -  Reputation: 6991

Like
1Likes
Like

Posted 28 May 2012 - 09:22 PM

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?

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.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#6 Enerjak   Members   -  Reputation: 233

Like
0Likes
Like

Posted 28 May 2012 - 10:00 PM

would this be a good way?

// 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());
   }
  }
}

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

#7 Cornstalks   Crossbones+   -  Reputation: 6991

Like
0Likes
Like

Posted 29 May 2012 - 09:19 AM

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 leaf. Why is it there? What do you use it for? What does it accomplish? You write to it, but do you ever read from it? What happens when leafCount() calls itself again? What does leaf++ accomplish in the end?

What happens if p is NULL? What does the function return?

What happens in the line 1 + leafCount(p->getFirstLink()) + leafCount(p->getLastLink())? More specifically, why is there the 1 there? The if statement checks if the node is a leaf, and if it's not (the else part), why are you adding 1 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 :)
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#8 Enerjak   Members   -  Reputation: 233

Like
0Likes
Like

Posted 29 May 2012 - 03:04 PM

// 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());
  }

seems lagit

#9 Enerjak   Members   -  Reputation: 233

Like
0Likes
Like

Posted 29 May 2012 - 03:36 PM

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:

// 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);
   }
  }
}

not sure if it worked.

#10 Cornstalks   Crossbones+   -  Reputation: 6991

Like
0Likes
Like

Posted 30 May 2012 - 09:16 AM

In the first one, the variable leaf 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 both children are NULL (that is, it has no children). If a node has one or more children, it is not a leaf. Your if statements ((node->getFirstLink() != NULL && node->getLastLink() == NULL) and (node->getFirstLink() == NULL && node->getLastLink() != NULL)) check if the node has one child. They do not check if it has no children (which would be the proper check). You should check if both children are NULL, and if so return 1. You should not have two if statements either.

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

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.

   A
 /   \
 B    C
/ \   /
D E  F

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

Edited by Cornstalks, 30 May 2012 - 09:17 AM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS