树与二叉树

树与二叉树

一、树的基本概念

1、树的定义

树是数据元素之间具有层次关系的非线性结构,定义树的一种自然方式就是递归的方式。一棵树是由一些结点组成的集合。这个集合可以是空集;若不是空集,则树由称为根结点R以及0个或者多个非空子树T[0]、T[1]、T[2]、… 、T[k-1]组成,这些子树中每一个根结点都与根结点R,连接的一条有向的

  • 1、特殊的结点,称为根结点,它没有前驱结点只有后继结点

  • 2、除了根结点之外的其他结点为k个不相交的集合T[0]、T[1]、T[2]、… 、T[k-1]. 其中每个集合也是一个树结构,也叫做子树

根据上述定义树可以存在如下四种状态:

  • 3、树结构是基于递归的基础上,所以理解递归的概念非常重要。在开始学习树之前,我们有必要来了解一下树结构中的一些常用术语:

根结点: 根结点就是没有父结点的结点,一棵树结构中只能有唯一一个根结点

孩子结点: 一棵树中,拥有父结点的结点,就是该父结点的孩子结点。例如上图中的B、C、D就是A的孩子结点,E、F就是B的孩子结点

父母结点(也称父结点): 例如上图中的A就是B、C、D的父结点,B就是E、F的孩子结点

兄弟结点: 拥有相同的父结点的所有孩子结点叫做兄弟结点,例如B、C、D三个结点的共同父结点都为A,因此它们是兄弟结点。

祖先结点: 如果存在一条从根结点到结点Q的路径,而且结点P出现在这条路径上,那么P就是Q的祖先结点,而结点Q也称为P的子孙结点或者后代。如上图的E的祖先结点有A和B,而E则是A和B的子孙结点。

叶子结点: 没有孩子结点的结点叫做叶子结点,例如上图的E、F、G、H、I、J都是

结点的度: 表示当前结点拥有的子树的棵数。如A结点的度就是3(因为它有3棵分别以B、C、D为根结点的子树),B结点的度就是2

树的层: 也叫做结点的层,该属性反映结点处于树中的层次位置,我们约定根结点的层为1,如上图所示,A层为1,B层为2,E的层为3。

树的深度或高度: 是指树中结点最大的层数,例如上图结点最大的层数是3,所以这个棵树的深度就是3

边: 边表示从父结点到孩子结点之间的连线

二、二叉树的定义和基本性质

二叉树是树结构中一种特殊结构的树,每个结点最大的度<=2,二叉树是由n个结点组成的有限集合,n=0表示是一棵空二叉树;n > 0的二叉树由一个根结点和两棵互不相交、分别称为左子树、右子树的子二叉树构成,二叉树符合递归定义,二叉树同样拥有树中深度、层、度的概念。

下面是二叉树的5种状态:

性质一:如果根结点的层次为1,那么二叉树第i层最多有2^(i-1)个结点。

性质二: 在高度为h的二叉树中,最多有2^h - 1个结点。

因为由性质一可得出,在二叉树的第i层最多有2^(i-1)个结点,那么高度为h的二叉树最多总共有多少个结点,实际上就是把每层累加求和,等比数列求和得到最多有2^h - 1个结点

性质三: 满二叉树和完全二叉树

一颗高度为h的满二叉树是具有2^h - 1个结点的二叉树。满二叉树的最大特点就是每一层的结点数都达到最大值。而对于完全二叉树就是除了第h层(最后一层)外,其他各层的结点数都达到最大值,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树,很明显一棵满二叉树肯定是一棵完全二叉树

性质四: 一棵具有n个结点的完全二叉树,对于序号为i(0≤i<n)的结点,则有如下规则 :

  • ①若i=0,则i为根结点,无父母结点;若i>0,则i的父母结点序号为⌊(i−1)/2⌋(向下取整)。

  • ②若2i+1<=n,则i的左孩子结点序号为2i+1,否则i无左孩子。

  • ③若2i+2>=n,则i的右孩子结点序号为2i+2,否则i无右孩子。

如上图(b)中i=0时为根结点A,其左孩子B序号为2i+1,右孩子结点C的序号则为2i+2。注意这仅使用于完全二叉树。

三、二叉树的抽象数据类型(ADT)和存储结构

与链表、栈、队列抽象数据类型类似,二叉树抽象数据类型也有插入、删除、查找等操作,同时二叉树有4种遍历方式: 层序、先序、中序、后序遍历方式。现在我们声明二叉树的抽象数据类型顶级接口Tree如下:T表示结点元素的类型,该类型必须实现了Comparable接口,方便比较数据。而 BinaryNode是二叉树的结点类。Tree接口声明如下:

