Sign in to follow this  

Binary Trees: Is My Logic Sound?

This topic is 3314 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

Okay, I've been looking into advanced classes and structures, which has led me to binary tree's. Can someone just read through my thought processes and logic, and tell me if i'm wrong, confused or actually learning something for once! I'll try and keep it short and precise. I'm using C++ and OpenGL. 1... Firstly, basics. This establishes a structure called Orbital, which an instance is called by ... Orbital dave; ... each structure will have space for 3 float variables ... x,y & z.
struct Orbital
{
  float x,y,z;
};

2... Okay, in regards to binary trees, when an instance of the Orbital structure is created, it'll have 3 float variables (I'll ignore this from now on) and a pointer to the parent structure (providing there is one), this would make a link upwards in a binary tree?
struct Orbital
{
  float x,y,z;
  Orbital *parent;
};

3... If I add a child then this would create a pointer to any posible children structures? To start with this would be NULL, until a child is added? Then I would have a (pointer) chain up and down the binary tree.
struct Orbital
{
  float x,y,z;
  Orbital *parent, *child;
};

4... If I wanted 2 children I could do it like this?
struct Orbital
{
  float x,y,z;
  Orbital *parent, *child1, *child2;
};

5... Or like this? Which would create an array of 2 children?
struct Orbital
{
  float x,y,z;
  Orbital *parent, *child[2];
};

My main concern is with how the binary tree connects together? And how to to create multiple children.

Share this post


Link to post
Share on other sites
Since you are doing a binary tree, the best solution is to have 2 pointers -- one for the left child, and one for the right child. They are usually called left and right child, because of the accepted convention for the representation of a binary tree, with a single node at the top called the "root", and nodes continuing downward from there.

Also, what you have so far is what would usually be called a "node" class. A node is what the tree is made out of, the branches, if you will. It is convenient to have a seperate class, called the "tree" class, that helps manage the tree as a whole (the "trunk" if you will). This saves you from having to write this functionality into your main program every time you want to use it.

Here is an example of the class setup you will want:



class tree;//forward declaration of the tree class

class node
{
friend class tree;//this tells the tree class it is OK to access the
//things in the private member area of the node class.
public:
node(float x, float y, float z);

setData(float x, float y, float z);

//whatever functions you want

private:
float x, y, z;
node * leftChild;
node * rightChild;

}

class tree
{
public:
tree();
~tree();//note that since you are playing with dynamic memory, (ie, using new/malloc)
//you will need to right a proper destructor for this class.
//remember that you need to call "delete" once for every time you call
//new or malloc. It is easy to write a destructor recursively.

addNode(float x, float y, float z);

//whatever functions you want

private:
node * root;


}




Also, if you want a more detailed look at a tree, here is a working templated left child-right sibling tree that I wrote last week for my current CS project to use:




using namespace std;


template <class T>
class tree;

class character;
class joint;

template <class T>
class node
{
friend class tree<T>;
friend class character;
friend class joint;

public:

node(T &newdata);
node(){leftChild = NULL; rightSibling = NULL;};

T get_data();
void set_data(T &data);

private:
T data;
node<T> * leftChild;
node<T> * rightSibling;

};

template <class T>
node<T>::node(T &newdata)
{
leftChild = NULL;
rightSibling = NULL;
data = newdata;
}

template <class T>
T node<T>::get_data()
{
return(data);
}

template <class T>
void node<T>::set_data(T &data)
{
data = data;
}



template <class T>
class tree
{
friend class character;
friend class joint;
public:
tree(){root = NULL;};
~tree();

void remove(node<T> * deleteThis);

node<T> * root;

};

template <class T>
tree<T>::~tree()
{
if(root != NULL)
delete(root);
}

template <class T>
void tree<T>::remove(node<T> * deleteThis)
{
if(deleteThis->leftChild != NULL)
remove(deleteThis->leftChild);

if(deleteThis->rightSibling != NULL)
remove(deleteThis->rightSibling);

delete deleteThis;
}




It is fairly general purpose, you will simply have to remove the friend class character from the two classes, and replace it with whatever class you want it use it for. If you don't want to have to keep declaring friend class, or want to use it outside a class, you'll have to write a new one, or implement an iterator. Sorry there are no comments, I wrote this quickly so I could get on with my actual project -- a skeletal animation system ;)

Share this post


Link to post
Share on other sites
Thank you for your help, I'll look through it and see from there. Also good luck with the skeletal animation ... I tried, succeeded, but didn't like it that much. So what i'm doing now is an attempt to learn about skeletal animation from scratch, by making a simple hierarchal system in the form of a solar system model. It makes sense in my head! Again cheers and good luck.

Share this post


