📄 trees part 1.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>Trees Part 1</TITLE>
<META http-equiv=Content-Type content="text/html; charset=windows-1252">
<META content="MSHTML 6.00.2600.0" name=GENERATOR><LINK
href="Trees Part 1_files/reference.css" type=text/css rel=STYLESHEET><LINK
href="/pics/gdicon.png" type=image/png rel=icon>
<META DESCRIPTION=""></HEAD>
<BODY text=#000000 vLink=#666699 aLink=#000000 link=#666699 bgColor=#ffffff>
<TABLE cellSpacing=0 cellPadding=5 width="100%" border=0>
<TBODY>
<TR>
<TD class=tblhdr>Trees Part 1</TD>
<TD class=tblhdr align=right><IMG height=16
src="Trees Part 1_files/littleg.gif" width=16 align=absBottom> <A
href="http://www.gamedev.net/"><SPAN
style="COLOR: white; TEXT-DECORATION: none">GameDev.net</A></SPAN></TD></TR>
<TR>
Programming:Data Structures</A> </TD></TR></TBODY></TABLE>
<P align=center><SPAN class=title>Trees Part 1</SPAN> <BR><SPAN class=author>by
<A href="mailto:Rp242@hotmail.com">Ron Penton</A></SPAN></P>
<H1>Introduction</H1>
<P>Trees are a very important portion of software programming theory. Whether
you know it or not, they are used all around you, in many applications and
games. This is why it was quite a surprise to me when I found out that most of
the programmers that frequent the <A
href="http://www.gamedev.net/">GameDev.net</A> chat room don't know exactly what
trees are, and what they are good for. I hope this article will remedy that.</P>
<P>My original intent was to not provide any code for this tutorial, as I prefer
it when people learn the theory rather than just copy the code (and probably use
it for a computer science homework project), but I have come to realise that
quite a few of you learn better by seeing an example of the topic rather than
just an explanation. Therefore, I have included <A
href="Trees Part 1.zip">source
code and demo programs</A> to accompany this tutorial.</P>
<P>This specific tutorial briefly covers recursion first, because it is a very
important topic to understand before you get involved with trees. The next part
describes how a tree is structured and how parts of a tree are labelled, and the
last part shows how to use a General Tree.</P>
<P>Basic Requirements for this series:</P>
<BLOCKQUOTE>Knowledge of basic data structures:
<BLOCKQUOTE>Linked List <BR>Stack <BR>Queue <BR>Priority Queue
</BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>Knowledge of basic C++ programming:
<BLOCKQUOTE>inheritance <BR>templates <BR>function
pointers</BLOCKQUOTE></BLOCKQUOTE>
<P>Included Classes for this tutorial:</P>
<BLOCKQUOTE>LinkedList <BR>GeneralTree</BLOCKQUOTE>
<H1>Recursion</H1>
<P>Trees are highly recursive structures. I'm hoping that you will be somewhat
familiar with recursion as a theory, because it is a difficult subject to get
correct for most beginning programmers. Here is a tiny introduction to recursion
(you'll probably want to find a more in depth tutorial if you've never heard the
term before).</P>
<P>What is recursion? An old programmers joke has the definition of Recursion in
the dictionary as this:</P>
<BLOCKQUOTE><B>re穋ur穝ion </B><I>n</I>.: See <I>Recursion</I>. </BLOCKQUOTE>
<P>The basic idea behind a recursive function is one which calls itself
repeatedly on many different levels. A recursive structure, such as a tree, has
itself as its own children, and is thus considered recursive. Recursion helps
software engineers solve problems by dividing up complex problems into smaller
sub-problems, and is often a great boost in algorithm completion time, because
recursion helps to "divide and conquer" the problem at hand, thus reducing the
complexity. I will go into this further in the next tutorial dealing with binary
tree抯.</P>
<P>The basic recursive function will have two portions: the recursive part, and
the terminating part. It is very important that recursive functions have a
terminating part, because without it, the recursive function would never end.
The above joke is an example of recursion without a terminating condition. If it
were in a program, the program would continuously look up the definition of
recursion forever.</P>
<P>Of course, having a machine run into infinite recursion is just as deadly as
an infinite loop, but the difference between the two is that infinite recursion
will eventually cause the machine or thread to quit out. This is because each
recursive call allocates more information on the stack every time it is called,
and when the machine or thread runs out of stack space, it quits out.</P>
<P>The stack is the most important part of recursion. It is an easy way to have
the machine store current state information about a function, change to another
object, and then return at a later time. Let's look at a simple recursion
example:</P>
<BLOCKQUOTE><PRE class=code>int getPower( int number, int power )
{
if( power != 1 )
return number * getPower( number, power - 1 );
else
return number;
}
</PRE></BLOCKQUOTE>
<P>Here is the non-recursive solution to the same problem:</P>
<BLOCKQUOTE><PRE class=code>int getPower( int number, int power )
{
int result = number;
while( power > 1 )
{
result *= number;
power--;
}
return result;
}
</PRE></BLOCKQUOTE>
<P>While the recursive example looks ugly and stupid, and the iterative example
is far more efficient, it demonstrates an important idea behind recursion. The
terminating case is where power is 1. When power reaches 1, it returns a number
instead of calling itself again. The recursive portion of the function decides
to let the function handle the power one less than the current power, as long as
the current power is not 1. So if the function were to calculate 2 to the
<I>N</I>th power, it would first check to see if <I>N</I> was one, and if it
isn't, it asks for the solution to the problem of 2^(<I>N</I>-1), until it gets
to 2^1, in which case it returns 2. If <I>N</I> were 2, it would ask for 2^1 and
multiply that by 2, and return. If <I>N</I> were 3, it would ask for the
solution to 2^2 and muliply that by 2. That is the basis of recursion.</P>
<P>So why use it? If analyzed, the recursive getPower function is slower and
harder to understand than the non-recursive iterative solution, so it quite
obviously offers no advantage. Recursion is not used to its full potential in
this example simply because I wanted to show you how a problem can be broken
down into a smaller problem by using recursion (Look for tutorials on <I>The
Towers of Hanoi</I> problem for a really cool demonstration of this effect).</P>
<P>The real reason we would use recursion is for a simple way of storing values
on a 'path' for future use. Recursion store's the state of the algorithm at each
level and allows the user to come back to that exact state later on. We will see
this in use when using the tree traversal routines.</P>
<H1>Introduction to Trees</H1>
<P>Trees are used for so much in computer programming. They can be used for
improving database search times (binary search trees, 2-3 trees, AVL trees,
2-3-4 trees, red-black trees), Game programming (minimax trees, decision trees,
pathfinding trees), 3d graphics programming (BSP trees, quadtrees, octrees),
Arithmetic Scripting languages (arithmetic precedence trees), Data compression
(Huffman trees), and even file system's (B-trees, sparse indexed trees, trie
trees). This article will go through the basic tree structures first (general
trees), and then go into the specifics of some of the more popular trees, but
not all of those listed above. A few of the trees above are quite complex and go
beyond the scope of this article.</P>
<H1>Computer Representations of Trees</H1>
<P>Imagine a linked list. The simplest implementation uses only one class, a
<B><I>Node</B></I>, and each node points to the next node in the list. In more
sophisticated implementations, the node may even point to the previous node in
the list as well. This implementation treats any given node as the start of a
list when accessed externally by the client. The more abstracted implementations
use a general container class that points to its first node.</P>
<P align=center><IMG height=196 src="Trees Part 1_files/linkedlist.gif"
width=313></P>
<P>The box represents the Linked List class, and the circles are the nodes.
Trees are the same way in that they are made up of a collection of nodes. As
with linked lists, a tree can be referenced by any one of it抯 nodes, or a
general tree container class. Whichever implementation you choose is all up to
you and your needs. This tutorial does not assume one particular way over
another, but all tree diagrams I will draw in this document do not show the
container (box) class for reasons of clarity and brevity. It looks better
without the box getting in the way.</P>
<H1>Parts of a Tree</H1>
<P>Trees have one discrete starting point. This is called the <B><I>root
</B></I>node. As with a linked list, each node points to another node, but the
difference is that a tree node can point to more than one node, whereas a linked
list node can only point to one node. Each of the nodes that any given node
points to is called a <B><I>child </B></I>node, with the possible exception of a
<B><I>parent </B></I>node. Some tree implementations maintain pointers to their
parents to ease traversal, but it is not explicitly required by a tree. Any node
that does not have any children is called a <B><I>leaf </B></I>node. Here is a
pictorial representation of a theoretical tree:</P>
<P align=center><IMG height=189 src="Trees Part 1_files/Figure1-1.gif"
width=304></P>
<P>Note that computer trees are typically drawn from the Root-down. Node 1 would
be considered the <B><I>root</B></I>, and 2, 3, and 4 are <B><I>children
</B></I>of the root. Node 1 is their <B><I>parent</B></I>. Note also that node 2
is a <B><I>parent </B></I>to 5 and 6, and 4 is a <B><I>parent </B></I>to 7. Thus
nodes 2 and 4 act as both <B><I>children </B></I>and <B><I>parents</B></I>.
Nodes 3, 5, 6 and 7 are <B><I>leaf </B></I>nodes. It is important to note that
every node in the tree is also a tree by itself. We usually call these
<B><I>sub-trees</B></I>. Take, for example, node number 2. Node 2 is the root of
a sub-tree that only has three nodes. Node's 5, 6 and 7 are all sub-trees with
no children.</P>
<H1>Hierarchy of a tree</H1>
<P>When you think of a linked list, it is typically a long horizontal string of
nodes, each one connected to the next. This gives it a shape roughly analogous
to a straight memory array. However, trees cannot be easily thought of in terms
of a straight line, so a tree has what are called <B><I>Height Levels</B></I>.
The root node has a level of 0 (or 1, depending on how you count), and all
children of any given node have a height level of one greater than the parent.
All children of any given node have the same height level. </P>
<P>Here is an example of height levels:</P>
<P align=center><IMG height=237 src="Trees Part 1_files/levels.gif"
width=304></P>
<H1>General Trees</H1>
<P>The <B><I>General tree </B></I>(also known as <B><I>Linked Trees</B></I>) is
a generic tree that has one root node, and every node in the tree can have an
<B><I>unlimited </B></I>number of child nodes. One popular use of this kind of
tree is in Family Tree programs. Here's an example family tree:</P>
<P align=center><IMG height=285 src="Trees Part 1_files/family.gif"
width=480></P>
<P>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 <I>linked
tree</I>) 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:</P>
<P align=center><IMG height=285 src="Trees Part 1_files/figure1-3.gif"
width=480></P>
<P>Each box is a linear container, and each node has a pointer to a single
linear container.</P>
<H1>Using The General Tree</H1>
<P>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:</P>
<P align=center><IMG height=261 src="Trees Part 1_files/figure1-4.gif"
width=564></P>
<P>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.</P>
<H1>The General Tree Interface</H1>
<P>Here is a listing of the basic public GeneralTree interface that I have
created:</P>
<BLOCKQUOTE><PRE class=code>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抯 child list.
// Arguments: - tree: sub-tree to add
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -