的数据结构——数组及与其相关的ArrayList。在第二部分，我们讲述了ArrayList的两个兄弟——堆栈和队列。它们存储数据的方式与ArrayList非常相似，但它们访问数据的方式受到了限制。我们还讨论了哈希表，它可以以任意对象作为其索引，而非一般所用的序数。
ArrayList，堆栈，队列和哈希表从存储数据的表现形式看，都可以认为是一种数组结构。这意味着，这四种数据结构都将受到数组边界的限制。回想第一部分所讲的，数组在内存中以线形存储数据，当数组容量到达最大值时，需要显式地改变其容量，同时会造成线形搜索时间的增加。
本部分，我们讲考察一种全新的数据结构——二叉树。它以一种非线性的方式存储数据。之后，我们还将介绍一种更具特色的二叉树——二叉搜索树（BST）。BST规定了排列树的每个元素项的一些规则。这些规则保证了BSTs能够以一种低于线形搜索时间的性能来搜索数据。
在树中排列数据
如果我们看过家谱，或者是一家公司的组织结构图，那么事实上你已经明白在树中数据的排列方式了。树由许多节点的集合组成，这些节点又有许多相关联的数据和“孩子”。子节点就是直接处于节点之下的节点。父节点则位于与节点直接关联的上方。树的根是一个不包含父节点的单节点。
图1显示了公司职员的组织结构图。
图一
例中，树的根为Bob Smith，是公司的CEO。这个节点为根节点是因为其上没有父亲。Bob Smith节点有一个孩子Tina Jones，公司总裁。其父节点为Bob Smith。Tina Jones有三个孩子： Jisun Lee, CIO Frank Mitchell, CFO Davis Johnson, VP of Sales
这三个节点的父亲都是Tina Jones节点。
所有的树都有如下共同的特性： 1、只有一个根；
2、除了根节点，其他所有节点又且只有一个父节点；
3、没有环结构。从任意一个节点开始，都没有回到起始节点的路径。正是前两个特性保证没有环结构的存在。
对于有层次关系的数据而言，树非常有用。后面我们会讲到，当我们有技巧地以层次关系排列数据时，搜索每个元素的时间会显著减少。在此之前，我们首先需要讨论的是一种特殊的树：二叉树。
理解二叉树
二叉树是一种特殊的树，因为它的所有节点最多只能有两个子节点。并且，对于二叉树中指定的节点，第一个子节点必须指向左孩子，第二个节点指向右孩子。如图二所示：
图二
二叉树（a）共有8个节点，节点1为根。节点1的左孩子为节点2，右孩子为节点3。注意，节点并不要求同时具有左孩子和右孩子。例如，二叉树（a）中，节点4就只有一个右孩子。甚至于，节点也可以没有孩子。如二叉树（b），节点4、5、6都没有孩子。
没有孩子的节点称为叶节点。有孩子的节点称为内节点。如图二，二叉树（a）中节点6、8为叶节点，节点1、2、3、4、5、7为内节点。
不幸的是，.Net Framework中并不包含二叉树类，为了更好地理解二叉树，我们需要自己来创建这个类。
第一步：创建节点类Node
节点类Node抽象地表示了树中的一个节点。认识到二叉树中节点应包括两个内容： 1、 数据；
2、 子节点：0个、1个、2个；
节点存储的数据依赖于你的实际需要。就像数组可以存储整型、字符串和其他类类型的实例一样，节点也应该如此。因此我们应该将节点类存储的数据类型设为object。
注意：在C# 2.0版中可以用泛型来创建强类型的节点类，这样比使用object类型更好。要了解更多使用泛型的信息，请阅读Juval Lowy的文章：An Introduction to C# Generics。
下面是节点类的代码：
public class Node {
private object data; private Node left, right;
#region Constructors
public Node() : this(null) {}
public Node(object data) : this(data, null, null) {} public Node(object data, Node left, Node right) {
this.data = data; this.left = left; this.right = right; }
#endregion
#region Public Properties public object Value { get {
return data; } set {
data = value; } }
public Node Left { get {
return left; }
set {
left = value; } }
public Node Right { get {
return right; } set {
right = value; } }
#endregion }
注意类Node有三个私有成员：
1、 data，类型为object：为节点存储的数据； 2、 left，Node类型：指向Node的左孩子； 3、 right，Node类型：指向Node的右孩子；
4、 类的其他部份为构造函数和公共字段，访问了这三个私有成员变量。注意，left和right
私有变量为Node类型，就是说Node类的成员中包含Node类的实例本身。
创建二叉树类BinaryTree