考察数据结构——第三部分:二叉树和BSTs[译]

Posted by

二叉搜索树或BST是一种流行的数据结构,用于保持元素的顺序。二叉搜索树是二叉树,其中左子节点的值小于或等于父节点,右子节点的值大于或等于父节点。由于它是二叉树,它只能有0,1或2个子节点。二叉搜索树之所以与众不同,是因为它能够减少诸如添加、删除和搜索(也称为插入、删除和查找)等基本操作的时间复杂性。在BST中,所有这些操作都可以在O时间内执行。这种速度提高的原因是由于二叉搜索树的独特属性,对于每个节点,左子节点中的数据小于,右子节点中的数据大于到所述节点中的数据。

小编整理了一些java进阶学习资料和面试题,需要资料的请加JAVA高阶学习Q群:664389243
这是小编创建的java高阶学习交流群,加群一起交流学习深造。群里也有小编整理的2019年最新最全的java高阶学习资料!

相关文档 

图片 1

在编程面试中,您将看到许多基于二叉搜索树的数据结构和算法问题,例如:检查二叉树是否是BST?或者,编写一个程序来检查BST是否平衡。为了解决这个问题,您必须知道如何在Java中实现BST。

考察数据结构——第一部分:数据结构简介

在这,我将教您如何在Java中实现二叉搜索树,您可以使用它来解决任何二叉搜索树或基于二叉树的编码问题。

考察数据结构——第二部分:队列、堆栈和哈希表

Java中的二叉搜索树

 

在这里,您将学习如何创建具有整数节点的二叉搜索树。我使用泛型不仅仅是为了使代码简单,如果您愿意,可以将问题扩展到使用泛型,这将允许您创建一个字符串、整数、浮点或双精度的二叉树。记住,确保BST的节点必须实现Comparable接口。这是许多Java程序员在尝试使用泛型实现二叉搜索树时容易忘记的。

原文链接:Part3: Binary Trees and
BSTs

这里是Java中的二叉搜索树的实现。这只是一个结构,我们随后将添加方法在二叉搜索树中添加节点,从二叉搜索树中删除节点,并在后续部分中从BST中查找节点。

 

在这个实现中,我创建了一个Node类,它类似于我们的链表节点类,在向您展示如何在Java中实现链表时创建的。它有一个数据元素,一个整数和一个Node引用,指向二叉树中的另一个节点。

本文是

我还创建了四个基本功能,如下所示:

“考察数据结构”系列文章的第三部分,讨论的是.Net Framework基类库没有包括的常用数据结构:

getRoot(), 返回二叉树的根

二叉树。就像线形排列数据的数组一样,我们可以将二叉树想象为以二维方式来存储数据。其中一种特殊的二叉树,我们称为二叉搜索树(binary search tree),简称为BST,它的数据搜索能力比一般数组更加优化。

isEmpty(), 用于检查二叉搜索树是否为空

 

size(), 查找BST中的节点总数

目录:

clear(), 清除BST

简介

以下是使用Java创建二叉搜索树或BST的示例代码,不使用任何第三方库。

在树中排列数据

<b>import</b> java.util.Stack;

理解二叉树

<font><i>/**

用BSTs改善数据搜索时间

* Java Program to implement a binary search tree. A binary search tree
is a

现实世界的二叉搜索树

* sorted binary tree, where value of a node is greater than or equal to
its

 

* left the child and less than or equal to its right child.

简介:

*

 

* @author WINDOWS 8

在本系列的第一部分,我们讲述了什么是数据结构,怎么评估它们的性能,以及怎样根据其性能选择具体的数据结构来处理特定的算法。另外,我们复习了数据结构的基础知识,了解了最常用的数据结构——数组及与其相关的ArrayList。在第二部分,我们讲述了ArrayList的两个兄弟——堆栈和队列。它们存储数据的方式与ArrayList非常相似,但它们访问数据的方式受到了限制。我们还讨论了哈希表,它可以以任意对象作为其索引,而非一般所用的序数。

*

 

*/</i></font><font>

ArrayList,堆栈,队列和哈希表从存储数据的表现形式看,都可以认为是一种数组结构。这意味着,这四种数据结构都将受到数组边界的限制。回想第一部分所讲的,数组在内存中以线形存储数据,当数组容量到达最大值时,需要显式地改变其容量,同时会造成线形搜索时间的增加。

