Contents  Introduction  Recursion  Introduction to Trees  General Trees  Adding, Removing  and Processing  Nodes  Conclusion  Source code  Printable version  Discuss this article  in the forums The Series  Introduction  Binary Trees

General Trees

The General tree (also known as Linked Trees) is a generic tree that has one root node, and every node in the tree can have an unlimited number of child nodes. One popular use of this kind of tree is in Family Tree programs. Here's an example family tree:

Any parent node is allowed to have as many children as it wants. (Random fact: Johann Sebastian Bach had 19 children). The standard method of representing a general tree is to use a linked list (hence the name linked tree) in each node to hold pointers to all of the children. You don't need to use a linked list though, you can just as easily use a resizable array, or any other linear container structure you can think of, but a linked list is usually the easiest way to think about storing the child nodes of a general tree. A representation of a Linked General Tree using the above family tree example would look like this:

Each box is a linear container, and each node has a pointer to a single linear container.

Using The General Tree

So, what would you use a general tree for? In game programming, many games use these types of trees for decision-making processes. For example, a computer AI might need to make a decision based on an event that happened. Here's an example of a computer gunman thinking about what to do when he hears a gunshot:

This is just a simple tree for demonstration. A more complex AI decision tree would definitely have a lot more options. The great thing about using a tree for decision-making is that the options are cut down for every level of the tree you go down, greatly improving the speed at which the AI makes a decision. Other uses might include storing level progressions. In level based games, there is a strong push lately to get rid of the old school "linear" line of thinking, and instead of using just a rigid number of pre-defined levels, maybe the level structure of a game might progress based on a tree. The big problem with tree based level progressions, however, is that sometimes the tree can get much too large and complex. Imagine offering just two choices for the next level at the end of each level in a ten level game. That would require a total of 1023 levels to be created. That requires quite a bit of effort, so it's best to try to limit the number of level choices. There are thousands of other uses for trees, and chances are there is something you want to do that trees are the best solution for.

The General Tree Interface

Here is a listing of the basic public GeneralTree interface that I have created:

Template <class dataType>
class GeneralTree
{
// ----------------------------------------------------------------
//  Name:           GeneralTree::GeneralTree
//  Description:    Default Constructor. Creates a tree node.
//  Arguments:      - data: data to initialise node with
//  Return Value:   None.
// ----------------------------------------------------------------
  GeneralTree( dataType& data );


// ----------------------------------------------------------------
//  Name:           GeneralTree::~GeneralTree
//  Description:    Destructor. Deletes all child nodes.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
  ~GeneralTree();


// ----------------------------------------------------------------
//  Name:           GeneralTree::addChild
//  Description:    Adds a child node to the tree’s child list.
//  Arguments:      - tree: sub-tree to add
//  Return Value:   None.
// ----------------------------------------------------------------
  void addChild( GeneralTree<dataType>* tree );


// ----------------------------------------------------------------
//  Name:           GeneralTree::start
//  Description:    resets the child iterator to point to the first
//                  child in the current tree.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
  void start();


// ----------------------------------------------------------------
//  Name:           GeneralTree::forth
//  Description:    moves the child iterator forward to point to
//                  the next child.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
  void forth();


// ----------------------------------------------------------------
//  Name:           GeneralTree::isValid
//  Description:    determines if the child iterator points to a
//                  valid child.
//  Arguments:      None.
//  Return Value:   True if the iterator points to a valid child,
//                  False otherwise.
// ----------------------------------------------------------------
  bool isValid();


// ----------------------------------------------------------------
//  Name:           GeneralTree::currentChild
//  Description:    returns a pointer to the current child tree
//                  that the child iterator points to.
//  Arguments:      None.
//  Return Value:   pointer to current child tree
// ----------------------------------------------------------------
  GeneralTree<dataType>* currentChild();


// ----------------------------------------------------------------
//  Name:           GeneralTree::removeChild
//  Description:    removes the child that the child iterator
//                  is pointing tom and moves child iterator to
//                  next child.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
  void removeChild();


// ----------------------------------------------------------------
//  Name:           GeneralTree::preorder
//  Description:    processes the list using a pre-order traversal
//  Arguments:      - process: A function which takes a reference
//                             to a dataType and performs an
//                             operation on it.
//  Return Value:   None.
// ----------------------------------------------------------------
  void preorder( void (*process)(dataType& item) );


// ----------------------------------------------------------------
//  Name:           GeneralTree::postorder
//  Description:    processes the list using a post-order traversal
//  Arguments:      - process: A function which takes a reference
//                             to a dataType and performs an
//                             operation on it.
//  Return Value:   None.
// ----------------------------------------------------------------
  void postorder( void (*process)(dataType& item) );
};

There is no default constructor, because a tree object MUST contain a piece of data. Therefore you are required to pass in a dataType to it on creation. Note that the destructor of a tree recursively delete’s all of it’s children, so when adding a sub-tree to a tree, make sure it is not referenced anywhere else in the program. The destructor, however, does NOT delete the data stored inside the tree node, so that must be managed by the client of the tree.

Since the tree will be using a linked list to store it’s children, the tree maintains a pointer (known as the iterator) to the current child. The basic iteration functions allow the user to reset the pointer to the start of the list (start()), travel through each child individually (forth()), retrieve the item at the current child iterator location (currentChild()), delete the current child subtree (removeChild()), and determine if the iterator is not pointing to a valid child (isValid()).

The Traversal methods will be discussed later on in this tutorial.

Next : Adding, Removing, and Processing Nodes