第7章树和二叉树

1、2011年5月11日星期三1第 7 7 章 树 知 识 点树的基本概念与术语树的基本概念与术语二叉树及二叉树的存储结构二叉树及二叉树的存储结构二叉树的遍历及线索二叉树二叉树的遍历及线索二叉树一般树和二叉树的转换一般树和二叉树的转换哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码 难难 点点二叉树遍历算法的设计二叉树遍历算法的设计利用二叉树遍历算法，解决简单应用问题利用二叉树遍历算法，解决简单应用问题哈夫曼树的算法哈夫曼树的算法 要 求 熟练掌握以下内容熟练掌握以下内容: 树的基本概念和术语树的基本概念和术语 二叉树定义和存储结构二叉树定义和存储结构 二叉树遍历的概念和二叉树遍历的算法二叉树遍历的概念和

2、二叉树遍历的算法 哈夫曼树的建立哈夫曼树的建立了解以下内容：了解以下内容： 树和二叉树之间的相互转换方法树和二叉树之间的相互转换方法 线索二叉树的概念线索二叉树的概念 哈夫曼编码哈夫曼编码第 7 7 章 目 录 7-1 树的定义和术语树的定义和术语 7-2 二叉树二叉树 7-3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 7-4 二叉树的转换二叉树的转换 7-5 二叉树的应用二叉树的应用 7-6 哈夫曼树及其应用哈夫曼树及其应用 小小 结结 验证性实验验证性实验7 树子系统树子系统 自主设计实验自主设计实验7标识符树与表达式求值标识符树与表达式求值 单元练习单元练习77-1 树的定义和术语7

3、-1-1 7-1-1 树的定义树的定义1树的定义树的定义 树是树是n（n0）个有限数据元素的集合。在任意一棵非空树）个有限数据元素的集合。在任意一棵非空树T中：中：（1）有且仅有一个特定的称为树根（）有且仅有一个特定的称为树根（root）的结点，根结点无前趋结点；）的结点，根结点无前趋结点；（2）当）当n1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m（m0）个互不相交的集合）个互不相交的集合T1，T2，Tm，其中每一个集合，其中每一个集合Ti（1 i m）本身又是一棵树，并且称为根）本身又是一棵树，并且称为根的子树。的子树。 树的定义采用了递归定义的方法，即在树的定义中又

4、用到树的概念，这正树的定义采用了递归定义的方法，即在树的定义中又用到树的概念，这正好反映了树的固有特性。好反映了树的固有特性。 1 2 3 4 图图 7-1 树结构示意图树结构示意图2树的其它表示法树的其它表示法 图图7-1是树的结构表示法，是一种直观的画法，其特点是对树的逻辑结构的是树的结构表示法，是一种直观的画法，其特点是对树的逻辑结构的描述非常直观、清晰。是使用最多的一种描述方法。除此以外，还有以下几种描述非常直观、清晰。是使用最多的一种描述方法。除此以外，还有以下几种描述树的方法：描述树的方法：ABCHGFEDJI（1）嵌套集合法）嵌套集合法 嵌套集合法，也称为文氏图法（嵌套集合法，也

5、称为文氏图法（Venn Diagram），它是用集合以及集合的），它是用集合以及集合的包含关系来描述树形结构，每个圆圈表示一个集合，套起来的圆圈表示包含关系。包含关系来描述树形结构，每个圆圈表示一个集合，套起来的圆圈表示包含关系。图图7-2 (a)就是一棵树的嵌套集合表示。就是一棵树的嵌套集合表示。 ABCEIJDFGH图图7-2 （a）嵌套集合表示）嵌套集合表示ABCHGFEDJI ( 2 ) 圆括号表示法圆括号表示法 圆括号表示法也称为广义表表示法，它是使用括号将集合层次与包含关圆括号表示法也称为广义表表示法，它是使用括号将集合层次与包含关系显示出来。系显示出来。 ( A ( B ( D,

6、 E ( I, J ), F ), C ( G, H ) ) ) ( 3 ) 凹入法凹入法 凹入法是用不同宽度的行来显示各结点，而行的凹入程度体现了各结点凹入法是用不同宽度的行来显示各结点，而行的凹入程度体现了各结点集合的包含关系。树的凹入表示法主要用于树的屏幕显示和打印输出。集合的包含关系。树的凹入表示法主要用于树的屏幕显示和打印输出。ABCHGFEDJI图图7-2（b）凹入表示法）凹入表示法ABCEDJFGHIABCHGFEDJI7-1-2 基本术语基本术语（1）结点）结点树的结点包含一个数据及若干指向树的结点包含一个数据及若干指向其子树的分支。其子树的分支。（2）结点的度）结点的度结点所

7、拥有的子树数称为该结结点所拥有的子树数称为该结点的度（点的度（Degree）。）。（3）树的度）树的度树中各结点度的最大值称为该树树中各结点度的最大值称为该树的度。的度。（4）叶子（终端结点）叶子（终端结点）度为零的结点称为叶度为零的结点称为叶子结点。子结点。（5）分枝结点）分枝结点度不为零的结点称为分支结点。度不为零的结点称为分支结点。（6）兄弟结点）兄弟结点同一父亲结点下的子结点称为同一父亲结点下的子结点称为兄弟结点。兄弟结点。（7）层数）层数树的根结点的层数为树的根结点的层数为1，其余结点，其余结点的层数等于它双亲结点的层数加的层数等于它双亲结点的层数加1。（8）树的深度）树的深度树中结

