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

Adding Nodes to the General Tree

The most common way to add nodes to a general tree is to first find the desired parent of the node you want to insert, then add the node to the parent's child list. The most common implementations insert the nodes one at a time, but since each node can be considered a tree on its own, other implementations build up an entire sub-tree before adding it to a larger tree.

Example of adding nodes to a linked tree:

void main()
{
  GeneralTree<int>* tree = new GeneralTree<int>( 1 );
  GeneralTree<int>* temp = 0;

  tree->addChild( new GeneralTree<int>( 2 ) );
  tree->addChild( new GeneralTree<int>( 3 ) );
  tree->addChild( new GeneralTree<int>( 4 ) );

  tree->start();
  temp = tree->child();
  temp->addChild( new GeneralTree<int>( 5 ) );
  temp->addChild( new GeneralTree<int>( 6 ) );

  tree->forth();
  tree->forth();
  temp = tree->child();
  temp->addChild( new GeneralTree<int>( 7 ) );
}

This snippet creates the tree that was given as an example of a general tree earlier using Top Down construction, where the root is created first, and the children are added later. Another way would have been to create the children first and add the sub children to the root. Building order: create node’s 5 and 6, create node 2, add 5 and 6 to 2, create 3, create 7, create 4, add 7 to 4, create 1, and add 2, 3 and 4 to node 1. This method is called Bottom Up construction.

Removing Nodes from the General Tree

Removing a node is entirely dependant on the use of the tree. The typical method to remove a node from a general tree is to find the node you want to remove, and just delete it from the current list it is in (this is what the removeChild() function does). This will remove the entire sub-tree, however, and if you want to keep the removed node's children in the tree, its up to you to re-add them. Example of removing a sub-tree from the tree.

void main()
{
  GeneralTree<int>* tree = new GeneralTree<int>( 1 );

  // create tree used in previous example here
  // ...

  tree->start();
  tree->removeChild();
}

This removes the entire subtree starting at node 2, which ends up removing both nodes 5 and 6 from the tree as well. Note that this is the standard accepted behavior of a remove routine, since children of a node are assumed to be related to the parent in an important manner, and maintaining them in the tree without the parent usually does not make sense.

Processing Nodes in the General Tree

Often, there arises a need to perform one operation on every node of a tree. Therefore, we need to use a method that traverses the entire tree and visits every node. There are generally three traversal methods for trees that guarantee that every node will be visited, however only two of them are used for general trees. They are called the Pre-Order Traversal and the Post-Order Traversal. The third such traversal, In-Order, is usually only used on binary trees. These traversal methods are recursive functions, and demonstrate how useful recursion can be.

The Pre-Order Traversal works by processing the current node first, and then processing all the children, where process() may be any user defined function. The reason this works is because in recursion, I stated earlier that the computer remembers the current state of the tree, and even though processing goes down an unknown number of levels, you can be assuered that when processing returns to the first function, you can continue processing the tree as usual. The recursive algorithm looks like this:

template <class dataType>
void GeneralTree<dataType>::preorder(void (*process)(dataType& item) )
{
  process( m_data );
  start();
  while( isValid() )
  {
    currentChild->preorder( process );
    forth();
  }
}

So, printing the items of the family tree example above would produce the list: Bob, Mary, Beth, James, John, Joe, Nick, Sam, Jo. First it processes Bob, then processes each of his children. Mary is the first child, so she is processed and it goes down to the next level, where it processes Beth and James. Since they don't have children, it jumps back up to Mary, then sees she has no more children, and jumps up to Bob. It then processes Bob's next child, John, and continues with Joe. It is called Pre ordering because it processes the root node before the children. This traversal is also known as the Depth-First traversal, because it traverses one path all the way to the bottom before it comes back up and follows a different path.

Now, since Pre ordering processes the root node first and the child second, Post ordering processes the children nodes first, and the root node last. The recursive algorithm for this is:

template <class dataType>
void GeneralTree<dataType>::postorder(void (*process)(dataType& item) )
{
  start();
  while( isValid() )
  {
    currentChild->postorder( process );
    forth();
  }
  process( m_data );
}

Printing the items of the family tree using a Post-order would produce: Beth, James, Mary, John, Sam, Jo, Nick, Joe, Bob. If you have a firm grasp on recursion, this is quite easy to understand. If, however, this is all gibberish to you, I would suggest reading up on recursion, because in the next article, recursion is discussed more in depth, and you need to have at least a working understanding of the basic concepts.

Next : Conclusion