《数据结构与算法分析》课件第5章

第5章树5.1树的基本概念5.2二叉树5.3二叉树的存储结构5.4二叉树的遍历5.5树和森林5.6线索二叉树5.7二叉树的应用

5.1树的基本概念

定义1

树(Tree)是n(n≥0)个结点的有限集合T，它满足如下两个条件：

(1)有且仅有一个特定的称为根(Root)的结点，它没有前趋；

(2)其余的结点可分成m个互不相交的有限集合T1，T2，

…，Tm，其中每个集合又是一棵树，并称为根的子树。

将n=0时的空集合定义为空树(有的书上将n=1的集合定义为空树)。图5-1学校的教学组织机构图

5.2二叉树

定义2

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

由二叉树的定义可以给出二叉树的五种基本形态，如图5-2所示。当n=0时得到空二叉树；n=1时得到仅有一个根结点的二叉树；当根结点的右子树为空时，得到一个仅有左子树的二叉树；当根结点的左子树为空时，得到一个仅有右子树的二叉树；当左、右子树均非空时，得到一般的二叉树。图5-2二叉树的基本形态图5-3满二叉树、完全二叉树和一般二叉树

性质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个结点。故命题成立。

性质2

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

(5-1)

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

性质3

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

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

n=n0+n1+n2

(5-2)

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

n=2n2+n1+1 (5-3)

比较式(5-1)与式(5-2)可得n0=n2+1。命题成立。

性质4

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

lbn

 + 1或 

lb(n + 1)

。

注：

x

表示不大于x的最大整数；

x

表示不小于x的最小整数。

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

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

(5-4)

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

lbn

，即k= 

lbn

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

lb(n+1)

。命题成立。

5.3二叉树的存储结构

5.3.1顺序存储结构

顺序存储结构是将二叉树的所有结点，按照一定的顺序化方式，存储到一片连续的存储单元中。结点的顺序将反映出结点之间逻辑关系。

图5-4完全二叉树的结点编号图5-5和表5-2给出了一般二叉树构成完全二叉树并用顺序存储结构存储的示例。其中方形结点为虚结点，并用符号@表示结点值。图5-5一般二叉树的结点编号5.3.2链式存储结构

链式存储是二叉树的一种自然链接方法。在一定的条件下，链式存储可节省存储单元。因为二叉树的每个结点至多有两个孩子，所以采用链式存储结构来存储二叉树时，每个结点应至少包括三个域：结点数据域(data)、左孩子指针域(lchild)和右孩子指针域(rchild)。二叉树链式存储结构的结点逻辑结构如图5-6所示。图5-6二叉树链式存储的结点结构图5-7链表存储结构5.3.3二叉树的建立

二叉树的建立是指如何在内存中建立二叉树存储结构。二叉树顺序存储结构的建立比较简单，只须将二叉树各个结点的(信息)值按原有的逻辑关系送入相应的向量单元中即可。

建立二叉树链式存储结构的算法有多种，它们依赖于按照何种形式来输入二叉树的逻辑结构信息。一种常见的算法是按照完全二叉树的层次顺序，依次输入结点信息来建立二叉链表。对于一般二叉树，首先必须通过添加若干个虚结点使其成为完全二叉树，然后建立二叉链表。

5.4二叉树的遍历

5.4.1二叉树的深度优先遍历

1.先序遍历算法

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

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。图5-8二叉树的遍历过程图5-9算法执行过程示意图

2.中序遍历算法

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

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。

3.后序遍历算法

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

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。5.4.2二叉树的广度优先遍历

二叉树的广度优先遍历又称为按层次遍历。这种遍历方式是先遍历二叉树的第一层结点，然后遍历第二层结点，……最后遍历最下层的结点。而对每一层的遍历是按从左至右的方式进行的。5.4.3深度优先遍历的非递归算法

前面描述的三种深度优先遍历算法都是用递归方式给出的。虽然递归算法比较紧凑，结构清晰，但它的运行效率比较低，通常可读性也较差；同时并非所有程序设计语言都允许递归，因此有时需要将一个递归算法转化为等价的非递归算法。5.4.4从遍历序列恢复二叉树

前面讨论了由二叉树得到遍历序列的问题，下面将讨论这个问题的逆问题，即在已知结点遍历序列的条件下，恢复相应二叉树的问题。在已知一棵任意二叉树的先序遍历序列和中序遍历序列，或者已知中序遍历序列和后序遍历序列的条件下，可以唯一地确定这棵二叉树。除了特殊的情况，不能用先序遍历序列和后序遍历序列来确定对应的二叉树。图5-10由先序和中序序列构造二叉树的过程5.4.5遍历算法的应用

1.统计一棵二叉树中的叶子结点数

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

2.求二叉树深度

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

