计算机软件技术基础教程课件-10第十章-树

第十章树10.1树的基本概念学校的教学组织机构图10.1树的基本概念定义树（Tree）是n（n>0）个结点的有限集合T，它满足如下两个条件：(1)有且仅有一个特定的称为根（Root）的结点，它没有前趋。(2)其余的结点可分成m个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为根的子树。将n=0时的空集合定义为空树（有的书上将n=1的集合定义为空树）。10.1树的基本概念树的直观表示通常采用以下几种方法：(1)直观表示法：使用圆圈表示结点，连线表示结点之间的关系，结点的名字可写在圆圈内或圆圈旁，如学校的教学组织机构图。(2)文氏图表示法：使用圆圈表示结点，用圆圈的相互包含表示结点之间的关系，如图(a)所示。(3)目录表示法：使用凹入的线条表示结点，以线条的长短表示结点间的关系，长线条包含短线条，如图(b)所示。(4)嵌套括号表示法：使用括号表示结点，括号的相互包含表示结点间的关系，如图(c)所示。10.1树的基本概念10.1树的基本概念结点：是指树中的一个元素，包含数据项及若干指向其子树的分支。结点的度：是指结点拥有的子树个数树的度：是指树中最大的结点度数。叶子：是指度为零的结点，又称为终端结点。孩子：一个结点的子树的根称为该结点的孩子。双亲：一个结点的直接上层结点称为该结点的双亲。兄弟：同一双亲的孩子互称为兄弟。结点的层次：从根结点开始，根结点为第一层，根的孩子为第二层，根的孩子的孩子为第三层，依次类推。10.1树的基本概念树的深度：树中结点的最大层次数。堂兄弟：双亲在同一层上的结点互称为堂兄弟。路径：若存在一个结点序列k1,k2,…,kj,可使k1到达kj,则称这个

结序序列是k1到达kj的一条路径。子孙和祖先：若存在k1到kj的一条路径k1,k2,…,kj，则k1,…,kj-1为kj的祖先，而k2,…,kj为k1的子孙。森林：m(m≥0)棵互不相交的树的集合构成森林。删除一棵树的根时，就得到了子树构成的森林；当在森林中加上一个根结点时，森林就变为一棵树。有序树和无序树：若将树中每个结点的各个子树都看成是从左到右有次序的（即不能互换），则称该树为有序树，否则为无序树。10.2二叉树10.2.1基本概念定义

二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点及两棵互不相交的、分别称做这个根的左子树和右子树的二叉树构成。

由二叉树的定义可以给出二叉树的五种基本形态。当n=0时得到空二叉树；n=1时得到仅有一个根结点的二叉树；当根结点的右子树为空时，得到一个仅有左子树的二叉树；当根结点的左子树为空时，得到一个仅有右子树的二叉树；当左、右子树均非空时，得到一般的二叉树。10.2二叉树10.2.1基本概念二叉树的基本形态10.2二叉树10.2.1基本概念满二叉树、完全二叉树和一般二叉树10.2二叉树10.2.2二叉树的性质性质1

在二叉树的第i层上至多有2i－1个结点(i≥1)。证明

可用数学归纳法予以证明。当i=1时有2i－1=20=1，同时第一层上只有一个根结点，故命题成立。设当i=k时成立，即第k层上至多有2k－1个结点。当i=k+1时，由于二叉树的每个结点至多有两个孩子，所以第k+1层上至多有2

2k－1=2k个结点，故命题成立。10.2二叉树10.2.2二叉树的性质

性质2

深度为k的二叉树至多有2k-1个结点(k≥1)。

（10-1）

证明：性质1给出了二叉树每一层中含有的最大结点数，深度为k的二叉树的结点总数至多为2k-1个。故命题成立。10.2二叉树10.2.2二叉树的性质

性质3

对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

证明：设度为1的结点数为n1，则一棵二叉树的结点总数为

n=n0+n1+n2

（10-2）除根结点外，其余结点都有一个进入的分支(边)，设B为分支总数，则n=B+1。又考虑到分支是由度为1和2的结点发出的，故有B=2n2+n1，即

n=2n2+n1+1 （10-3）

比较式(10-1)与式(10-2)可得n0=n2+1。命题成立。10.2二叉树10.2.2二叉树的性质

性质4

具有n个结点的完全二叉树的深度为 

lbn

 + 1或 

lb(n + 1)

。

证明：由完全二叉树的定义可知，一个k层的完全二叉树的前k-1层共有2k-1-1个结点，第k层上还有若干结点，所以结点总数n满足关系：

2k-1-1＜n≤2k-1

（10-4）可推出2k-1≤n＜2k，取对数后可得k - 1≤lbn＜k。因为k为整数，所以有k-1 = 

lbn

，即k= 

