声明
本文译自http://www.devx.com/dotnet/Article/37855/0的文章并略有改动以便于理解和学习，如果你对作者文章感兴趣，请访问该网站；如果作者不愿意本人翻译学习其文章，请来信告诉我：iamben250@126.com
导言
Visual Studio提供了足够的类，如集合（collection）、哈希表（hash tables）和字典（dictionaries),来实现各种形式的数据结构。树的每个节点可以有一个或多个的字节点，所以用来存储层次数据非常有用。很多.NET开发员使用TreeView控件或者XML对象来建立树,但是这两种方法都是本方法，而其会增加一些你不想要的麻烦。
建立树结构
通过本文，我们要来弄明白什么是树，如何建立一个树，如何维护树，以及如何将树运用于实际工作，如提取树或者以不同的序列列出树的项目。
在我们开始之前，先来复习一下关于树的术语。
树的有关术语
树的术语融合了园艺学和家谱学的相关内容。园艺学提供了一些关于树、节（点）、根、枝和叶的术语，而家谱学提供了诸如祖先、父、子的术语。
一个树由节（点）构成，而节点连接着枝。一个节点只有一个父节点，但每个节点可以有0个、1个或多个子节点。分枝是定向的，就是说可以根据分枝知道树的方向，所以你可以弄明白哪些是父节点，哪些是子节点。
没有父节点的节点就是根。树中除根节点之外的其他节点都直接或间接和根节点相连。正常情况下，当你画一个树时，你会把根面在上面，这和地上长的自然界的树的方向恰好相反；但是它便于我们分清子节点和父节点。
节点的度就是它拥有的子节点的数量。一个树的度等于拥有最大度的节点的度。度为2的树称为二叉树，度为3的树称为三叉树。度大于3的，人们通常成其为N叉树，如度为7的树就成为7重树。
在树的最底端的、没有子节点的节点成为叶节点。根据定义，叶节点的度为0。
节点的级别就是其与根节点的距离。一些人认为节点的级别就是节点和根节点之间枝的数量；另一些认为是节点的数量（包括该节点及根节点），结果其值别比前种算法大1。这两种方法的差别就是你是否考虑根节点，即你把根节点是称为1级或是0级（有点像美国英语和英国英语对floor的层数有不用的算法，前者为1后者为0层）。我采用将根节点视为1级的算法，并没有特别好的理由来解释。
整个树的高度或级别就是其有最高级别的叶节点的级别。
注意枝知能够连接父节点和子节点。枝不能连接“兄妹”节点（即相同父节点的节点），也不能连接不是同一“代”的节点。
该规则的一个结果就是，书不能有断点或循环。另一个结果是，从一个节点到另一个节点直接只有唯一的最短路径。为了找到这个最短路径，你可以从选定的开始节点出发，向上即根节点的方向寻找，当找到两个节点共用的一个祖先为止。你最终会找到这个共用的祖先，即使在过程中你可能会经过根节点。当年找到这个共用祖先时，你再沿着分枝向下找到目标节点。图1是一个简单的树。
在 图 1中, 你不难看出：
图 1. 巧妙的树：树是由枝条连接的节点组成
- 节点A是根节点（没有父节点）
- 节点 D、E、G、H和 I 是叶节点 (没有子节点，度数为0).
- 数的度为3，因为节点F有最多的子节点3个。.
- 树的高度是4，因为最远的叶(G、H和 I )在第四级的节点上
。
图 2. 二叉的乐趣: 在一个完整的二叉树中，每个非叶节点有且只有2个子节点，除了可能出现的单节点，如图中的F节点 - 从D节点到H节点的唯一最短路径是D—B—A—C—F—H。 (如果有兴趣你可以试着找出其他节点直接的唯一最短路径。)
- 在树的分枝中没有断点和循环。
一个完整的树，其每个节点要么具有树的完整的度（比如，尽可能多的子节点）要么没有子节点。
根据你处理树的需要，你只可以允许一个例外。在这种情况下，第二到最低级别具有所有右边的叶节点，而最有边的非叶节点所具有的子节点数可以少于允许的最大值。
比如，图2 是一个完整的二叉数。在该树中，每个非叶节点有两个子节点，除了F节点。
树的遍历
树的遍历就是访问树中每个节点的方法。当你要访问某个节点时，你可能会做这些事：画出该节点，将其名称写入字符串，在节点上设置一个参数或者其他你试图执行的运算。
遍历一个二叉树有三种标准的顺序：先根次序、内根次序和后根次序。根据对于每个节点编写的代码，你可以定义任何一种遍历方法。
在先根次序遍历中，你先访问节点然后再访问其子节点。其所以成为“先根次序”，就是因为你在访问子节点前须要访问自节点的父节点。
比如，我们来看图2。假如这次遍历要输出节点名称——这里是字母。如果你从根开始遍历，根据规则，首先访问根节点，所以你先要输出字母A，然后你才可访问A的子节点。
因此，你要访问节点B，并对B进行先根次序遍历。根据规则，你要输出B，并移向节点D。你输出D，并访问D的子节点。最后，当你访问节点H时，你已经到达一个叶节点，因此你只是输出H。正常情况下，你会访问节点的子节点但现在没有了，因此本次递归结束，你转回树的节点D。从节点B开始，你已经访问了节点D，因此你该访问其他子节点：节点E。这种过程一直这样持续，直到你访问了每个节点并将他们全部输出。
图3 来自图2，但是加了一些小数字，表示在先根次序遍历中，节点的访问次序。
 |