算法。在二叉树中，取左子树深度和右子树深度中数值较大的深度加1，就得到了二叉树的深度。其计算表达式如下：

3.表达式与二叉树的关系

表达式有三种表达方式：前缀表达式、中缀表达式和后缀表达式。这三种表达式分别对应其表达式树的先序遍历、中序遍历和后序遍历。我们平常一般使用的是中缀表达式如a*(((b+c)*(d*e))+f)，与之对应的后缀表达式为abc+de**f+*，

下面主要讨论由后缀表达式生成表达式树的方法。由后缀表达式生成表达式树算法的主要思想是：

(1)维护一个操作数栈。

(2)扫描后缀表达式，如果碰到操作数，则生成操作数结点入栈；若为操作符，则生成操作符结点，并将栈中头两个元素出栈，作为操作符结点的左右子树(注意：先出栈的为右子树，后出栈的为左子树)，然后将新生成的树作为操作数结点入栈。

(3)重复(2)的操作直到后缀表达式结束为止。若后缀表达式语法正确，栈中将仅剩一个结点，该结点就是表达式树。

5.5树和森林

本节将讨论树的存储表示，并建立森林与二叉树的对应关系。一般树的表示方法如图5-11所示。图5-11树的表示5.5.1树的存储结构

树可以用多种形式的存储结构来表示，经常用到的有以下三种方法。

1．双亲表示法

在树中，每个结点的双亲是唯一的。利用这个性质，可在存储结点信息的同时，为每个结点存储其双亲结点的地址信息。

2．孩子表示法

由于树中每个结点的子树数目不尽相同，因此在采用链式存储结构来表示树时，每个结点内要设置多少个指向其孩子的指针是难以确定的。若以整个树的度k来设置指针，则在n个结点的树中，其空指针域的数目是k*n-(n-1)=n(k-1)+1,这将造成极大的空间浪费。若每个结点按其实际的孩子个数设置指针，并在结点内设置度数域degree来表示该结点所包含的指针数，则各结点不等长，虽然节省了存储空间，但会给运算带来不便。图5-12孩子和双亲孩子表示法

3．孩子兄弟表示法

在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域first和next，即可得到树的孩子兄弟表示法。例如，图5-11中树的孩子兄弟表示法如图5-13所示。这种存储结构的最大优点是，它和二叉树的二叉链表表示完全一样，因此，可利用二叉树的算法来实现对树的操作。图5-13孩子兄弟表示法5.5.2树、森林和二叉树之间的转换

树、森林和二叉树之间有对应关系，它们之间可以互相进行转换，即任何一个森林或一棵树可以唯一地转换成一棵二叉树；而任意一棵二叉树也能唯一地对应于一个森林或一棵树。这种转换是具有唯一性的。将一棵树转换为二叉树的方法是：

(1)在兄弟之间增加一条连线。

(2)对每个结点，除了保留与其左孩子的连线外，应除去与其他孩子之间的连线。

(3)以树的根结点为轴心，将整个树顺时针旋转45°。

图5-14给出了一棵树转换为二叉树的过程。从转换结果可以看出，任何一棵树转化为对应的二叉树后，二叉树的右子树为空。图5-14树转换成二叉树将一棵二叉树转换成树的规则是：

(1)若结点X是双亲Y的左孩子，则把X的右孩子，右孩子的右孩子……都与Y用连线相连。

(2)去掉原有的双亲到右孩子的连线。

图5-15给出了一棵二叉树转化为树的过程。图5-15二叉树转换成树将一个森林转换成二叉树的方法是：先将森林中的每一棵树转换为二叉树；再将第一棵树的根作为转换后二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树的右子树，第三棵树作为转换后的二叉树根的右子树的右子树，如此类推下去，就将一个森林转换为一棵二叉树，如图5-16所示。图5-16森林和对应的二叉树

5.6线 索 二 叉 树

5.6.1线索二叉树的建立

为了记录结点的前趋和后继信息，可在原来的二叉链表中增加一个前趋指针域(pred)和一个后继指针域(succ)，分别指向该结点在某种次序下的前趋结点和后继结点，使结点的结构为这样做显然会浪费不少存储空间。考虑到在n个结点的二叉链表中含有n+1个空指针域，因此可以利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针。这种附加的指针称为线索；加上了线索的二叉链表称为线索链表；相应的二叉树称为线索二叉树(ThreadedBinaryTree)。为了区分一个结点的指针域是指向其孩子的指针，还是指向其前趋或后继的线索，可在每个结点中增加两个线索标志域。这样，线索链表中的结点结构为其中图5-17中序线索二叉树及其二叉链表表示5.6.2访问线索二叉树

1．查找某结点 *p在指定次序下的前趋结点和后继结点

在建立了线索二叉树后，如何在线索二叉树中查找结点的后继或前趋呢？