8、点的最大层数称为树的树中结点的最大层数称为树的深度（或高度）。深度（或高度）。（9）森林）森林零棵或有限棵互不相交的树的集合零棵或有限棵互不相交的树的集合称为森林。称为森林。 在数据结构中，树和森林并不象自然界里有在数据结构中，树和森林并不象自然界里有一个明显的量的差别。任何一棵树，只要删去根一个明显的量的差别。任何一棵树，只要删去根结点就成了森林，见图结点就成了森林，见图6-3。 (a) (a) 树树 (b) (b) 移去根结点后成为森林移去根结点后成为森林 图图7-3（10）有序树和无序树）有序树和无序树树中结点的各子树从树中结点的各子树从左到右是有次序的（即不能互换位置），称这样左到右是

9、有次序的（即不能互换位置），称这样的树为有序树；否则称为无序树。的树为有序树；否则称为无序树。ABCHGFEDJIKJBCDEFGHIK7-2 二叉树7-2-1 二叉树的定义二叉树的定义1定义定义 二叉树是有二叉树是有n（n=0）个结点的有限集合。）个结点的有限集合。（1）该集合或者为空（）该集合或者为空（n=0）；）；（2）或者由一个根结点及两个不相交的分别称为左子树）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；和右子树组成的非空树；（3）左子树和右子树同样又都是二叉树。）左子树和右子树同样又都是二叉树。 通俗地讲：在一棵非空的二叉树中，每个结点至多通俗地讲：在一棵非空

10、的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。所以，二叉树是特殊的有序树。次序不能任意交换。所以，二叉树是特殊的有序树。2二叉树的形态二叉树的形态 根据定义，二叉树可以有五种基本形态，如图根据定义，二叉树可以有五种基本形态，如图7-4所示。所示。 (a) (b) (c) (d) (e) 图图7-4 二叉树的基本形态二叉树的基本形态 其中：（其中：（a）空二叉树；）空二叉树； （b）仅有根结点的二叉树；）仅有根结点的二叉树； （c）右子树为空的二叉树；）右子树为空的二叉树； （d）左子树为空的二叉树；

11、）左子树为空的二叉树； （e）左、右子树均非空的二叉树。）左、右子树均非空的二叉树。 LchildLchildRchildRchild3二叉树的基本操作：二叉树的基本操作：（1） CreateBT（）：（）： 创建一棵二叉树。创建一棵二叉树。（2）ShowTree(BT *T)：按凹入法显示二叉树。：按凹入法显示二叉树。（3）Preorder(BT *T)：按先序（根、左、右）遍历二叉树上所有结点。：按先序（根、左、右）遍历二叉树上所有结点。（4）Inorder(BT *T)： 按中序（左、根、右）遍历二叉树上所有结点。按中序（左、根、右）遍历二叉树上所有结点。（5）Postorder(BT

12、*T)：按后序（左、右、根）遍历二叉树上所有结点。：按后序（左、右、根）遍历二叉树上所有结点。（6）Levelorder(BT *T)：按层次遍历二叉树上所有结点。：按层次遍历二叉树上所有结点。（7）Leafnum(BT *T)： 求二叉树叶结点总数。求二叉树叶结点总数。（8）TreeDepth(BT *T)： 求二叉树的深度。求二叉树的深度。7-2-2 7-2-2 二叉树的性质二叉树的性质性质性质1 一棵非空二叉树的第一棵非空二叉树的第i层上最多有层上最多有2 i1个结点（个结点（i 1）。）。 一棵非空二叉树的第一层有一棵非空二叉树的第一层有1个结点，第二层最多有个结点，第二层最多有2个结

13、点，第三层最多个结点，第三层最多有有4个结点个结点，利用归纳法即可证明第，利用归纳法即可证明第i层上最多有层上最多有2 i1个结点。个结点。性质性质2 深度为深度为h的二叉树中最多具有的二叉树中最多具有2 h 1个结点（个结点（h 1）。）。证明：根据性质证明：根据性质1，当深度为，当深度为h的二叉树每一层都达到最多结点数时，它的和（的二叉树每一层都达到最多结点数时，它的和（n）最大，即：最大，即： 命题正确。命题正确。 （1）满二叉树）满二叉树 一棵深度为一棵深度为h h，且有，且有2 2 h h11个结点的二叉树称为满二叉树。图个结点的二叉树称为满二叉树。图7-57-5所示是所示是一棵深度

14、为一棵深度为4 4的满二叉树，其特点是每一层上的结点都具有最大的结点数。如的满二叉树，其特点是每一层上的结点都具有最大的结点数。如果对满二叉树的结点进行连续的编号，约定编号从根结点起，从上往下，自果对满二叉树的结点进行连续的编号，约定编号从根结点起，从上往下，自左向右，由此可以引出完全二叉树的定义。左向右，由此可以引出完全二叉树的定义。123876541091112131415图图7-5 7-5 满二叉树满二叉树（2）完全二叉树）完全二叉树 深度为深度为h，有，有n个结点的二叉树，当且仅当每一个结点都与深度为个结点的二叉树，当且仅当每一个结点都与深度为h的的满二叉树中编号从满二叉树中编号从1至