|
| 图3. 聪明的遍历: 先根次序遍历中，先访问节点，然后访问其子节点。 |
先根次序遍历的最终输出结构是：
A, B, D, H, I, E, J, K, C, F, L, G.
后根次序遍历和先根次序遍历相似，但是在访问节点前你要先访问该节点的子节点。这个练习较给读者去完成吧。你可以核对一下对于图2进行该遍历的结果： H, I, D, J, K, E, B, L, F, G, C, A.
最后一种类型的遍历和前两种遍历也相似，但是它总是先访问节点左边的子节点，然后是节点自身，最后是节点右边的子节点。图2执行该遍历的结果为： H, D, I, B, J, E, K, A, L, F, C, G.
分析和排序
学习如何分析树，来计算算数表达式，以及如何对数进行排序。
本文的开始就已经介绍的树的有关术语，并演示如何用Visual Basic 语言来建立一个简单的树。接着还解释了如何对树进行遍历，但真正实用的应用就是如何使一个树把自己画出来。如果你需要显示一个树，现在就非常熟练了，然后，我们必须知道，树的用途远不止此。
现在我们来解释说明如何使用树完成一些实际的工作。首先，要明白如何用树来分析算术表达式，然后讨论拍戏的树以及演示如何使用排序的树来建立一个简单的猜动物游戏。
计算表达式的值
你可以列出一个算术表达式来，如-2*(8+7)/-10 ，并画出该式的表达式树或者分析树。树内部的节点代表运算符如*、（）和.,叶节点代表数字，如2、80和3.14159265。
 |
|
| 图4. 表达式树: 该树表示算术表达式：-2*(8+7)/-10。 |
叶节点的值只是其本身数字的值。要得到非叶节点的值，你要计算其子节点的值并用适当的运算将其合并。
比如, 图4 是表达式-2*(8+7)/-10的分析树。最下面连个节点的值是8和7；其父节点值是8+7。如果你计算整个树后，就知道根节点的值是3。Making a parse tree evaluate itself is easy. The node class’s Evaluate function simply calls its children’s Evaluate function and then combines the results by using the appropriate operand. (More on this later.)
The tricky part is building the parse tree; you need to pick apart the expression and figure out what nodes to build to represent the expression’s pieces.
The example program EvaluateExpressions, which is available for download in Visual Basic and C# versions, uses an ExpressionNode class to represent the pieces of an expression. This class uses four variables to keep track of the sub-expression that it represents. Expression stores a string representing the node’s sub-expression. LeftChild and RightChild are references to ExpressionNode objects, which represent the node’s children in the tree. Op holds the node’s operand.
For example, the root node in Figure 1 has Expression = “-2*(8+7)/-10” and Op = “/”. The following code shows the ExpressionNode class's constructor. The code saves the node’s expression and sets its children to Nothing. It then calls the ParseExpression method to do all of the fun work.
评论