Archived

This topic is now archived and is closed to further replies.

Leadorn

BTree

Recommended Posts

Leadorn    100
Hi First of all what do you call a normal two child tree, is it BTree (Binarytree)? What should such a tree class include, what functions are commonly needed when using the tree class.

Share this post


Link to post
Share on other sites
Zipster    2359
It depends on what this binary tree stores and how you''re going to be using it. Typically, you might want an interating function that performs some operation on each node, a searching algorithm, an insertion and removal algorithm, etc. But I can''t tell you for sure.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Well, think about how a binary tree would be structured...

By its very name, a binary tree would have two leaves/branches at each branch. Therefore your basic structure could have a couple of pointers to it''s ''child'' nodes. Depending on the functionality you want in your tree you could also have pointers back up the tree to parent items, depending on how you want to use the tree.
Then, add the specific data to each node. Personally, I use a pointer to a separate data structure as it makes it easier to swap items when sorting etc.

struct TreeItem
{
void* data; // pointer to data

TreeItem* left; // left child node
TreeItem* right; // right child node

TreeItem* parent; // parent node
};

Your basic tree class would then have a TreeItem at it''s root, and the tree can then be built from there by adding nodes to the left/right pointers.

As for functionality, that really depends on what you are using it for and what data is contained in the tree.

This is a pretty basic example but it should give you an idea...

Share this post


Link to post
Share on other sites
Leadorn    100
Should i have functions like

SetRoot //Sets the *root
GoUp //Currect = Current->Parent;
GoRight //Current = Current->RChild;
GoLeft //Current = Current->LChild;
SetRight //Current->RChild = RChild;
SetLeft /Current->LChild = LChild

Or should all thease functions be a part of a iterator for the tree?

Share this post


Link to post
Share on other sites
jamessharpe    497
quote:
Original post by Anonymous Poster

struct TreeItem
{
void* data; // pointer to data

TreeItem* left; // left child node
TreeItem* right; // right child node

TreeItem* parent; // parent node
};




If you''re using C++ you should really code thia like this:


template<typename T>
class TreeItem
{
public:
T* data; // pointer to data


TreeItem<T>* left; // left child node

TreeItem<T>* right; // right child node


TreeItem<T>* parent; // parent node

};



Share this post


Link to post
Share on other sites