抽象数据类型(ADT)

存储结构

二叉树的存储结构主要采用的是链式存储结构,至于顺序存储结构仅适用于完全二叉树或满二叉树,这个我们后面再介绍,这里我们主要还是分析二叉树的链式存储结构。二叉树的链式存储结构主要有二叉链表和三叉链表两种,下面分别说明

  • 1、二叉树的二叉链表存储结构

二叉链表结构主要由一个数据域和两个分别指向左、右孩子的结点组成

class BinaryNode(data: T , left: BinaryNode<T>? = null , right: BinaryNode<T>? = null )

采用二叉链表存储结构,每个结点只存储了到其孩子结点的单向关系,而没有存储到父结点的关系,这样的话,每次要获取父结点时将消耗较多的时间,因为需要从root根结点开始查找,花费的时间是遍历部分二叉树的时间,而且与该结点的位置有关。为了更高效的获取父结点,三叉链表存储结构孕育而生了。

  • 2、二叉树的三叉链表存储结构

三叉链表主要是在二叉链表的基础上多添加了一个指向父结点的域,这样我们就存储了父结点与孩子结点的双向关系,当然这样也增加了一定的空开销其结点结构如下:

class TreeNode(data: T, parent: BinaryNode<T>? = null, left: BinaryNode<T>? = null , right: BinaryNode<T>? = null)

  • 3、二叉树的静态二/三叉链表存储结构

除了以上两种结构,其实我们也可采用一个结点数组存储所有二叉树的所有结点,这种结构称为静态二/三叉链表,在这样的结构中,每个结点存储其(父结点)左、右孩子下标,通过下标表示结点间的关系,-1表示无此结点。结构如下:

四、二叉查找树(二叉搜索树)

基本特性

二叉查找树的特性是,对于树中的每个结点T(T可能是父结点),它的左子树中所有项的值小T中的值,而它的右子树中所有项的值都大于T中的值

二叉查找树BinarySearchTree类结构定义如下:

基本操作

  • 1、插入操作

对于二叉查找树的插入操作的设计是比较简单,我们只要利用二叉查找树的特性(即对每个父结点,它的左子树中所有项的值小T中的值,而它的右子树中所有项的值都大于T中的值),找到只对应的插入位置即可,假如现在我们要插入data=4的结点,那么可以这样操作,沿着树查找(比较结点的数据与data的大小从而决定往左/右子树继续前行),如果找到data(4),则什么也不做,否则将data插入到遍历的路径上的最后一个点

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-13-52-image.png)

五、二叉树的遍历

二叉树的层序遍历

二叉树的层序遍历就是兄弟优先访问原则,同一层的兄弟访问顺序是先左后右,以此类推他们的后代结点兄弟结点访问次序类似。

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-15-53-image.png)

需要明确几个遍历的问题:

  • p点如何到达其兄弟结点? B->C

  • p点如何到达它同层下一个结点(非兄弟结点)?D->E

  • p点如何在访问完当前层的最后一个结点时,进入下一层的第一个结点?C->D

上述的遍历问题实际上按照二叉树的本身结构特性,是无法实现的。所以我们需要借助第三方容器也就是所谓的集合来达到遍历。那么这个容器该如何选呢?该容器必须告诉我们下一个访问结点是谁?层次遍历的规则是兄弟优先,从左往右,因此,在访问时,必须先将当前正在访问的结点P的左右孩子依次放入容器,如P=C时,E、H必须已在栈中,而且先进入必须先访问,即先进E再进H,然后先访问E再访问H,显然该容器必须满足“先进先出”的原则,那也就是队列了,这里我们选择LinkedQueue队列,层次遍历算法描述如下:

p点从根结点开始访问,设一个空队列,当前p结点不为空时,重复以下操作:

① 访问p结点,将p结点的左右孩子依次入队。

② 使p指向一个出队结点,重复①的操作,直到队列为空。

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-16-18-image.png)

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-16-28-image.png)

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-16-37-image.png)

二叉树的先序遍历

先序遍历算法,它的访问规则是先遍历根结点,再遍历左子树,最后遍历右子树(根左右)

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-16-53-image.png)

1、递归实现

从图可知,先根遍历每次总是先访问根结点,再访问左子树,最后访问右子树,而对于一个复杂的树,我们可以先将其简化为三个结点的树(两个结点或者一个结点则空白填补,最后去掉即可),然后解出该子树的顺序,再求解其上层的子树,如上图的步骤(1)(2)的过程,我们可先求出以B为根的三个结点的子树,先根遍历次序为BEF,然后再求出以A为根结点的树,然后将已解出的(2)作为左子树整体插入到A(BEF)C的序列中即可,这样整棵树的遍历顺序求出来了,事实上这里我们又再次运用递归思维(复杂化简单求解问题),

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-17-21-image.png)