lbn

 + 1。同样利用(10-3)式有2k-1＜n+1≤2k，取对数得k-1＜lb(n+1)≤k，因而k= 

lb(n+1)

。命题成立。10.3二叉树的存储结构10.3.1顺序存储结构顺序存储结构是将二叉树的所有结点，按照一定的顺序化方式，存储到一片连续的存储单元中。结点的顺序将反映出结点之间逻辑关系。10.3二叉树的存储结构10.3.1顺序存储结构完全二叉树的结点编号完全二叉树的顺序存储10.3二叉树的存储结构10.3.1顺序存储结构下图给出了一般二叉树构成完全二叉树并用顺序存储结构存储的示例，其中方形结点为虚结点，并用符号@来表示结点值。一般二叉树的结点编号10.3二叉树的存储结构10.3.2链式存储结构链式存储是二叉树的一种自然链接方法。在一定的条件下，链式存储可节省存储单元。由于二叉树的每个结点最多有两个孩子，所以采用链式存储结构来存储二叉树时，每个结点应至少包括三个域：结点数据域(data)、左孩子指针域(lchild)和右孩子指针域(rchild)，这样二叉树链式存储结构的结点逻辑结构如图所示。10.3二叉树的存储结构10.3.2链式存储结构链表存储结构10.3二叉树的存储结构10.3.3二叉树的建立二叉树的建立是指如何在内存中建立二叉树存储结构。二叉树顺序存储结构的建立比较简单，只须将二叉树各个结点的(信息)值按原有的逻辑关系送入相应的向量单元中即可。建立二叉树链式存储结构的算法有多种，它们依赖于按照何种形式来输入二叉树的逻辑结构信息。一种常见的算法是按照完全二叉树的层次顺序，依次输入结点信息来建立二叉链表。对于一般二叉树，首先必须通过添加若干个虚结点使其成为完全二叉树，然后建立二叉链表。10.4二叉树的遍历10.4.1二叉树的深度优先遍历1.先序遍历算法

先序遍历算法的遍历过程是，若二叉树非空，执行以下操作：

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。10.4二叉树的遍历10.4.1二叉树的深度优先遍历二叉树的遍历过程10.4二叉树的遍历10.4.1二叉树的深度优先遍历

2.中序遍历算法

中序遍历算法的遍历过程是，若二叉树非空，执行以下操作：

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。10.4二叉树的遍历10.4.1二叉树的深度优先遍历

3.后序遍历算法

后序遍历算法的遍历过程是，若二叉树非空，执行以下操作：

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。10.4二叉树的遍历10.4.2二叉树的广度优先遍历二叉树的广度优先遍历又称为按层次遍历。这种遍历方式是先遍历二叉树的第一层结点，然后遍历第二层结点，……最后遍历最下层的结点。而对每一层的遍历是按从左至右的方式进行的。10.4二叉树的遍历10.4.3深度优先的非递归算法前面描述的三种深度优先遍历算法都是用递归方式给出的。虽然递归算法比较紧凑，结构清晰，但它的运行效率比较低，通常可读性也较差；同时并非所有程序设计语言都允许递归，因此有时需要将一个递归算法转化为等价的非递归算法。10.4二叉树的遍历10.4.4从遍历序列恢复二叉树前面讨论了由二叉树得到遍历序列的问题，下面将讨论这个问题的逆问题，即在已知结点遍历序列的条件下，恢复相应二叉树的问题。在已知一棵任意二叉树的先序遍历序列和中序遍历序列，或者已知中序遍历序列和后序遍历序列的条件下，可以唯一地确定这棵二叉树。除了特殊的情况，不能用先序遍历序列和后序遍历序列来确定对应的二叉树。10.4二叉树的遍历10.4.4从遍历序列恢复二叉树由先序和中序序列构造二叉树的过程10.4二叉树的遍历10.4.5遍历算法的应用1.统计一棵二叉树中的叶子结点数

因为叶子结点是二叉树中那些左孩子和右孩子均不存在的结点，所以可在二叉树的遍历过程中，对这种特殊结点进行计数，来完成叶子结点数的统计。这个统计可在任何一种遍历方式下给出。下面给出一种统计一棵二叉树叶子结点数的递归统计算法。10.4二叉树的遍历10.4.5遍历算法的应用一棵树的叶子数目等于它的左子树叶子数加上右子树叶子数的总和。而当一个结点没有左子树也没有右子树的时候，即为叶子结点。其计算表达式如下：10.4二叉树的遍历10.4.5遍历算法的应用2.求二叉树深度

二叉树的深度是二叉树中结点层次的最大值。可通过先序遍历来计算二叉树中每个结点的层次，其中的最大值即为二叉树的深度。下面给出一种计算二叉树深度的递归计算的