Link to post
Share on other sites
Quote:
Original post by Captain P
I think the first issue here is: why use a binary tree? What criteria will you use to determine where to put your Orbitals in the tree? If you just want a hierarchical system. why restrict the number of children to only two?


That aside, the code provided by MortusMaximus is of questionable quality. I don't intend to be offensive here, I just want to point out a few flaws for educative purposes.

First, one of the main advantages of using templates is the type-independent code. This saves you the hassle of writing the same functionality for multiple types. Tying a template class closely to another class that has nothing to do with the generic functionality (Character / Joint) defeats that advantage. In this case, the only reason for this friendliness seems to be to access child nodes. The better solution is to let the Tree and Node classes provide access to these nodes, either by making their child node pointers public, or by providing functions that expose them.

Second, the Tree and Node classes can be merged together into one class. This class would provide methods to add and remove child nodes and to check for their existence. This can easily be done recursively until a leaf node is reached. Without such functionality, a binary tree is mostly useless.

Third, don't delete things you didn't create! It's pretty easy to break this binary tree by creating a node<T> on the stack and setting it as the root node, then calling remove on the tree. Auch! It's probably best to let the Node manage it's subnodes, new'ing subnodes whenever you add a T object to it, delete'ing them whenever you remove nodes (again, by specifying which T object should be removed from the tree, because that's what you're interested in, not the nodes themselves).

You have to tick the 'Check here to include your profile signature' box in order to append your signature to a post. Your link doesn't work though: it asks me to log in into Facebook.


Thanks for the tips about the sig. As for the code, I included a disclaimer that it was a hackjob I did in 20 minutes for the purpose of the project I was doing, and it works perfectly for my needs ;)

I merely provided it as an example of what a quick improvised tree might look like.

Also I see your point about the remove function -- however, it isn't really a problem unless you are actively TRYING to break it, and it will just leave all the nodes stranded. Heh.. I do see now that I forgot to set the root to private. That is indeed a rather severe error. Thanks for the feedback Captain P.

[Edited by - MortusMaximus on November 17, 2008 7:06:33 PM]

Share this post


Link to post
Share on other sites
I think the first issue here is: why use a binary tree? What criteria will you use to determine where to put your Orbitals in the tree? If you just want a hierarchical system. why restrict the number of children to only two?


That aside, the code provided by MortusMaximus is of questionable quality. I don't intend to be offensive here, I just want to point out a few flaws for educative purposes.

First, one of the main advantages of using templates is the type-independent code. This saves you the hassle of writing the same functionality for multiple types. Tying a template class closely to another class that has nothing to do with the generic functionality (Character / Joint) defeats that advantage. In this case, the only reason for this friendliness seems to be to access child nodes. The better solution is to let the Tree and Node classes provide access to these nodes, either by making their child node pointers public, or by providing functions that expose them.

Second, the Tree and Node classes can be merged together into one class. This class would provide methods to add and remove child nodes and to check for their existence. This can easily be done recursively until a leaf node is reached. Without such functionality, a binary tree is mostly useless.

Third, don't delete things you didn't create! It's pretty easy to break this binary tree by creating a node<T> on the stack and setting it as the root node, then calling remove on the tree. Auch! It's probably best to let the Node manage it's subnodes, new'ing subnodes whenever you add a T object to it, delete'ing them whenever you remove nodes (again, by specifying which T object should be removed from the tree, because that's what you're interested in, not the nodes themselves).


Quote:

I put it in my sig, but I can't see any sig for myself... Can you see it? :/ Maybe you can't see your own sig.

You have to tick the 'Check here to include your profile signature' box in order to append your signature to a post. Your link doesn't work though: it asks me to log in into Facebook.

Share this post


Link to post
Share on other sites
Quote:
Original post by MortusMaximus
As for the code, I included a disclaimer that it was a hackjob I did in 20 minutes for the purpose of the project I was doing, and it works perfectly for my needs ;)

I think it's better to provide no code than bad code, especially because this is the beginners section.

Quote:
Also I see your point about the remove function -- however, it isn't really a problem unless you are actively TRYING to break it, and it will just leave all the nodes stranded.

It's already a problem when you try to use the tree. A binary tree shouldn't leave it's node management to the user - that's what the tree is for. You have only provided a data struct here, but almost no functionality. Then, you hide the data (because it's OOP?), but, because that causes a usability problem, you add friend classes... and these friend classes have to do the node management, manually adding data to the tree, etc.

But wait, that is exactly what the binary tree should do... see, hiding data without providing functionality is useless. Making the Tree's root node private is not the only thing you should do: you should also provide Add and Remove functions, that internally add things to this root node. And whatever other functionality you need. Only then is making this root node private actually good, because now you provide functionality, without allowing the user to manually mess up with the internals of your tree (which is exactly why data hiding is useful).

Share this post


Link to post
Share on other sites

This topic is 3314 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.

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