2、非递归实现

当然我们也可以使用非递归的方式实现,不过得借助容器栈实现(这里利用LinkedStack)。我们这里来分析一下为什么需要借助栈,如下图:

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-17-23-image.png)

 p结点从根结点A开始,沿左子树开始遍历B、D,再沿D的右子树访问G结点,这样就完成了遍历A的左子树的工作,此时需要返回到根结点A,然后继续遍历A的右子树,但G结点并没有到达A的直接指向,因此可见二叉链表本身并不能很好支持非递归的遍历二叉树的操作,所以我们需要一个容器来记录这个访问路径,以便能顺利返回A点继续遍历其右子树,由于所有刚才所有经过的结点次序(ABDG)与返回结点的次序(GDBA)正好相反,如果我们能保存路径上的所经过的结点,只要按照相反次序就应该能找到返回的路径,也就是说这个容器的特点必须是后进先出的–栈,这就是选择栈的原因。根据这一思路,我们将二叉查找树的先根次序非递归遍历算法描述如下(如下图所示,p从根结点开始,设置辅助容器linkedStack,当p非空或者栈非空时,循环执行下述操作,直到栈和二叉查找树为空):

①若p非空,表示恰好到达p结点,访问p结点,再将p入栈,进入p的左子树。

②进入p的左子树后,若p为空但栈不为空,则表示已完整走完一条路径,则需返回寻找另一条路径,而此时返回的结点恰恰是刚才经过的最后一个结点,它已保存在栈顶,因此出栈该结点,赋值给p,再遍历p的右子树。

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-18-18-image.png)

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-18-03-image.png)

二叉树的中序遍历

中根次序遍历的算法规则是,先遍历左子树,再遍历根结点,最后遍历右子树(左根右)。过程如下图(同样利用的是递归思维)

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-18-14-image.png)

1、递归实现

图的原理跟先根次序的的原理是一样的,唯一不同的是根结点的遍历顺序罢了,下面给出递归算法的实现代码:

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-18-12-image.png)

2、非递归实现

同样的,我们也可以借助栈容器使用非递归的遍历算法实现中根遍历,中根遍历算法描述如下(p从根结点开始,设置辅助容器linkedStack,当p非空或者栈非空时,循环执行下述操作,直到栈和二叉查找树为空):

① 若p不为空,表示刚刚到达p结点,由于是中根遍历,不能先访问根结点,直接将p入栈,继续进入p左子树,直到p为null。

②若p为空但栈不为空,表示已走完一条路径,则需要返回寻找另一条路径,而返回结点就是刚才经过的最后一个结点,它已保存在栈顶,所以出栈一个结点,使p指向它,并访问该结点,再进入p的右子树。

程序实现如下:

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-18-20-image.png)

二叉树的后序遍历

后根次序遍历的算法规则是,先访问左子树,再访问右子树,最后访问根结点(左右根)

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-18-23-image.png)

1、递归实现

loading-ag-706

2、非递归实现

同样的,我们也可以借助栈容器使用非递归的遍历算法实现后根遍历

![](/Users/mikyou/Library/Application Support/marktext/images/2019-12-10-22-40-24-image.png)

六、完全二叉树的构造与实现

七、二叉树的构造与实现

1、先序和中序构造二叉树

2、后序和中序构造二叉树

八、平衡二叉树(AVL树)定义与基本性质

九、平衡二叉树(AVL树)的基本操作

十、平衡二叉树(AVL树)的设计与实现

十一、平衡二叉树(AVL树)的单旋实现

十二、平衡二叉树(AVL树)的双旋实现

十三、平衡二叉树的最少节点和最多节点问题


   转载规则


《树与二叉树》 mikyou 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
有关Kotlin类型别名(typealias)你需要知道的一切 有关Kotlin类型别名(typealias)你需要知道的一切
翻译说明: 原标题: All About Type Aliases in Kotlin 原文地址: https://typealias.com/guides/all-about-type-aliases/ 原文作者: Dave Leeds
2019-10-27
下一篇 
Dart语法篇之基础语法(一) Dart语法篇之基础语法(一)
简述: 又是一段新的开始,Dart这门语言相信很多人都是通过Flutter这个框架才了解的,因为Flutter相比Dart更被我们所熟知。很多人迟迟不愿尝试Flutter原因大多数是因为学习成本高,显然摆在面前的是需要去重新学习一门新的语
2019-10-26