15、至n的结点一一对应时，称此二叉树为完全二叉树。如图的结点一一对应时，称此二叉树为完全二叉树。如图7-6（a）所示为一棵完全二叉树。）所示为一棵完全二叉树。ABCHGFEDJI图图7-6（a）一棵完全二叉树）一棵完全二叉树 如图如图7-6（b）所示则不是完全二叉树。）所示则不是完全二叉树。图图7-67-6（b b） 一棵非完全二叉树一棵非完全二叉树 完全二叉树除最后一层外，其余各层都是满的，并且最后一层或者为满，完全二叉树除最后一层外，其余各层都是满的，并且最后一层或者为满，或者仅在右边缺少连续若干个结点。或者仅在右边缺少连续若干个结点。ABCGFEDH性质性质3 对于一棵有对于一棵有n个结点的

16、完全二叉树，若按满二叉树的同样方法对结点进个结点的完全二叉树，若按满二叉树的同样方法对结点进行编号，（见图行编号，（见图7-5）则对于任意序号为）则对于任意序号为i的结点，有：的结点，有： （1）若）若i1，则序号为，则序号为i的结点的父结点的序号为的结点的父结点的序号为i/2； 若若i1，则序号为，则序号为i的结点是根结点。的结点是根结点。（2）若）若2in，则序号为，则序号为i的结点的左孩子结点的序号为的结点的左孩子结点的序号为2i； 若若2in，则序号为，则序号为i的结点无左孩子。的结点无左孩子。（3）若）若2i1n，则序号为，则序号为i的结点的右孩子结点的序号为的结点的右孩子结点的序号

17、为2i1； 若若2i1n，则序号为，则序号为i的结点无右孩子。的结点无右孩子。 证明略。证明略。 性质性质4 具有具有n（n0）个结点的完全二叉树（包括满二叉树）的深度（）个结点的完全二叉树（包括满二叉树）的深度（h）为：）为： 证明：由性质证明：由性质2和完全二叉树定义可知，当完全二叉树的深度为和完全二叉树定义可知，当完全二叉树的深度为h、结点个数、结点个数为为n时时 有：有： 2 h11n2 h-1 即：即： 2 h1n2 h 对不等式取对数有：对不等式取对数有： h1log2ndata); / / 输出结点的数据域输出结点的数据域 Preorder(T-lchild); / / 先序递归

18、遍历左子树先序递归遍历左子树 Preorder(T-rchild); / / 先序递归遍历右子树先序递归遍历右子树 图图7-10 先序遍历的序列为：先序遍历的序列为： A B D G C E F H动画演示动画演示2中序遍历递归过程中序遍历递归过程 若二叉树为空遍历结束，否则：若二叉树为空遍历结束，否则： （1）中序遍历根结点的左子树；）中序遍历根结点的左子树； （2）访问根结点；）访问根结点； （3）中序遍历根结点的右子树。）中序遍历根结点的右子树。void InOrder(BT *T) / / 中序遍历二叉树中序遍历二叉树BTBT if (T = =NULL) return; / / 递归

19、调用的结束条件递归调用的结束条件 Inorder(T-lchild); / / 中序递归遍历左子树中序递归遍历左子树 printf(T-data); / / 输出结点的数据域输出结点的数据域 Inorder(T-rchild); / / 中序递归遍历右子树中序递归遍历右子树 图图7-10 中序遍历的序列为：中序遍历的序列为： D G B A E C H F动画演示动画演示3后序遍历递归过程后序遍历递归过程 若二叉树为空遍历结束，否则：若二叉树为空遍历结束，否则： （1）后序遍历根结点的左子树；）后序遍历根结点的左子树； （2）后序遍历根结点的右子树。）后序遍历根结点的右子树。 （3）访问根结点

20、；）访问根结点；void PostOrder(BT *T) / / 后序遍历二叉树后序遍历二叉树BTBT if (T = =NULL) return; / / 递归调用的结束条件递归调用的结束条件 Postorder(T-lchild); / / 后序递归遍历左子树后序递归遍历左子树 Postorder(T-rchild); / / 后序递归遍历右子树后序递归遍历右子树 printf(T-data); / / 输出结点的数据域输出结点的数据域 图图7-10 后序遍历的序列为：后序遍历的序列为： G D B E H F C A动画演示动画演示4层次遍历层次遍历 按照自上而下（从根结点开始），从左

21、到右的顺序逐层访问二叉树上的所按照自上而下（从根结点开始），从左到右的顺序逐层访问二叉树上的所有结点，这样的遍历称为按层次遍历。有结点，这样的遍历称为按层次遍历。 按层次进行遍历时，当一层结点访问完后，接着访问下一层的结点，先遇按层次进行遍历时，当一层结点访问完后，接着访问下一层的结点，先遇到的结点先访问，这与队列的操作原则是一致的。因此，在进行层次遍历时，到的结点先访问，这与队列的操作原则是一致的。因此，在进行层次遍历时，可设置一个数组来模拟队列，用于保存被访问结点的子结点的地址。遍历从二可设置一个数组来模拟队列，用于保存被访问结点的子结点的地址。遍历从二叉树的根结点开始，首先将根结点指针入

