• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Enerjak

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

9 posts in this topic

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*
0

Share this post


Link to post
Share on other sites
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.
1

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?
0

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.
1

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
0

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 :)
0

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
0

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.
0

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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0