在中序线索二叉树中，查找结点 *p的中序后继结点分两种情况：

(1)若 *p的右子树为空，则p->rchild为右线索，直接指向 *p的中序后继结点。

(2)若*p的右子树非空，则*p的中序后继必是其右子树中第一个中序遍历到的结点，即从*p的右孩子开始沿左指针链向下找，直至找到一个没有左孩子的结点为止。这个结点是*p的右子树中“最左下”的结点，它就是*p的中序后继结点。如图5-18所示，其中*p的中序后继结点是结点*s。应用类似的方法，可以在中序线索树中查找结点 *p的中序前趋结点。若 *p的左子树为空，则p->lchild为左线索，直接指向 *p的中序前趋结点；若 *p的左子树非空，则从 *p的左孩子出发，沿右指针链往下查找，直至找到一个没有右孩子的结点为止。该结点是 *p的左子树中“最右下”的结点，是 *p的左子树中最后一个中序遍历到的结点，它就是 *p的中序前趋结点。如图5-19所示，其中 *p的中序前趋结点是结点 *t。图5-18*p的中序后继结点 *s图5-19*p的中序前趋结点 *t在后序线索二叉树中，查找指定结点*p的后序前趋结点的方法是：

(1)若p->ltag=1(左子树为空)，则p->lchild即为前趋结点。

(2)若p->ltag=0(左子树非空)，则

①当p->rtag=0(右子树非空)，则p->rchild为前趋结点；

②当p->rtag=1(右子树为空)，则p->lchild为前趋结点。如图5-20所示，其中的虚线表示线索，可以看出：H的后序前趋结点是B，C的前趋是F，A的前趋是C，F的前趋是G。

在后序线索二叉树中，查找指定结点 *p的后序后继结点的方法是：

(1)若 *p为根，则后继为空。

(2)若 *p是其双亲的右孩子，则其双亲即为后序后继结点。

(3)若 *p是其双亲的左孩子，但 *p没有右兄弟时，则 *p的后序后继结点是其双亲结点。

(4)若 *p是其双亲的左孩子，但 *p有右兄弟时，则 *p的后序后继结点是其双亲的右子树中第一个后序遍历到的结点，它是该子树中“最左下”的叶子结点。图5-20后序线索二叉树图5-20后序线索二叉树

2．遍历线索二叉树

遍历某种次序的线索二叉树，只要从该次序的开始结点出发，查找结点在该次序下的后继，直至查找到终端结点为止。这对于中序和前序线索二叉树是十分简单的，无须像非线索树遍历那样，引入栈来保存留待以后访问的子树信息。

5.7二叉树的应用

5.7.1哈夫曼树及其应用

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

1．基本概念

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

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

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

图5-21中看出。图5-21四结点构成的三种二叉树设路径长度用PL表示，则二叉树1、二叉树2和二叉树3的路径长度分别为

PL1=0+1+1+2=4，PL2=0+1+1+2=4，

PL3=0+1+2+3=6

当树中的结点被赋予一个称之为权的有某种意义的实数时，则该结点的带权路径长度为结点到树根之间的路径长度与结点权值的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，记做：

(5-5)在有n个带权叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树被称为最优二叉树或哈夫曼树。

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

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

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

在叶子数和权值相同的二叉树中，完全二叉树不一定是最优二叉树。例如，对于权值分别为2，4，5，7的四个结点a，b，c，d的集合而言，构造出的完全二叉树和哈夫曼树如图5-23所示。图5-23完全二叉树与哈夫曼树可以计算出完全二叉树的带权路径长度为

WPL=2×2+4×2+5×2+7×2=36

哈夫曼树的带权路径长度为

WPL=2×3+4×3+5×2+7×1=35

2.哈夫曼树的构造

哈夫曼最早给出了一个带有一般规律的算法来构造哈夫曼树。图5-24哈夫曼树的构造过程图5-25结点的存储结构图5-26构造哈夫曼树

3.哈夫曼编码

哈夫曼树的应用很广泛，下面讨论哈夫曼树在通信编码中的应用。

如何构造前缀码，并且使传送的电文长度最小呢？

利用二叉树来设计二进制的前缀码。例如，有一棵二叉树如图5-27所示，其四个叶子结点分别表示a、b、c和d这四个字符，且约定左分支表示字符0，右分支表示字符1，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码，这样得到的一定是二进制前缀编码。由图5-27所得a、b、c和d的二进制前缀编码分别为0、10、110和11。图5-27前缀编码示例

4.哈夫曼树译码

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

树形结构的一个重要应用是用来组织目录。树形结构的目录称为树目录。

1.二叉排序树的概念

如果一棵二叉树的每个结点对应一个关键码，并且每个结点的左子树中所有结点的