22、队列，然后从队头取出一个元素，每叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：取一个元素，执行下面两个操作：（1）访问该元素所指结点；）访问该元素所指结点；（2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针依次入队。指针和右孩子指针依次入队。 此过程不断进行，直到队空为止。在层次遍历算法中，以二叉链表方式存此过程不断进行，直到队空为止。在层次遍历算法中，以二叉链表方式存储，一维数组储，一维数组qMAXLEN用以实现队列，用以实现队列，lchi

23、ld和和rchild分别是被访问结点的分别是被访问结点的左、右指针。左、右指针。void Levelorder(BT *T)/ 按层次遍历二叉树按层次遍历二叉树BT int i,j; BT *qMAXLEN,*p; / 设置一个数组来模拟队列设置一个数组来模拟队列 p=T; if (p!=NULL) / 若二叉树非空，则根结点地址入队若二叉树非空，则根结点地址入队 i=1;qi=p;j=2; while (i!=j) p=qi;printf(p-data); / 访问队首结点的数据域访问队首结点的数据域 if( p-lchild!=NULL) / 将队首结点的左孩子结点入队列将队首结点的左孩子

24、结点入队列 qj=p-lchild; j+; if(p-rchild!=NULL) / 将队首结点的右孩子结点入队列将队首结点的右孩子结点入队列 qj=p-rchild；j+； i+ ； 图图7-10的二叉树，按层次遍历所得到的结果序列为：的二叉树，按层次遍历所得到的结果序列为： A B C D E F G H 【例例7-17-1】 二叉树，如图二叉树，如图7-147-14所示，求它的先序遍历、中序遍历、后序遍历和所示，求它的先序遍历、中序遍历、后序遍历和层次遍历。层次遍历。 先序遍历的序列：先序遍历的序列： A B D G E H C F I KA B D G E H C F I K 中序遍

25、历的序列：中序遍历的序列： D G B H E A F K I CD G B H E A F K I C 后序遍历的序列：后序遍历的序列： G D H E B K I F C AG D H E B K I F C A 层次遍历的序列：层次遍历的序列： A B C D E F G H I KA B C D E F G H I KABCIKFEDHG图图7-13 7-13 二叉树二叉树【例例7-27-2】设表达式设表达式A AB B* *（C+DC+D）+E/+E/（F+GF+G）的二叉树表示如图）的二叉树表示如图7-147-14所示。试写所示。试写出它的先序遍历、中序遍历和后序遍历。出它的先序遍

26、历、中序遍历和后序遍历。 先序遍历的结果（即前缀表达）：先序遍历的结果（即前缀表达）： + + A A * * B + C D / E + F G B + C D / E + F G 中序遍历的结果：中序遍历的结果： A A B B * * C + D + E / F + G C + D + E / F + G后序遍历（即后缀表达式）：后序遍历（即后缀表达式）： A B C D + A B C D + * * E F G + / + E F G + / +图图7-14 7-14 表达式二叉树表达式二叉树A*/EF+BDC-+G7-3-2 7-3-2 恢复二叉树恢复二叉树 在统一绘图软件或其它绘

27、图软件中存在着这样的问题：如何存储一个用树在统一绘图软件或其它绘图软件中存在着这样的问题：如何存储一个用树表示的图形数据结构？在研制统一绘图软件系统时是用这样的办法来处理的：表示的图形数据结构？在研制统一绘图软件系统时是用这样的办法来处理的：（1 1）对于用链表结构表示的图形数据结构，我们把每一个结点去掉指针项，只）对于用链表结构表示的图形数据结构，我们把每一个结点去掉指针项，只按结点的中序序列存储，并给出这棵树的前序（或后序）按结点的中序序列存储，并给出这棵树的前序（或后序）“序表序表”。（2 2）图形结构调入内存时，由中序的结点表及）图形结构调入内存时，由中序的结点表及“序表序表”，形成的

28、前序和中序数，形成的前序和中序数组（或后序和中序数组），恢复图形数据结构。组（或后序和中序数组），恢复图形数据结构。 二叉树的先序遍历是先访问根结点，然后再遍历根结点的左子树，最后遍二叉树的先序遍历是先访问根结点，然后再遍历根结点的左子树，最后遍历根结点的右子树。即在先序序列中，第一个结点必定是二叉树的根结点。历根结点的右子树。即在先序序列中，第一个结点必定是二叉树的根结点。 中序遍历则是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，中序遍历则是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点根结点在中序序列中

29、必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。 根据这两个子序列，先由先序序列确定第一个结点为根结点；知道根结点后，根据这两个子序列，先由先序序列确定第一个结点为根结点；知道根结点后，按中序序列可以划分左、右子树。按中序序列可以划分左、右子树。 在先序序列中，左子树序列的第一个结点是左子树的根结点，右子序列的第在先序序列中，左子树序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。一个结点是右子树的根结点。这样，就

30、确定了二叉树的三个结点。 同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以恢复一棵二叉树。个子序列，如此递归下去，当取尽先序序列中的结点时，便可以恢复一棵二叉树。 1. 1. 由前序和中序恢复二叉树由前序和中序恢复二叉树（1 1）根据前序序列确定树的根（第一个结点），根据中序序列确定左子树和）根据前序序列确定树的根（第一个结点），根据中序序列确定左子树和右子树；右子树；（2 2）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到父）分别找出左子树和

