创建好Node类后，紧接着创建BinaryTree类。BinaryTree类包含了一个私有字段——root——它是Node类型，表示二叉树的根。这个私有字段以公有字段的方式暴露出来。
BinaryTree类只有一个公共方法Clear()，它用来清除树中所有元素。Clear()方法只是简单地将根节点置为空null。代码如下： public class BinaryTree {
private Node root;
public BinaryTree() {
root = null; }
#region Public Methods public virtual void Clear() {
root = null; }
#endregion
#region Public Properties public Node Root { get {
return root; } set {
root = value; } }
#endregion }
下面的代码演示了怎样使用BinaryTree类来生成与图二所示的二叉树（a）相同的数据结构： BinaryTree btree = new BinaryTree(); btree.Root = new Node(1); btree.Root.Left = new Node(2); btree.Root.Right = new Node(3);
btree.Root.Left.Left = new Node(4); btree.Root.Right.Right = new Node(5);
btree.Root.Left.Left.Right = new Node(6); btree.Root.Right.Right.Right = new Node(7);
btree.Root.Right.Right.Right.Right = new Node(8);
注意，我们创建BinaryTree类的实例后，要创建根节点（root）。我们必须人工地为相应的左、右孩子添加新节点类Node的实例。例如，添加节点4，它是根节点的左节点的左节点，我们的代码是：
btree.Root.Left.Left = new Node(4);
回想一下我们在第一部分中提到的数组元素，使存放在连续的内存块中，因此定位时间为常量。因此，访问特定元素所耗费时间与数组增加的元素个数无关。
然而，二叉树却不是连续地存放在内存中，如图三所示。事实上，BinaryTree类的实例指向root Node类实例。而root Node类实例又分别指向它的左右孩子节点实例，以此类推。关键在于，
组成二叉树的不同的Node实例是分散地放在CLR托管堆中。他们没有必要像数组元素那样连续存放。
图三
如果我们要访问二叉树中的特定节点，我们需要搜索二叉树的每个节点。它不能象数组那样根据指定的节点直接访问。搜索二叉树要耗费线性时间，最坏情况是查询所有的节点。也就是说，当二叉树节点个数增加时，查找任意节点的步骤数也将相应地增加。
因此，如果二叉树的定位时间为线性，查询时间也为线性，那怎么说二叉树比数组更好呢？因为数组的查询时间虽然也是线性，但定位时间却是常量啊？是的，一般的二叉树确实不能提供比数组更好的性能。然而当我们有技巧地排列二叉树中的元素时，我们就能很大程度改善查询时间（当然，定位时间也会得到改善）。
用BSTs改善数据搜索时间
二叉搜索树是一种特殊的二叉树，它改善了二叉树数据搜索的效率。二叉搜索树有以下属性：对于任意一个节点n，其左子树下的每个后代节点的值都小于节点n的值；而其右子树下的每个后代节点的值都大于节点n的值。
所谓节点n的子树，可以将其看作是以节点n为根节点的树。因此，子树的所有节点都是节点n的后代，而子树的根则是节点n本身。图四演示了子树的概念和二叉搜索树的属性。
图四
图五显示了二叉树的两个例子。图右，二叉树（b），是一个二叉搜索树（BST），因为它符合二叉搜索树的属性。而二叉树（a），则不是二叉搜索树。因为节点10的右孩子节点8小于节点10，但却出现在节点10的右子树中。同样，节点8的右孩子节点4小于节点8，却出现在了它的右子树中。不管是在哪个位置，不符合二叉搜索树的属性规定，就不是二叉搜索树。例如，节点9的右子树只能包含值小于节点9的节点（8和4）。
图五
从二叉搜索树的属性可知，BST各节点存储的数据必须和另外的节点进行比较。给出任意两个节点，BST必须能够判断这两个节点的值是小于、大于还是等于。
现在，设想一下，我们要查找BST的某个特定的节点。例如图五中的二叉搜索树（b），我们要查找节点10。BST和一般的二叉树一样，都只有一个根节点。那么如果节点10存在于树中，搜索这棵树的最佳方案是什么？有没有比搜索整棵树更好的方法？
如果节点10存在于树中，我们从根开始。可以看到，根节点的值为7，小于我们要查找的节点值。因此，一旦节点10存在，必然存在其右子树。所以应该跳到节点11继续查找。此时，节点10小于节点11的值，必然存在于节点11的左子树中。移到节点11的左孩子，此时我们已经找到了目标节点，定位于此。
如果我们要查找的节点在树中不存在，会发生问题？例如我们查找节点9。重复上述操作，直到到达节点10，它大于节点9，那么如果节点9存在，必然是在节点10的左子树中。然而我们看到节点10根本就没有左孩子，因此节点9在树中不存在。
正式地，我们的搜索算法如下所示。假定我们要查找节点n，此时已指向BST的根节点。算法不断地比较数值的大小直到找到该节点，或指为空值。每一步我们都要处理两个节点：树中的节点c，要查找的节点n，并比较c和n的值。C的初始化值为BST根节点的值。然后执行以下步骤： 1、 如果c值为null，则n不在BST中；