考察数据结构——第三部分：二叉树和BSTs[译]相关文档 原文链接：Part3: Binary Trees and BSTs
本文是 "考察数据结构"系列文章的第三部分，讨论的是.Net Framework基类库没有包括的常用数据结构：二叉树。就像线形排列数据的数组一样，我们可以将二叉树想象为以二维方式来存储数据。其中一种特殊的二叉树，我们称为二叉搜索树（binary search tree），简称为BST，它的数据搜索能力比一般数组更加优化。 目录： 简介 在树中排列数据 理解二叉树 用BSTs改善数据搜索时间 现实世界的二叉搜索树 简介： 在本系列的第一部分，我们讲述了什么是数据结构，怎么评估它们的性能，以及怎样根据其性能选择具体的数据结构来处理特定的算法。另外，我们复习了数据结构的基础知识，了解了最常用的数据结构——数组及与其相关的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 创建好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中； 2、 比较c和n的值； 3、 如果值相同，则找到了指定节点n； 4、 如果n的值小于c，那么如果n存在，必然在c的左子树中。因此回到第一步，将c的左孩子作为c； 5、 如果n的值大于c，那么如果n存在，必然在c的右子树中。因此回到第一步，将c的右孩子作为c； 分析BST搜索算法 通过BST查找节点，理想情况下我们需要检查的节点数可以减半。如图六的BST树，包含了15个节点。从根节点开始执行搜索算法，第一次比较决定我们是移向左子树还是右子树。对于任意一种情况，一旦执行这一步，我们需要访问的节点数就减少了一半，从15降到了7。同样，下一步访问的节点也减少了一半，从7降到了3，以此类推。
图六 这里一个重要概念就是算法的每一步在理想状态下都将使被访问的节点数减少一半。比较一下数组的搜索算法。搜索数组时，要搜索所有所有元素，每个元素搜索一次。也就是说，搜索有n个元素的数组，从第一个元素开始，我们要访问n-1个元素。而有n个节点的二叉搜索树，在访问了根节点后，只需要再搜索n/2个节点。 搜索二叉树与搜索排序数组相似。例如，你要在电话薄中查找是否有John King。你可以从电话薄的中间开始查找，即从以M开头的姓氏开始查找。按照字母顺序，K是在M之前，那么你可以将M之前的部分在折半，此时，可能是字母H。因为K是在H之后，那么再将H到M这部分折半。这次你找到了字母K，你可以马上看到电话薄里有没有James King。 搜索BST与之相似。BST的中点是根节点。然后从上到下，浏览你所需要的左孩子或右孩子。每一步都将节约一半的搜索时间。根据这一特点，这个算法的时间复杂度应该是log2n，简写为log n。回想我们在第一部分讨论的数学问题，log2n = y，相当于2y = n。即，节点数增加n，搜索时间只缓慢地增加到log2n。图七表示了log2n和线性增长的增长率之间的区别。时间复杂度为log2n的算法运行时间为下面那条直线。
图七 可以看出，这条对数曲线几乎是水平线，随着N值的增加，曲线增长缓慢。举例来说吧，搜索一个具有1000个元素的数组，需要查询1000个元素，而搜索一个具有1000个元素的BST树，仅需要查询不到10个节点（log10 1024 = 10）。 在分析BST搜索算法中，我不断地重复“理想地（ideally）”这个字眼儿。这是因为BST实际的搜索时间要依赖于节点的拓扑结构，也就是说节点之间的布局关系。象图六中所示的二叉树，每一步比较操作都可以使搜索时间减半。然而，我们来看看图八所示的BST树，它的拓扑结构是与数组的排列方式是同构的。
图八 搜索图八中的BST树，仍然要耗费线性时间，因为每比较一步，都紧紧减少了一个节点，而非像图六中那样减半。 因此，搜索BST所耗费的时间要依赖于它的拓扑结构。最佳情况下，耗费时间为log2 n，最坏情况则要耗费线性时间。在下一节我们将看到，BST的拓扑结构与插入节点的顺序有关。因此，插入节点的顺序将直接影响BST搜索算法的耗时。 插入节点到BST中 我们已经知道了在BST中查询一个特定节点的方法，但是我们还应该掌握插入一个新节点的方法。向二叉搜索树插入一个新节点，不能任意而为，必须遵循二叉搜索树的特性。 通常我们插入的新节点都是作为叶节点。唯一的问题是，怎样查找合适的节点，使其成为这个新节点的父节点。与搜索算法相似，我们首先应该比较节点c和要插入的新节点n。我们还需要跟踪节点c的父节点。初始状态下，c节点为树的根节点，父节点为null。定位一个新的父节点遵循如下算法： 1、 如果c指向null，则c节点作为n的父节点。如果n的值小于父节点值，则n为父节点新的左孩子，否则为右孩子； （译注：原文为If c is a null reference,then parent will be the parent of n.. If n’s value is less than parent’s value,then n will be parent’s new left child; otherwise n will be parent’s new right child. 那么翻译过来就是如果c的值为空，当前父节点为n的父节点。笔者以为这似乎有误。因为如果c值为空，则说明BST树为空，没有任何节点，此时应为后面讲到的特殊情况。如果是说c指向null。那么说明c为叶节点，则新插入的节点应作为c的孩子。即c作为n的父节点，也不是原文所说的c的父节点作为n的父节点） 2、 比较n和c的值； 3、 如果c等于n，则用于试图插入一个相同的节点。此时要么直接抛弃该节点，要么抛出异常。（注意，在BST中节点的值必须是唯一的。） 4、 如果n小于c，则n必然在c的左子树中。让父节点等于c，c等于c的左孩子，返回到第一步。 5、 如果n大于c，则n必然在c的右子树中。让父节点等于c，c等于c的右孩子，返回到第一步。 当合适的叶节点找到后，算法结束。将新节点放到BST中使其成为父节点合适的孩子节点。插入算法中有种特例需要考虑。如果BST树中没有根节点，则父节点为空，那么添加新节点作为父节点的孩子这一步就忽略。而且在这种情况下，BST的根节点必须分配为新节点。 图九描述了BST插入算法：
图九 BST插入算法和搜索算法时间复杂度一样：最佳情况为log2 n，最坏情况为线性时间。之所以相同，是因为它为插入的新节点定位所采取的策略是一致的。 节点插入顺序决定BST的拓扑结构 既然新插入的节点是作为叶节点插入的，则插入的顺序将直接影响BST自身的拓扑结构。例如，我们依次插入节点：1，2，3，4，5，6。当插入节点1时，作为根节点。接着插入2作为1的右孩子，插入3作为2的右孩子，4作为3的右孩子，以此类推。结果BST就形成如图八那样的结构。 如果我们有技巧地排列插入值1，2，3，4，5，6的顺序，则BST树将伸展得更宽，看起来更像图六所示的结构。理想的插入顺序是：4，2，5，2，3，6。这样将4作为根节点，2作为4的左孩子，5作为4的右孩子，1和3分别作为2的左孩子和右孩子。而6则作为5的右孩子。 既然BST的拓扑结构将影响搜索、插入和删除（下一节介绍）操作的时间复杂度，那么以升序或降序（或近似升序降序）的方式插入数据，会极大地破坏BST的效率。在本文的后面将详细地讨论。 从BST中删除节点 从BST中删除节点比之插入节点难度更大。因为删除一个非叶节点，就必须选择其他节点来填补因删除节点所造成的树的断裂。如果不选择节点来填补这个断裂，那么二叉搜索树就违背了它的特性。例如，图六中的二叉搜索树。如果删除节点150，就需要某些节点来填补删除造成的断裂。如果我们随意地选择，比如选择92，那么就违背了BST的特性，因为这个时候节点95和111出现在了92的左子树中，而它们的值是大于92的。 删除节点算法的第一步是定位要删除的节点。这可以使用前面介绍的搜索算法，因此运行时间为log2 n。接着应该选择合适的节点来代替删除节点的位置，它共有三种情况需要考虑，在后面的图十有图例说明。 情况1：如果删除的节点没有右孩子，那么就选择它的左孩子来代替原来的节点。二叉搜索树的特性保证了被删除节点的左子树必然符合二叉搜索树的特性。因此左子树的值要么都大于，要么都小于被删除节点的父节点的值，这取决于被删除节点是左孩子还是右孩子。因此用被删除节点的左子树来替代被删除节点，是完全符合二叉搜索树的特性的。 情况2：如果被删除节点的右孩子没有左孩子，那么这个右孩子被用来替换被删除节点。因为被删除节点的右孩子都大于被删除节点左子树的所有节点。同时也大于或小于被删除节点的父节点，这同样取决于被删除节点是左孩子还是右孩子。因此，用右孩子来替换被删除节点，符合二叉搜索树的特性。 情况3：最后，如果被删除节点的右孩子有左孩子，就需要用被删除节点右孩子的左子树中的最下面的节点来替代它，就是说，我们用被删除节点的右子树中最小值的节点来替换。 注意：我们要认识到，在BST中，最小值的节点总是在最左边，最大值的节点总是在最右边。 因为替换选择了被删除节点右子树中最小的一个节点，这就保证了该节点一定大于被删除节点左子树的所有节点，同时，也保证它替代了被删除节点的位置后，它的右子树的所有节点值都大于它。因此这种选择策略符合二叉搜索树的特性。 图十描述了三种情况的替换选择方案
图十 和搜索、插入算法一样，删除算法的运行时间与BST的拓扑结构有关。理想状态下，时间复杂度为log2 n，最坏情况下，耗费的为线性时间。 BST节点的遍历 对于线性的连续的数组元素，采用的是单向的迭代法。从第一个元素开始，依次向后迭代每个元素。而BST则有三种常用的遍历方式： 1、 前序遍历（Perorder traversal） 2、 中序遍历（Inorder traversal） 3、 后序遍历（Postorder traversal） 当然，这三种遍历工作原理几乎相似。它们都是从根节点开始，然后访问其子节点。区别在于遍历时，访问节点本身和其子节点的顺序不同。为帮助理解，我们看看图十一所示的BST树。（注意图六和图十一所示的BST树完全相同。
图十一 前序遍历 前序遍历从当前节点（节点c）开始，然后访问其左孩子，再访问右孩子。如果从BST树的根节点c开始，算法如下： 1、 访问c。（这里所谓访问时指输出节点的值，并将节点添加到ArrayList中，或者其它地方。这取决于你遍历BST的目的。） 2、 对c的左孩子重复第一步； 3、 <%2 |
|
|