31、右子树的根结点，并把左、右子树的根结点联到父（fatherfather）结点上去；）结点上去；（3 3）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1 1个个结点或结点或2 2个结点或空为止。个结点或空为止。【例例7-37-3】由下列前序序列和中序序列恢复二叉树。由下列前序序列和中序序列恢复二叉树。 前序序列：前序序列：A C B R S E D F M L K 中序序列：中序序列：R B S C E A F D L K M 首先，由先序序列可知，结点首先，由先序序列可知，结点A A是二叉树的根结点；其次，根据中序序

32、列，是二叉树的根结点；其次，根据中序序列，在在A A之前的所有结点都是根结点左子树的结点，在之前的所有结点都是根结点左子树的结点，在A A之后的所有结点都是根结点之后的所有结点都是根结点右子树的结点：右子树的结点： 前序序列：前序序列： A C B R S E D F M L K 根根 左子树左子树 右右 子树子树 中序序列：中序序列： R B S C E A F D L K M 左子树左子树 根根 右子树右子树 继续对左、右子树进行分解：继续对左、右子树进行分解： 左子树：左子树： 右子树：右子树： 前序前序：前序前序：C B R S E D F M L K 根根 左子树左子树 右子树右子树

33、 根根 左子树左子树 右子树右子树 中序前序：中序前序：R B S C E F D L K M 左子树左子树 根根 右子树右子树 左子树左子树 根根 右子树右子树 再按同样的方法继续分解下去，最后得到如图再按同样的方法继续分解下去，最后得到如图7-157-15所示的整棵二叉树。所示的整棵二叉树。ACDRMFEBLSK图图7-157-15 上述过程是一个递归过程，上述过程是一个递归过程，其递归算法的思想是：先根据先其递归算法的思想是：先根据先序序列的第一个元素建立根结点；序序列的第一个元素建立根结点；然后在中序序列中找到该元素，然后在中序序列中找到该元素，确定根结点的左、右子树的中序确定根结点的

34、左、右子树的中序序列；再在先序序列中确定左、序列；再在先序序列中确定左、右子树的先序右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。序列与中序序列建立右子树。2 2由中序和后序恢复二叉树由中序和后序恢复二叉树 由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。其方法为：由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。其方法为：（1 1）根据后序序列找出根结点（最后一个），根据中序序列确定左、右子树；）根据后序序列找出根结点（最后一个），根据中序序列确定左、右子树；（2

35、 2）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到父）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到父（fatherfather）结点上去；）结点上去；（3 3）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1 1个个结点或结点或2 2个结点或空为止。个结点或空为止。【 例例7-4 7-4 】由下列中序序列和后序序列恢复二叉树。由下列中序序列和后序序列恢复二叉树。 中序序列：中序序列：C B E D A G H F J IC B E D A G H F J I 后序序列：后序序列：C E D

36、B H G J I F AC E D B H G J I F A 首先，由后序序列可知，结点首先，由后序序列可知，结点A A是二叉树的根结点；其次，根据中序序列，是二叉树的根结点；其次，根据中序序列，在在A A之前的所有结点都是根结点左子树的结点，在之前的所有结点都是根结点左子树的结点，在A A之后的所有结点都是根结点之后的所有结点都是根结点右子树的结点：右子树的结点： 后序序列：后序序列：C E D BC E D B H G J I FH G J I F A A 左子树左子树 右子树右子树 根根 中序序列：中序序列：C B E DC B E D A A G H F J IG H F J I

37、左子树左子树 根根 右子树右子树 继续分解：继续分解： 左子树：左子树： 右子树：右子树： 后序序列：后序序列：C C E DE D B B H G H G J I J I F F 左子树左子树 右子树右子树 根根 左子树左子树 右子树右子树 根根 中序序列：中序序列： C C B B E D E D G H G H F F J I J I 左子树左子树 根根 右子树右子树 左子树左子树 根根 右子树右子树 再按同样的方法再按同样的方法继续分解下去，最后继续分解下去，最后得到如图得到如图7-167-16的整棵的整棵二叉树。二叉树。ABFEIGDCJH图图7-167-16思 考 根据二叉树的前序

38、序列和后序序列能唯一恢复一棵二叉树吗？根据二叉树的前序序列和后序序列能唯一恢复一棵二叉树吗？ 7-3-3 7-3-3 线索二叉树线索二叉树1 1什么是线索二叉树什么是线索二叉树 遍历二叉树是按一定的规则将二叉树中所有结点排列为一个有序序列，这遍历二叉树是按一定的规则将二叉树中所有结点排列为一个有序序列，这实质上是对一个非线性的数据结构进行线性化的操作。经过遍历的结点序列，实质上是对一个非线性的数据结构进行线性化的操作。经过遍历的结点序列，除第一个结点和最后一个结点以外，其余每个结点都有且仅有一个直接前驱结除第一个结点和最后一个结点以外，其余每个结点都有且仅有一个直接前驱结点和一个直接后继结点。