算法。10.4二叉树的遍历10.4.5遍历算法的应用在二叉树中，取左子树深度和右子树深度中数值较大的深度加1，就得到了二叉树的深度。其计算表达式如下：10.5二叉树的应用10.5.1哈夫曼树及应用

哈夫曼树，又称最优二叉树，是一类带权路径长度最短的树。

1．基本概念

两个结点间的路径是指从树中一个结点到另一个结点之间的分支。

路径的长度是指从树中一个结点到另一个结点之间的分支数。例如，k1，k2，…，kn是一条路径，则该路径长度为n-1。10.5二叉树的应用10.5.1哈夫曼树及应用树的路径长度是树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。当然，也可能有其他非完全二叉树具有同完全二叉树相同

的路径长度，这可以从具有四个结点构成的三种二叉树的

下图中看出：10.5二叉树的应用10.5.1哈夫曼树及应用设路径长度用PL表示，则(a)、(b)、(c)中二叉树的路径长度分别为(a) PL=0+1+1+2=4;(b) PL=0+1+1+2=4;(c) PL=0+1+2+3=6。当树中的结点被赋予一个称之为权的有某种意义的实数时，则该结点的带权路径长度为结点到树根之间的路径长度与结点权值的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，记作：10.5二叉树的应用10.5.1哈夫曼树及应用在有n个带权叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树被称为最优二叉树或哈夫曼树。

由于WPL是所有叶子结点的权值与路径长度乘积的和，因此要使WPL尽可能地小，就必须使每个叶子结点的路径长度与权值之积尽可能小。但因为权值是确定的，所以只能通过调整叶子结点的路径长度来使结点的权值和路径长度之积尽可能小。也就是说，当一个叶子结点的权值比较大时，应让其尽可能接近根结点，这样就减少了路径长度，从而减少了WPL。10.5二叉树的应用10.5.1哈夫曼树及应用对于具有权值为w1，w2，…，wn的n个叶子结点形成的二叉树，可以具有多种形态，其中能被称为哈夫曼树的二叉树并不是唯一的。例如，对于四个权值分别为3，4，5，7的叶子结点a，b，c，d构造的二叉树，可以得到两棵哈夫曼树，如下图所示。10.5二叉树的应用10.5.1哈夫曼树及应用可以计算出这两棵哈夫曼树的WPL分别为

WPL1=3×2+4×2+5×2+7×2=38

WPL2=3×3+4×3+5×2+7=38

10.5二叉树的应用10.5.1哈夫曼树及应用在叶子数和权值相同的二叉树中，完全二叉树不一定是最优二叉树。例如，对于权值分别为2,4,5,7的四个结点A,B,C,D的集合而言，构造出的完全二叉树和哈夫曼树如下图所示。10.5二叉树的应用10.5.1哈夫曼树及应用可以计算出两棵树的WPL分别为：(a)WPL＝2×2＋4×2＋5×2＋7×2＝36(b)WPL＝2×3＋4×3＋5×2＋7×1＝3510.5二叉树的应用10.5.1哈夫曼树及应用

2.哈夫曼树的构造

哈夫曼最早给出了一个带有一般规律的算法来构造哈夫曼树。10.5二叉树的应用10.5.1哈夫曼树及应用10.5二叉树的应用10.5.1哈夫曼树及应用结点的存储结构10.5二叉树的应用10.5.1哈夫曼树及应用构造哈夫曼树10.5二叉树的应用10.5.1哈夫曼树及应用3.哈夫曼编码通过从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。10.5二叉树的应用10.5.1哈夫曼树及应用

4.哈夫曼树译码

哈夫曼树译码是指由给定的代码求出代码所表示的结点值。它是哈夫曼编码的逆过程。哈夫曼树译码的过程是：从根结点出发，逐个读入电文中的二进制代码，若代码为0则走向左孩子；否则走向右孩子。一旦到达叶子结点，便可译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束为止。10.5二叉树的应用10.5.2二叉排序树树形结构的一个重要应用是用来组织目录。树形结构的目录称为树目录。

1.二叉排序树的概念

如果一棵二叉树的每个结点对应一个关键码，并且每个结点的左子树中所有结点的码值都小于该结点的关键码值，而右子树中所有结点的关键码值都大于该结点的关键码值，则这个二叉树称为二叉排序树。10.5二叉树的应用10.5.2二叉排序树10.5二叉树的应用10.5.2二叉排序树

2.二叉排序树的构造

二叉排序树的构造是指将一个给定的数据元素序列构造为相应的二叉排序树。

对于任意的一组数据元素{R1，R2，…，Rn}，可按以下方法来构造二叉排序树：

(1)令R1为二叉树的根。

(2)若R2<R1，令R2为R1左子树的根结点；否则R2为R1右子树的根结点。

(3)对于R3，…，Rn