trees part 1.html

游戏开发数据结构Data Structures for Game Programmers The Goodies Directory contains all sorts of stuff. For

//  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) );
};
</PRE></BLOCKQUOTE>
<P>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抯 all of it抯 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.</P>
<P>Since the tree will be using a linked list to store it抯 children, the tree 
maintains a pointer (known as the <B><I>iterator</B></I>) to the current child. 
The basic iteration functions allow the user to reset the pointer to the start 
of the list (<B><I>start()</B></I>), travel through each child individually 
(<B><I>forth()</B></I>), retrieve the item at the current child iterator 
location (<B><I>currentChild()</B></I>), delete the current child subtree 
(<B><I>removeChild()</B></I>), and determine if the iterator is not pointing to 
a valid child (<B><I>isValid()</B></I>).</P>
<P>The Traversal methods will be discussed later on in this tutorial.</P>
<H1>Adding Nodes to the General Tree</H1>
<P>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.</P>
<P>Example of adding nodes to a linked tree:</P>
<BLOCKQUOTE><PRE class=code>void main()
{
  GeneralTree&lt;int&gt;* tree = new GeneralTree&lt;int&gt;( 1 );
  GeneralTree&lt;int&gt;* temp = 0;

  tree-&gt;addChild( new GeneralTree&lt;int&gt;( 2 ) );
  tree-&gt;addChild( new GeneralTree&lt;int&gt;( 3 ) );
  tree-&gt;addChild( new GeneralTree&lt;int&gt;( 4 ) );

  tree-&gt;start();
  temp = tree-&gt;child();
  temp-&gt;addChild( new GeneralTree&lt;int&gt;( 5 ) );
  temp-&gt;addChild( new GeneralTree&lt;int&gt;( 6 ) );

  tree-&gt;forth();
  tree-&gt;forth();
  temp = tree-&gt;child();
  temp-&gt;addChild( new GeneralTree&lt;int&gt;( 7 ) );
}
</PRE></BLOCKQUOTE>
<P>This snippet creates the tree that was given as an example of a general tree 
earlier using <B><I>Top Down</B></I> 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抯 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 
<B><I>Bottom Up</B></I> construction.</P>
<H1>Removing Nodes from the General Tree</H1>
<P>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 
<B><I>removeChild()</B></I> 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.</P>
<BLOCKQUOTE><PRE class=code>void main()
{
  GeneralTree&lt;int&gt;* tree = new GeneralTree&lt;int&gt;( 1 );

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

  tree-&gt;start();
  tree-&gt;removeChild();
}
</PRE></BLOCKQUOTE>
<P>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.</P>
<H1>Processing Nodes in the General Tree</H1>
<P>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 <B><I>Pre-Order Traversal </B></I>and the 
<B><I>Post-Order Traversal</B></I>. The third such traversal, 
<B><I>In-Order</B></I>, is usually only used on binary trees. These traversal 
methods are recursive functions, and demonstrate how useful recursion can 
be.</P>
<P>The Pre-Order Traversal works by processing the current node first, and then 
processing all the children, where <B><I>process() </B></I>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:</P>
<BLOCKQUOTE><PRE class=code>template &lt;class dataType&gt;
void GeneralTree&lt;dataType&gt;::preorder(void (*process)(dataType&amp; item) )
{
  process( m_data );
  start();
  while( isValid() )
  {
    currentChild-&gt;preorder( process );
    forth();
  }
}
</PRE></BLOCKQUOTE>
<P>So, printing the items of the family tree example above would produce the 
list: <I>Bob, Mary, Beth, James, John, Joe, Nick, Sam, Jo</I>. 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 <B><I>Pre</B> </I>ordering because it 
processes the root node before the children. This traversal is also known as the 
<B><I>Depth-First</B></I> traversal, because it traverses one path all the way 
to the bottom before it comes back up and follows a different path.</P>
<P>Now, since <I>Pre</I> ordering processes the root node first and the child 
second, <I>Post </I>ordering processes the children nodes first, and the root 
node last. The recursive algorithm for this is:</P>
<BLOCKQUOTE><PRE class=code>template &lt;class dataType&gt;
void GeneralTree&lt;dataType&gt;::postorder(void (*process)(dataType&amp; item) )
{
  start();
  while( isValid() )
  {
    currentChild-&gt;postorder( process );
    forth();
  }
  process( m_data );
}
</PRE></BLOCKQUOTE>
<P>Printing the items of the family tree using a Post-order would produce: 
<I>Beth, James, Mary, John, Sam, Jo, Nick, Joe, Bob</I>. 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.</P>
<H1>Why recursion was used in these traversals</H1>
<P>As I have said many times before, recursion is a powerful tool because it 
allows a large problem to be broken down into a much simpler problem. In the 
case of traversal, the beauty lies in being able to specify a small function 
which operates on only one node and allows the children to solve the problem for 
their children as well, thus allowing the root (or any parent node in the tree) 
to remain totally ignorant of the structure of its children. When you pre-order 
a tree, you process the root node, and then call preorder on each of it抯 
children. So when you preorder a child, it completes and pop抯 execution back up 
to the root, allowing it to do the same thing to the next child, then the next, 
and so forth.</P>
<P>While it is possible to represent the traversal problem with an iterative 
solution, that solution would require a custom made stack, which is esentially 
using recursion with a different name. It is likely that the user defined stack 
will not be as efficient as the system stack, so an iterative solution would end 
up being slower.</P>
<P>The importance of recursion is somewhat downplayed in the traversal routines 
because each tree node maintains a pointer to the current child. Now, imagine a 
general tree implementation that used an array for its child list instead of a 
linked list. An array does not have an iterator object, and must use an index 
variable instead. In this case recursion helps because the index is stored on 
the stack at every level, and automatically restored when execution returns to 
each higher level. Recursion essentially helps the algorithm remember which path 
it traveled down.</P>
<P>In the end, recursion works so well with tree抯 because a tree is esentially 
a recursive structure.</P>
<H1>Conclusion</H1>
<P>That's it for this tutorial. I had intended to include even more tree related 
stuff, all into one tutorial, but it ended up being too large. So next time, in 
part II, the tutorial will continue on with trees. Specifically, we'll be 
looking at binary trees, a specific subset of all trees, and the many various 
things that have been done with binary trees. I think I'll finish up at the 
third article, going into some of the more advanced tree structures. Until next 
time! </P>
<P align=center><B><A 
href="http://www.gamedev.net/community/forums/topic.asp?key=featart&amp;uid=1374&amp;forum_id=35&amp;Topic_Title=Trees+Part+1">Discuss 
this article in the Gamedev.net forums</A></B></P>
</BODY></HTML>