39、点和一个直接后继结点。 当以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而不当以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而不能直接得到结点任意一个序列中的直接前趋结点和直接后继结点是什么，这种能直接得到结点任意一个序列中的直接前趋结点和直接后继结点是什么，这种信息只有在对二叉树遍历的动态过程中才能得到得到。信息只有在对二叉树遍历的动态过程中才能得到得到。 在用二叉链表存储的二叉树中，单个结点的二叉树有两个空指针域，如图在用二叉链表存储的二叉树中，单个结点的二叉树有两个空指针域，如图7-17(a) 7-17(a) 所示，两个结点的二叉树有三个空指针域，如图所示，两个结

40、点的二叉树有三个空指针域，如图7-17(b) 7-17(b) 所示。所示。 不难证明：一个具有不难证明：一个具有n n个结点的二叉树，若采用二叉链表存储结构，在其个结点的二叉树，若采用二叉链表存储结构，在其总共总共2n2n个指针域中只有个指针域中只有n n-1 1个指针域是用来存储结点子树的地址，而另外个指针域是用来存储结点子树的地址，而另外n+1n+1个都个都是空指针域。充分利用二叉链表存储结构中的空指针域，可以保存结点在某种遍是空指针域。充分利用二叉链表存储结构中的空指针域，可以保存结点在某种遍历序列中的直接前趋和直接后继的地址信息。历序列中的直接前趋和直接后继的地址信息。 指向直接前趋结

41、点或指向直接后继结点的指针称为线索（指向直接前趋结点或指向直接后继结点的指针称为线索（ThreadThread），带有线），带有线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。程称为线索化。 A BA 图图7-17(a) 单结点的二叉链表图单结点的二叉链表图 7-17(b) 两个结点的二叉链表两个结点的二叉链表 2 2线索二叉树的方法线索二叉树的方法 由于二叉树结点的序列可由不同的遍历方法得到，因此，线索二叉树也有由于二叉树结点的序列可由不同的遍历方法得到，因此，线索二叉树也有先序线索二

42、叉树、中序线索二叉树和后序线索二叉树三种。在三种线索二叉树先序线索二叉树、中序线索二叉树和后序线索二叉树三种。在三种线索二叉树中一般以中序线索化用得最多，所以下面以图中一般以中序线索化用得最多，所以下面以图7-107-10（P138P138）所示的二叉树为）所示的二叉树为例，说明中序线索二叉树的方法：例，说明中序线索二叉树的方法：（1 1）先写出原二叉树的中序遍历序列：）先写出原二叉树的中序遍历序列： D G B A E C H FD G B A E C H F（2 2）若结点的左子树为空，则此线索指针将指向前一个遍历次序的结点；）若结点的左子树为空，则此线索指针将指向前一个遍历次序的结点；（

43、3 3）若结点的右子树为空，则此线索指针将指向下一个遍历次序的结点。）若结点的右子树为空，则此线索指针将指向下一个遍历次序的结点。 图图7-107-10二叉树的中序遍历序列：二叉树的中序遍历序列： D G B A E C H FD G B A E C H F。其中序线索二叉树的结果如图其中序线索二叉树的结果如图7-187-18所示。其中实线表示指针，虚线表示线索。所示。其中实线表示指针，虚线表示线索。 图图7-18 中序线索二叉树中序线索二叉树 线索二叉树的结点结构定义如下：线索二叉树的结点结构定义如下：typedef struct threadbinode datatype data; /

44、二叉链表的结点二叉链表的结点 bool ltag;/ 左孩子标志，当左孩子标志，当ltag为为true时，时， / 表示左孩子存在（表示左孩子存在（lChild所指为该所指为该 / 结点左孩子）；反之，则表示左孩结点左孩子）；反之，则表示左孩 / 子不存在（子不存在（lChild所指为该结点直所指为该结点直 / 接后继）接后继） struct threadbinode lChild; / 左孩子指针左孩子指针 bool rtag; / 其含义与其含义与ltag类似类似 struct threadbinode rChild; / 右孩子指针右孩子指针 ThreadBiNode; / 二叉链表结点

45、的类型二叉链表结点的类型二叉树进行中序线索化的递归函数代码如下：二叉树进行中序线索化的递归函数代码如下：void InThreadBiTree(ThreadBiNode *T, ThreadBiNode *pre, ThreadBiNode *rear) / pre指向整个二叉树指向整个二叉树T中序序列的直接前驱节点，中序序列的直接前驱节点，/ rear指向整个二叉树指向整个二叉树T中序序列的直接后继节点。中序序列的直接后继节点。 if (true=T-ltag) InThreadBiTree(T-lChild, pre, T); / 左子树的直接前驱就是整棵二叉树的左子树的直接前驱就是整棵二

46、叉树的 /直接前驱，左子树的直接后继就是整棵二叉树的根结直接前驱，左子树的直接后继就是整棵二叉树的根结 else T-lChild=pre; if (true=T-rtag) InThreadBiTree(T-rChild, T, rear);/ 右子树的直接前驱就是整棵二叉树的根右子树的直接前驱就是整棵二叉树的根 / 结点，右子树的直接后继就是整棵二叉树的直接后继结点，右子树的直接后继就是整棵二叉树的直接后继 else T-rChild=rear; 由于整棵二叉树中序序列的直接前驱和直接后继均可为空，因此对二叉由于整棵二叉树中序序列的直接前驱和直接后继均可为空，因此对二叉树树T进行中序线索化