<b>public</b> <b>class</b> BST {

 

<b>private</b> <b>static</b>
<b>class</b> Node {

本部分,我们讲考察一种全新的数据结构——二叉树。它以一种非线性的方式存储数据。之后,我们还将介绍一种更具特色的二叉树——二叉搜索树(BST)。BST规定了排列树的每个元素项的一些规则。这些规则保证了BSTs能够以一种低于线形搜索时间的性能来搜索数据。

<b>private</b> <b>int</b> data;

 

<b>private</b> Node left, right;

 

<b>public</b> Node(<b>int</b> value) {

在树中排列数据

data = value;

 

left = right = <b>null</b>;

如果我们看过家谱,或者是一家公司的组织结构图,那么事实上你已经明白在树中数据的排列方式了。树由许多节点的集合组成,这些节点又有许多相关联的数据和“孩子”。子节点就是直接处于节点之下的节点。父节点则位于与节点直接关联的上方。树的根是一个不包含父节点的单节点。

}

 

}

图1显示了公司职员的组织结构图。

<b>private</b> Node root;

图片 2

<b>public</b> BST() {

图一

root = <b>null</b>;

 

}

例中,树的根为Bob Smith,是公司的CEO。这个节点为根节点是因为其上没有父亲。Bob Smith节点有一个孩子Tina Jones,公司总裁。其父节点为Bob Smith。Tina Jones有三个孩子:

<b>public</b> Node getRoot() {

Jisun Lee, CIO

<b>return</b> root;

Frank Mitchell, CFO

}

Davis Johnson, VP of Sales

</font><font><i>/**

这三个节点的父亲都是Tina Jones节点。

* Java function to check if binary tree is empty or not

 

* Time Complexity of this solution is constant O for

所有的树都有如下共同的特性:

* best, average and worst case.

1、只有一个根;

*

2、除了根节点,其他所有节点又且只有一个父节点;

* @return true if binary search tree is empty

3、没有环结构。从任意一个节点开始,都没有回到起始节点的路径。正是前两个特性保证没有环结构的存在。

*/</i></font><font>

 

<b>public</b> <b>boolean</b> isEmpty() {

对于有层次关系的数据而言,树非常有用。后面我们会讲到,当我们有技巧地以层次关系排列数据时,搜索每个元素的时间会显著减少。在此之前,我们首先需要讨论的是一种特殊的树:二叉树。

<b>return</b> <b>null</b> == root;

 

}

理解二叉树

</font><font><i>/**

 

* Java function to return number of nodes in this binary search tree.

二叉树是一种特殊的树,因为它的所有节点最多只能有两个子节点。并且,对于二叉树中指定的节点,第一个子节点必须指向左孩子,第二个节点指向右孩子。如图二所示:

* Time complexity of this method is O

图片 3

* @return size of this binary search tree

图二

*/</i></font><font>

 

<b>public</b> <b>int</b> size() {

二叉树(a)共有8个节点,节点1为根。节点1的左孩子为节点2,右孩子为节点3。注意,节点并不要求同时具有左孩子和右孩子。例如,二叉树(a)中,节点4就只有一个右孩子。甚至于,节点也可以没有孩子。如二叉树(b),节点4、5、6都没有孩子。

Node current = root;

 

<b>int</b> size = 0;

没有孩子的节点称为叶节点。有孩子的节点称为内节点。如图二,二叉树(a)中节点6、8为叶节点,节点1、2、3、4、5、7为内节点。

Stack<Node> stack = <b>new</b> Stack<Node>();

 

<b>while</b> (!stack.isEmpty() || current !=
<b>null</b>) {

不幸的是,.Net Framework中并不包含二叉树类,为了更好地理解二叉树,我们需要自己来创建这个类。

<b>if</b> (current != <b>null</b>) {

 

stack.push;

第一步:创建节点类Node

current = current.left;

 

} <b>else</b> {

节点类Node抽象地表示了树中的一个节点。认识到二叉树中节点应包括两个内容:

size++;

1、 
数据;

current = stack.pop();

2、 
子节点:0个、1个、2个;

current = current.right;

 

}

节点存储的数据依赖于你的实际需要。就像数组可以存储整型、字符串和其他类类型的实例一样,节点也应该如此。因此我们应该将节点类存储的数据类型设为object。

}

 

<b>return</b> size;

注意:在C# 2.0版中可以用泛型来创建强类型的节点类,这样比使用object类型更好。要了解更多使用泛型的信息,请阅读Juval Lowy的文章:An
Introduction to C#
Generics。

}

 

</font><font><i>/**

下面是节点类的代码:

* Java function to clear the binary search tree.

 

* Time complexity of this method is O

public class Node

*/</i></font><font>

{

<b>public</b> <b>void</b> clear() {

   private
object data;

root = <b>null</b>;

   private
Node left, right;

}

 

}

   #region
Constructors

</font>

   public
Node() : this(null) {}

小编整理了一些java进阶学习资料和面试题,需要资料的请加JAVA高阶学习Q群:664389243
这是小编创建的java高阶学习交流群,加群一起交流学习深造。群里也有小编整理的2019年最新最全的java高阶学习资料!

   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托管堆中。他们没有必要像数组元素那样连续存放。

图片 4

图三

 

如果我们要访问二叉树中的特定节点,我们需要搜索二叉树的每个节点。它不能象数组那样根据指定的节点直接访问。搜索二叉树要耗费线性时间,最坏情况是查询所有的节点。也就是说,当二叉树节点个数增加时,查找任意节点的步骤数也将相应地增加。

 

因此,如果二叉树的定位时间为线性,查询时间也为线性,那怎么说二叉树比数组更好呢?因为数组的查询时间虽然也是线性,但定位时间却是常量啊?是的,一般的二叉树确实不能提供比数组更好的性能。然而当我们有技巧地排列二叉树中的元素时,我们就能很大程度改善查询时间(当然,定位时间也会得到改善)。

 

用BSTs改善数据搜索时间

 

二叉搜索树是一种特殊的二叉树,它改善了二叉树数据搜索的效率。二叉搜索树有以下属性:对于任意一个节点n,其左子树下的每个后代节点的值都小于节点n的值;而其右子树下的每个后代节点的值都大于节点n的值。

 

所谓节点n的子树,可以将其看作是以节点n为根节点的树。因此,子树的所有节点都是节点n的后代,而子树的根则是节点n本身。图四演示了子树的概念和二叉搜索树的属性。

图片 5

图四

 

图五显示了二叉树的两个例子。图右,二叉树(b),是一个二叉搜索树(BST),因为它符合二叉搜索树的属性。而二叉树(a),则不是二叉搜索树。因为节点10的右孩子节点8小于节点10,但却出现在节点10的右子树中。同样,节点8的右孩子节点4小于节点8,却出现在了它的右子树中。不管是在哪个位置,不符合二叉搜索树的属性规定,就不是二叉搜索树。例如,节点9的右子树只能包含值小于节点9的节点(8和4)。

图片 6

图五

 

从二叉搜索树的属性可知,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,以此类推。

图片 7

图六

 

这里一个重要概念就是算法的每一步在理想状态下都将使被访问的节点数减少一半。比较一下数组的搜索算法。搜索数组时,要搜索所有所有元素,每个元素搜索一次。也就是说,搜索有n个元素的数组,从第一个元素开始,我们要访问n-1个元素。而有n个节点的二叉搜索树,在访问了根节点后,只需要再搜索n/2个节点。

 

搜索二叉树与搜索排序数组相似。例如,你要在电话薄中查找是否有John King。你可以从电话薄的中间开始查找,即从以M开头的姓氏开始查找。按照字母顺序,K是在M之前,那么你可以将M之前的部分在折半,此时,可能是字母H。因为K是在H之后,那么再将H到M这部分折半。这次你找到了字母K,你可以马上看到电话薄里有没有James King。

 

搜索BST与之相似。BST的中点是根节点。然后从上到下,浏览你所需要的左孩子或右孩子。每一步都将节约一半的搜索时间。根据这一特点,这个算法的时间复杂度应该是log­2n,简写为log n。回想我们在第一部分讨论的数学问题,log­2n = y,相当于2y = n。即,节点数增加n,搜索时间只缓慢地增加到log­2n。图七表示了log­2n和线性增长的增长率之间的区别。时间复杂度为log­2n的算法运行时间为下面那条直线。

图片 8

 

图七

 

可以看出,这条对数曲线几乎是水平线,随着N值的增加,曲线增长缓慢。举例来说吧,搜索一个具有1000个元素的数组,需要查询1000个元素,而搜索一个具有1000个元素的BST树,仅需要查询不到10个节点(log10 1024 = 10)。

 

在分析BST搜索算法中,我不断地重复“理想地(ideally)”这个字眼儿。这是因为BST实际的搜索时间要依赖于节点的拓扑结构,也就是说节点之间的布局关系。象图六中所示的二叉树,每一步比较操作都可以使搜索时间减半。然而,我们来看看图八所示的BST树,它的拓扑结构是与数组的排列方式是同构的。

图片 9

图八

 

搜索图八中的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插入算法:

图片 10

图九

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中,最小值的节点总是在最左边,最大值的节点总是在最右边。

因为替换选择了被删除节点右子树中最小的一个节点,这就保证了该节点一定大于被删除节点左子树的所有节点,同时,也保证它替代了被删除节点的位置后,它的右子树的所有节点值都大于它。因此这种选择策略符合二叉搜索树的特性。

 

图十描述了三种情况的替换选择方案

 

图片 11 

 图十

和搜索、插入算法一样,删除算法的运行时间与BST的拓扑结构有关。理想状态下,时间复杂度为log2 n,最坏情况下,耗费的为线性时间。

 

BST节点的遍历

 

对于线性的连续的数组元素,采用的是单向的迭代法。从第一个元素开始,依次向后迭代每个元素。而BST则有三种常用的遍历方式:

1、 
前序遍历(Perorder traversal)

2、 
中序遍历(Inorder traversal)

3、 
后序遍历(Postorder traversal)

 

当然,这三种遍历工作原理几乎相似。它们都是从根节点开始,然后访问其子节点。区别在于遍历时,访问节点本身和其子节点的顺序不同。为帮助理解,我们看看图十一所示的BST树。(注意图六和图十一所示的BST树完全相同。

图片 7

图十一

 

前序遍历

 

前序遍历从当前节点(节点c)开始,然后访问其左孩子,再访问右孩子。如果从BST树的根节点c开始,算法如下:

1、 
访问c。(这里所谓访问时指输出节点的值,并将节点添加到ArrayList中,或者其它地方。这取决于你遍历BST的目的。)

2、 
对c的左孩子重复第一步;

3、 
对c的右孩子重复第一步;

 

设想算法的第一步打印出c的值。以图十一所示的BST树为例,以前序遍历的方法输出的值是什么?是的,我们在第一步首先输出根节点的值。然后对根的左孩子执行第一步,输出50。因为第二步是反复执行第一步操作,因此是对根节点的左孩子的左孩子访问,输出20。如此重复直到树的最左边底层。当到达节点5时,输出其值。既然5没有左、右孩子,我们又回到节点20,执行第三步。此时是对节点20的右孩子反复执行第一步,即输出25。25没有孩子节点,又回到20。但我们对20已经做完了三步操作,所以回到节点50。再对50执行第三步操作,即对50的右孩子重复执行第一步。这个过程不断进行,直到遍历完树的所有节点。最后通过前序遍历输出的结果如下:

90, 50, 20, 5, 25, 75, 66, 80, 150, 95, 92, 111, 175,
166, 200

 

可以理解,这个算法确实有点让人糊涂。或许我们来看看算法的代码可以理清思路。下面的代码为BST类的PreorderTraversal()方法,这个类在文章后面会构建。注意这个方法调用了Node类的实例作为输出参数。输出的节点就是算法步骤中所提到的节点c。执行前序遍历就是从BST的根节点开始调用PreorderTraversal()方法。

 

protected virtual string PreorderTraversal(Node
current, string separator)

{

   if (current
!= null)

   {

     
StringBuilder sb = new StringBuilder();

     
sb.Append(current.Value.ToString());

     
sb.Append(separator);

 

     
sb.Append(PreorderTraversal(current.Left, separator));

     
sb.Append(PreorderTraversal(current.Right, separator));

      return
sb.ToString();

   }

   else

      return
String.Empty;

}

 

(译注:实际上本方法就是一个递归调用)

注意遍历后的结果放到字符串中,这个字符串时通过StringBuilder创建。首先将当前节点的值放到字符串中,然后再访问当前节点的左、右孩子,将结果放到字符串中。

 

中序遍历

 

中序遍历是从当前节点的左孩子开始访问,再访问当前节点,最后是其右节点。假定BST树的根节点为c,算法如下:

1、 
访问c的左孩子。(这里所谓访问时指输出节点的值,并将节点添加到ArrayList中,或者其它地方。这取决于你遍历BST的目的。)

2、 
对c重复第一步;

3、 
对c的右孩子重复第一步。

 

InorderTraversal()方法的代码和PreorderTraversal()相似,只是添加当前节点值到StringBuilder的操作之前,先递归调用方法本身,并将当前节点的左孩子作为参数传递。

 

protected virtual string InorderTraversal

               
(Node current, string separator)

{

相关文章

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注