47、可采用语句进行中序线索化可采用语句InThreadBiTree(T, NULL, NULL);。 另外，为了便于操作，在存储线索二叉树时需要增设一个结点，其结构另外，为了便于操作，在存储线索二叉树时需要增设一个结点，其结构与其他线索二叉树的结点结构一样。与其他线索二叉树的结点结构一样。3线索二叉树的优点线索二叉树的优点（1）利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉）利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。树的遍历速度快，且节约存储空间。（2）任意一个结点都能直接找到它的前一个或后一个遍历顺序的结点。）任意一个结点都能直

48、接找到它的前一个或后一个遍历顺序的结点。 4线索二叉树的缺点线索二叉树的缺点（1）结点的插入和删除麻烦，且速度也较慢。）结点的插入和删除麻烦，且速度也较慢。（2）线索子树不能共用。）线索子树不能共用。7-4-1 7-4-1 一般树转换为二叉树一般树转换为二叉树 如果对树或森林采用链表存储并设定一定的规则，如果对树或森林采用链表存储并设定一定的规则，就可用二叉树结构表示树和森林。这样，对树的操作就可用二叉树结构表示树和森林。这样，对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现就可以借助二叉树存储，利用二叉树上的操作来实现。实现。1 1一般树和二叉树的二叉链表存储结构比较一般树和二叉

49、树的二叉链表存储结构比较 一般树是无序树，树中结点的各孩子的次序是无一般树是无序树，树中结点的各孩子的次序是无关紧要的；二叉树中结点的左、右孩子结点是有区别关紧要的；二叉树中结点的左、右孩子结点是有区别的。为避免发生混淆，我们约定树中每一个结点的孩的。为避免发生混淆，我们约定树中每一个结点的孩子结点按从左到右的次序排列。如图子结点按从左到右的次序排列。如图7-197-19所示为一棵所示为一棵一般树。一般树。7-4 二叉树的转换 根结点根结点A A有有B B、C C、D D三个孩子，可以认为结点三个孩子，可以认为结点B B为为A A的长子，结点的长子，结点C C为为B B的的次弟，结点次弟，结点

50、D D为为C C的次弟。的次弟。ABCKJFEDMLGHI图图7-19 7-19 一般树一般树 图图7-20为一般树和二叉树的二叉链表存储结构示意图为一般树和二叉树的二叉链表存储结构示意图长子地址长子地址 结点信息结点信息 次弟地址次弟地址左子树地址左子树地址结点信息结点信息右子树地址右子树地址 (a) (a) 一般树双链表存储结构一般树双链表存储结构 (b) (b) 二叉树双链表存储结构二叉树双链表存储结构 图图7-207-20 2 2将一棵树转换为二叉树的方法：将一棵树转换为二叉树的方法： 只要把一般树的长子作为其父结点的左子树；把一般树的次弟作为其兄只要把一般树的长子作为其父结点的左子树

51、；把一般树的次弟作为其兄结点的右子树，即可以把一棵一般树转换为一棵二叉树。结点的右子树，即可以把一棵一般树转换为一棵二叉树。 整个转换可以分为三步：整个转换可以分为三步：（1 1）连线）连线链接树中所有相邻的亲兄弟之间连线。链接树中所有相邻的亲兄弟之间连线。（2 2）删线）删线保留父结点与长子的连线，打断父结保留父结点与长子的连线，打断父结点与非长子结点之间的连线。点与非长子结点之间的连线。（3 3）旋转）旋转以根结点为轴心，将整棵树顺时针旋以根结点为轴心，将整棵树顺时针旋转一定的角度，使之层次分明。转一定的角度，使之层次分明。 可以证明，树作这样的转换所构成的二叉树是唯可以证明，树作这样的转

52、换所构成的二叉树是唯一的。图一的。图7-21 (a)7-21 (a)、(b)(b)、(C)(C)给出了图给出了图7-197-19所示的一所示的一般树转换为二叉树的转换过程。般树转换为二叉树的转换过程。图图7-21(a) 7-21(a) 链接相邻亲兄弟结点链接相邻亲兄弟结点 ABCKJFEDMLGHI 图图 7-21 (b) 删去与非长子结点的链接删去与非长子结点的链接 ABCKJFEDMLGHI图图7-21(c) 7-21(c) 将兄弟结点顺时针旋转后得到的二叉树将兄弟结点顺时针旋转后得到的二叉树ABCKJFEDMLGHI1234567 结结 论：论：（1）在转换产生的二叉树中，左分支上的各结

53、点在原来的树中是父子关系；）在转换产生的二叉树中，左分支上的各结点在原来的树中是父子关系；而右分支上的各结点在原来的树中是兄弟关系。而右分支上的各结点在原来的树中是兄弟关系。（2）由于树的根结点无兄弟，所以转换后的二叉树的根结点必定无右子树。）由于树的根结点无兄弟，所以转换后的二叉树的根结点必定无右子树。（3）一棵树采用长子、兄弟表示法所建立的存储结构与它所对应的二叉树的）一棵树采用长子、兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。二叉链表存储结构是完全相同的。（4）一般树转换为二叉树以后，将使树的深度增加。如图）一般树转换为二叉树以后，将使树的深度增加。如图7

54、-19的树深度为的树深度为4，转换为二叉树以后，深度就变成转换为二叉树以后，深度就变成7了，见图了，见图7-21（c）。）。7-4-2 森林转换为二叉树森林转换为二叉树 森林是若干棵树的集合。只要将森林中的每一棵森林是若干棵树的集合。只要将森林中的每一棵树的根视为兄弟，而每一棵树又可以用二叉树表示，树的根视为兄弟，而每一棵树又可以用二叉树表示，这样，森林也同样可以用二叉树来表示了。这样，森林也同样可以用二叉树来表示了。 森林转换为二叉树的方法如下：森林转换为二叉树的方法如下：（1）将森林中的每一棵树转换成相应的二叉树。）将森林中的每一棵树转换成相应的二叉树。（2）第一棵二叉树保持不动，从第二棵

55、二叉树开始，）第一棵二叉树保持不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右子树，直到把最后一棵二叉树的根结点作为其点的右子树，直到把最后一棵二叉树的根结点作为其前一棵二叉树的右子树为止。前一棵二叉树的右子树为止。 【例例7-5】将图将图7-22(a) 给出的森林转换为二叉树。给出的森林转换为二叉树。 ABCKJFEDLGHI图图7-22(a) 7-22(a) 森林森林ABCKJFEDLGHI图图7-22(b)7-22(b)森林中每棵树转换为二叉树森林中每棵树转换为二叉树图图7-22(c) 7-22(c) 最终最终的

56、二叉树的二叉树ABCKJFEGLDHI7-4-3 二叉树转换为树和森林二叉树转换为树和森林 树转换为二叉树以后，其根结点必定无右子树；而森林转换为二叉树树转换为二叉树以后，其根结点必定无右子树；而森林转换为二叉树以后，其根结点有右分支。显然这一转换过程是可逆的，即可以依据二叉以后，其根结点有右分支。显然这一转换过程是可逆的，即可以依据二叉树的根结点有无右子树，将一棵二叉树还原为树或森林。树的根结点有无右子树，将一棵二叉树还原为树或森林。动画演示动画演示 二叉树转换为树或森林的方法：二叉树转换为树或森林的方法：（1）若某结点是其父结点的左孩子，则把该结点的右孩子、右孩子的右孩子，直）若某结点是其

57、父结点的左孩子，则把该结点的右孩子、右孩子的右孩子，直到最后一个右孩子都与该结点的父结点连起来；到最后一个右孩子都与该结点的父结点连起来；（2）删掉原二叉树中所有的父结点与右孩子结点的连线；）删掉原二叉树中所有的父结点与右孩子结点的连线；（3）整理（）整理（1）、（）、（2）的结果，使之层次分明，显示出树或森林的形状。）的结果，使之层次分明，显示出树或森林的形状。 ABCJFEDGHI 图图7-23(a) 7-23(a) 二叉树二叉树 图图7-23 二叉树还原深林的过程二叉树还原深林的过程 ABCJFEDGHI (b) (b) 加连线加连线ABCJFEDGHI (c) (c) 删除父结点与右孩

58、子的连线删除父结点与右孩子的连线 图图7-23 二叉树还原深林的过程二叉树还原深林的过程 (d) (d) 还原后的森林还原后的森林ABCJFEDGHI【例例7-67-6】将图将图7-24(a)7-24(a)给出的二叉树转换为一般树给出的二叉树转换为一般树 (a) (a) 二叉树二叉树 (b) (b) 加连线加连线 (c)(c)删除父结点与右孩子的连线删除父结点与右孩子的连线图图7-24 二叉树转换为树的过程二叉树转换为树的过程 ABCFEDGHIABCFEDGHIABCFEDGHI 图图7-24(d) 7-24(d) 还原后的树还原后的树ABCFEDGHI7-5 二叉树的应用7-5-1 二叉树

59、的基本应用二叉树的基本应用1 1统计二叉树叶子结点数统计二叉树叶子结点数（1 1）基本思想：）基本思想： 若二叉树结点的左子树和右子树都为空，则该结若二叉树结点的左子树和右子树都为空，则该结点为叶子结点，点为叶子结点，count+1count+1； 递归统计递归统计T T的左子树叶结点数；的左子树叶结点数； 递归统计递归统计T T的右子树叶结点数。的右子树叶结点数。（2 2）算法）算法void LeafNum(BT void LeafNum(BT * *T) T) / / 求二叉树叶结点数求二叉树叶结点数if(T) if(T) / / 若树不为空若树不为空 / / 开始时，开始时，BTBT为根

60、结点所在链结点的指针，返回值为为根结点所在链结点的指针，返回值为BTBT的叶子数的叶子数 if(T-lchild=NULL & T-rchild=NULL)if(T-lchild=NULL & T-rchild=NULL) / / 若左子树和右子树都为空若左子树和右子树都为空 count+; count+; / / 统计叶结点个数变量统计叶结点个数变量countcount（初值为（初值为0 0）加）加1 1 Leaf LeafNum(T-lchild); um(T-lchild); / / 递归统计递归统计T T的左子树叶结点数的左子树叶结点数 LeafLeafNum(T-rchild); u