1、数据结构(CC+语言版)第五章 树和二叉树21.熟练掌握二叉树的结构特性二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构存储结构的特点及适用范围。3.遍历二叉树遍历二叉树是二叉树各种操作的基础，掌握各种遍历策略 的递归算法递归算法，灵活运用遍历算法灵活运用遍历算法实现二叉树的其它操作。4.熟悉树的树的各种存储结构存储结构及其特点，掌握树和森林与二叉树树和森林与二叉树的转换的转换方法。5.学会编写实现树的各种操作实现树的各种操作的算法。6.了解最优树的特性最优树的特性，掌握建立最优树和哈夫曼编码建立最优树和哈夫曼编码的方法。3 1、若一棵树中度为、若一棵树中度为1的结点有的结点
2、有n1个，度为个，度为2的结点有的结点有n2个，个，度为，度为m的结点有的结点有nm个，它有多少个叶结点？个，它有多少个叶结点？2、找出所有的二叉树，其结点在下列两种次序下恰好都以、找出所有的二叉树，其结点在下列两种次序下恰好都以同样的顺序出现：同样的顺序出现：（1）先根和中根）先根和中根（2）先根和后根（）先根和后根（3）中根和后根）中根和后根3、设计一个算法，根据一个二叉树结点的先根序列和中根、设计一个算法，根据一个二叉树结点的先根序列和中根序列构造出该二叉树。假设二叉树是链接表示的，并且任意序列构造出该二叉树。假设二叉树是链接表示的，并且任意两个结点的两个结点的info字段值都不同。字段
3、值都不同。4、设计一个算法，将一个链接表示的二叉树中每个结点的、设计一个算法，将一个链接表示的二叉树中每个结点的左、右子女位置交换。左、右子女位置交换。5、设计一个算法，按层次顺序输出二叉树中的所有结点，、设计一个算法，按层次顺序输出二叉树中的所有结点，要求同一层上的结点从左到右输出。要求同一层上的结点从左到右输出。6、设、设F是一个森林，是一个森林，B是与是与F对应的二叉树。试问，对应的二叉树。试问，F中非叶中非叶结点的个数和结点的个数和B中右子树为空的结点的个数之间有什么数量中右子树为空的结点的个数之间有什么数量关系？关系？4 树的存储方法主要有哪些？举例说明树的存储方法主要有哪些？举例说
4、明具体存储结构。具体存储结构。5树的定义树的定义树：树：n（n0）个个结点结点的有限的有限集合集合。当。当n0时，称为时，称为空树；任意一棵非空树满足以下条件：空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为有且仅有一个特定的称为根根的结点；的结点；当当n1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m（m0）个个互不相交互不相交的有限集合的有限集合T1,T2,Tm，其中其中每个集合又是一棵树，并称为这个根结点的每个集合又是一棵树，并称为这个根结点的子树子树。5.1 树的逻辑结构树的逻辑结构树的定义是采用递归方法树的定义是采用递归方法65.1 树的逻辑结构树的逻辑结
5、构CGBDE FK LHMIJA7CGBDEFKLHMIJA5.1 树的逻辑结构树的逻辑结构85.1 树的逻辑结构树的逻辑结构CGBDEFKLHMIJA91 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJC5.1 树的逻辑结构树的逻辑结构10CBDEFKLHJA712345689105.1 树的逻辑结构树的逻辑结构11数据结构中讨论的一般都是有序树数据结构中讨论的一般都是有序树 5.1 树的逻辑结构树的逻辑结构ACBGFEDACBGFED12CBDEFKLHJ5.1 树的逻辑结构树的逻辑结构A135.1 树的逻辑结构树的逻辑结构ACBGFEDDAECFBG14线性结构线性结构树
6、结构树结构第第一一个数据元素个数据元素根结点（只有根结点（只有一一个）个）无前驱无前驱无双亲无双亲最后最后一一个数据元素个数据元素叶子结点叶子结点(可以有可以有多多个个)无后继无后继无孩子无孩子其它数据元素其它数据元素其它结点其它结点一个前驱一个前驱,一个后继一个后继一个双亲一个双亲,多个孩子多个孩子一对一一对一 一对多一对多5.1 树的逻辑结构树的逻辑结构155.1 树的逻辑结构树的逻辑结构数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树；为空集，则称为空树；否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的
7、数据元素root,(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互不相个互不相交的有限集交的有限集T1,T2,Tm,其中每一棵子集本身又是其中每一棵子集本身又是一棵符合本定义的树，称为根一棵符合本定义的树，称为根root的子树。的子树。数据关系数据关系 R：16A(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根 (b)(a)上面是树的广义表表示形式 例如：例如：1718树的遍历操作树的遍历操作 树的遍历：树的遍历：从从根根结点出发，按照某种结点出发，按照某种次次序访问序访问树中树中所有结点，使得每个结点被访问一次且仅被访问一所有结点，使得每个结点被访问一次
8、且仅被访问一次。次。如何理解如何理解访问访问?抽象抽象操作，操作，可以是对结点进行的各种处理，这里可以是对结点进行的各种处理，这里简简化为输出结点的数据。化为输出结点的数据。如何理解如何理解次序次序?树通常有前序（根）遍历、后序（根）遍历和层树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。序（次）遍历三种方式。5.1 树的逻辑结构树的逻辑结构树结构（非线性结构）树结构（非线性结构）线性结构。线性结构。遍历的实质遍历的实质?19前序遍历前序遍历 树的前序遍历操作定义为：树的前序遍历操作定义为：若树为空，则空操作返回；若树为空，则空操作返回；否则否则 访问根结点；访问根结点；按照从
9、左到右的顺序前序按照从左到右的顺序前序遍历根结点的每一棵子树。遍历根结点的每一棵子树。5.1 树的逻辑结构树的逻辑结构前序遍历序列：前序遍历序列：A B D E H I F C GACBGFEDHI20后序遍历后序遍历 树的后序遍历操作定义为：树的后序遍历操作定义为：若树为空，则空操作返回；若树为空，则空操作返回；否则否则 按照从左到右的顺序后序按照从左到右的顺序后序遍历根结点的每一棵子树；遍历根结点的每一棵子树；访问根结点。访问根结点。5.1 树的逻辑结构树的逻辑结构后序遍历序列：后序遍历序列：D H I E F B G C AACBGFEDHI21层序遍历层序遍历 树的层序遍历操作定义为：
10、树的层序遍历操作定义为：从树的第一层（即根结点）从树的第一层（即根结点）开开始，自上而下逐层遍历，始，自上而下逐层遍历，在同一层中，按从左到右的在同一层中，按从左到右的顺序对结点逐个访问。顺序对结点逐个访问。5.1 树的逻辑结构树的逻辑结构层序遍历序列：层序遍历序列：A B C D E F G H IACBGFEDHI225.2 树的存储结构树的存储结构实现树的存储结构，关键是什么实现树的存储结构，关键是什么?什么是存储结构什么是存储结构?树中结点之间的逻辑关系是什么树中结点之间的逻辑关系是什么?思考问题的出发点：如何表示结点的双亲和孩子思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结
11、点之间的逻辑关系。如何表示树中结点之间的逻辑关系。数据元素以及数据元素之间的数据元素以及数据元素之间的逻辑关系逻辑关系在存储器在存储器中的表示。中的表示。23下标下标 data parent012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 5.2 树的存储结构树的存储结构 ACBHFEDGI24012345678下标下标 data firstchild A B C D E F G H I 5.2 树的存储结构树的存储结构12 345 7 68 ACBHFEDGI255.2 树的存储结构树的存储结构012345678 A -1 B 0 C 0 D 1
12、E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 ACBHFEDGI265.2 树的存储结构树的存储结构 A B C D E F G H IACBHFEDGI27二叉树的定义二叉树的定义 二叉树是二叉树是n（n0）个结点的有限集合，该集合或个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点者为空集（称为空二叉树），或者由一个根结点和两棵和两棵互不相交互不相交的、分别称为根结点的的、分别称为根结点的左子树左子树和和右子树右子树的二叉树组成。的二叉树组成。5.3 二叉树的逻辑结构二叉树的逻辑结构问题转化：将树转换为二叉树，
13、从而利用二叉树解问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。决树的有关问题。研究二叉树的意义？研究二叉树的意义？285.3 二叉树的逻辑结构二叉树的逻辑结构ABCDEFGABAB29二叉树的基本形态二叉树的基本形态空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树5.3 二叉树的逻辑结构二叉树的逻辑结构305.3 二叉树的逻辑结构二叉树的逻辑结构31特殊的二叉树特殊的二叉树斜树斜树1.所所有结点都只有左子有结点都只有左子树的二叉树称为
14、树的二叉树称为左斜树左斜树；2.所有结点都只所有结点都只有右子有右子树的二叉树称为树的二叉树称为右斜树右斜树；3.3.左斜树和右斜树统称为左斜树和右斜树统称为斜树斜树。1.在斜树中，每一层只有一个结点；在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。斜树的结点个数与其深度相同。5.3 二叉树的逻辑结构二叉树的逻辑结构斜树的特点：斜树的特点：ABCABC32满二叉树满二叉树在一棵二叉树中，如果所在一棵二叉树中，如果所有分支结点都存在左子树有分支结点都存在左子树和右子树，并且所有叶子和右子树，并且所有叶子都在都在同一层上。同一层上。满二叉树的特点满二叉树的特点：叶子只能出现在最下一层
15、；叶子只能出现在最下一层；只有度为只有度为0和度为和度为2的结点。的结点。5.3 二叉树的逻辑结构二叉树的逻辑结构特殊的二叉树特殊的二叉树A15234678910BCDEFGHIJKLM NO1112 13 14 15335.3 二叉树的逻辑结构二叉树的逻辑结构A1523467BCDEFGLM89345.3 二叉树的逻辑结构二叉树的逻辑结构A15234678910BCDEFGHIJKLM NO1112 13 14 15A15234678910BCDEFGHIJ35在满二叉树中，从最后在满二叉树中，从最后一个结点开始，一个结点开始，连续连续去去掉掉任意任意个结点，即是一个结点，即是一棵完全二叉树
16、。棵完全二叉树。5.3 二叉树的逻辑结构二叉树的逻辑结构A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ特殊的二叉树特殊的二叉树365.3 二叉树的逻辑结构二叉树的逻辑结构A15234678910BCDEFGHIJ37二叉树的基本性质二叉树的基本性质5.3 二叉树的逻辑结构二叉树的逻辑结构A15234678910BCDEFGHIJ385.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的基本性质二叉树的基本性质 A15234678910BCDEFGHIJ39n0+n1+n2=n1+2*n2+1 n0=n2+15.3 二叉树的逻辑结构二
17、叉树的逻辑结构二叉树的基本性质二叉树的基本性质 405.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的基本性质二叉树的基本性质 A15234678910BCDEFGHIJKLM NO1112 13 14 15415.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的基本性质二叉树的基本性质 42 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。5.3 二叉树的逻辑结构二叉树的逻辑结构 2k-1-12k-12k-1第第k-1层层第第k层层最少结点数最少结点数最多结点数最多结点数完全二叉树的基本性质完全二叉树的基本性质 43 5.3 二叉树的逻辑结构二叉树的逻辑结构log
18、2n+1log2nlog2nlog2n+1k所在区间所在区间完全二叉树的基本性质完全二叉树的基本性质 对不等式取对数，有：对不等式取对数，有：k-1log2nk即：即：log2nklog2n+1由于由于k是整数，故必有是整数，故必有k log2n+1。445.3 二叉树的逻辑结构二叉树的逻辑结构完全二叉树的基本性质完全二叉树的基本性质 4518910456723对一棵具有对一棵具有n个结点的完全个结点的完全二叉树中从二叉树中从1开始按层序编开始按层序编号，则号，则l 结点结点i的双亲结点为的双亲结点为 i/2；l 结点结点i的左孩子为的左孩子为2i；l 结点结点i的右孩子为的右孩子为2i1。5
19、.3 二叉树的逻辑结构二叉树的逻辑结构性质性质6表明，在完全二叉树中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。完全二叉树的基本性质完全二叉树的基本性质 46二叉树的抽象数据类型定义二叉树的抽象数据类型定义查书查书5.3 二叉树的逻辑结构二叉树的逻辑结构 二叉树的主要基本操作二叉树的主要基本操作：查查 找找 类类 插插 入入 类类 删删 除除 类类47二叉树的遍历操作二叉树的遍历操作 二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结点，使得每个结点被访问一访问二叉树中的所有结点，
20、使得每个结点被访问一次且仅被次且仅被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化5.3 二叉树的逻辑结构二叉树的逻辑结构抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 48如果限定先左后右，则二叉树遍历方式有三种：如果限定先左后右，则二叉树遍历方式有三种：前序前序：DLR中序中序：LDR后序后序：LRD层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。5.3
21、 二叉树的逻辑结构二叉树的逻辑结构考虑二叉树的组成：考虑二叉树的组成：根结点根结点D左子树左子树L右子树右子树R二二叉叉树树495.3 二叉树的逻辑结构二叉树的逻辑结构前序遍历序列：前序遍历序列：A B D G C E FABCDEFG二叉树的遍历操作二叉树的遍历操作 505.3 二叉树的逻辑结构二叉树的逻辑结构中序遍历序列：中序遍历序列：D G B A E C FABCDEFG二叉树的遍历操作二叉树的遍历操作 515.3 二叉树的逻辑结构二叉树的逻辑结构后序遍历序列：后序遍历序列：G D B E F C AABCDEFG二叉树的遍历操作二叉树的遍历操作 525.3 二叉树的逻辑结构二叉树的逻
22、辑结构层序遍历序列：层序遍历序列：A B C D E F GABCDEFG二叉树的遍历操作二叉树的遍历操作 535.3 二叉树的逻辑结构二叉树的逻辑结构ABCABC二叉树的遍历操作二叉树的遍历操作 545.3 二叉树的逻辑结构二叉树的逻辑结构ABCABC二叉树的遍历操作二叉树的遍历操作 555.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的遍历操作二叉树的遍历操作 561.根据前序序列的第一个元素建立根结点；根据前序序列的第一个元素建立根结点；2.在中序序列中找到该元素，确定根结点的左右子树在中序序列中找到该元素，确定根结点的左右子树的中序序列；的中序序列；3.在前序序列中确定左右子树的前序序列
23、；在前序序列中确定左右子树的前序序列；4.由左子树的前序序列和中序序列建立左子树；由左子树的前序序列和中序序列建立左子树；5.由右子树的前序序列和中序序列建立右子树。由右子树的前序序列和中序序列建立右子树。5.3 二叉树的逻辑结构二叉树的逻辑结构已知一棵二叉树的前序序列和中序序列，构造该已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：二叉树的过程如下：二叉树的遍历操作二叉树的遍历操作 57顺序存储结构顺序存储结构二叉树的顺序存储结构就是用一维数组存储二叉树二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的中的结点，并且结点的存储位存储位置置（下标）应能体现（下标）应能
24、体现结点之间的结点之间的逻辑关系逻辑关系父子关系。父子关系。如何利用数组下标来反映结点之间的逻辑关系如何利用数组下标来反映结点之间的逻辑关系?完全二叉树完全二叉树和和满二叉树满二叉树中结点的序号可以唯一中结点的序号可以唯一地反映出结点之间的逻辑关系地反映出结点之间的逻辑关系。5.4 二叉树的存储结构及实现二叉树的存储结构及实现58 A B C D E F G H I J数组下标数组下标 1 2 3 4 5 6 7 8 9 10完全二叉树的顺序存储完全二叉树的顺序存储5.4 二叉树的存储结构及实现二叉树的存储结构及实现A15234678910BCDEFGHIJ以编号以编号为下标为下标59二叉树的
25、顺序存储二叉树的顺序存储ABC DE F G数组下标数组下标 1 2 3 4 5 6 7 8 9 10 11 12 135.4 二叉树的存储结构及实现二叉树的存储结构及实现ABCDFGE以编号以编号为下标为下标ABCDFGE123561013按照完全按照完全二叉树编号二叉树编号60一棵斜树的顺序存储会怎样呢？一棵斜树的顺序存储会怎样呢？深度为深度为k的右斜树，的右斜树，k个结点需分配个结点需分配2k1个存储单元。个存储单元。一棵二叉树改造后成完一棵二叉树改造后成完全二叉树形态，需增加全二叉树形态，需增加很多空结点，造成存储很多空结点，造成存储空间的浪费。空间的浪费。5.4 二叉树的存储结构及实
26、现二叉树的存储结构及实现二叉树的顺序存储结构一般仅存储二叉树的顺序存储结构一般仅存储完全完全二叉树二叉树ABC137D1561二叉链表二叉链表基本思想：基本思想：令二叉树的每个结点对应一个链表结点，令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信链表结点除了存放与二叉树结点有关的数据信息外，息外，还要设置指示左右孩子的指针。还要设置指示左右孩子的指针。结点结构：结点结构：lchild data rchild其中，其中，data：数据域，存放该结点的数据信息；数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；左指针域，存放指向左孩子的指针；r
27、child：右指针域，存放指向右孩子的指针。右指针域，存放指向右孩子的指针。5.4 二叉树的存储结构及实现二叉树的存储结构及实现62template struct BiNode T data;BiNode*lchild,*rchild;5.4 二叉树的存储结构及实现二叉树的存储结构及实现lchild data rchild左孩子结点左孩子结点右孩子结点右孩子结点二叉链表二叉链表63GFEDBAABCDEFGC二叉链表二叉链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现具有具有n个结点的二叉链表中，有多少个空指针？个结点的二叉链表中，有多少个空指针？64GFEDBAABCDEFGC二叉链
28、表二叉链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现具有具有n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针。个空指针。65前序遍历前序遍历递归算法递归算法template void BiTree:PreOrder(BiNode*root)if(root=NULL)return;else cout-data;PreOrder(root-lchild);PreOrder(root-rchild);5.4 二叉树的存储结构及实现二叉树的存储结构及实现66AGBCDFE5.4 二叉树的存储结构及实现二叉树的存储结构及实现前序遍历前序遍历算法的执行轨迹算法的执行轨迹67二叉树前序
29、遍历的非递归算法的二叉树前序遍历的非递归算法的关键关键：在前序遍历过：在前序遍历过某结点的整个左子树后，如何找到该结点的某结点的整个左子树后，如何找到该结点的右子树右子树的的根指针。根指针。解决办法：解决办法：在访问完该结点后，将该结点的指针保存在访问完该结点后，将该结点的指针保存在在栈栈中，以便以后能通过它找到该结点的右子树。中，以便以后能通过它找到该结点的右子树。在前序遍历中，设要遍历二叉树的根指针为在前序遍历中，设要遍历二叉树的根指针为root，则则有两种可能：有两种可能：若若root!=NULL，则表明？如何处理？则表明？如何处理？若若root=NULL，则表明？如何处理？则表明？如何
30、处理？5.4 二叉树的存储结构及实现二叉树的存储结构及实现前序遍历前序遍历非递归算法非递归算法68访问结点序列访问结点序列:A栈栈S内容内容:B D A B前序遍历的前序遍历的非递归非递归实现实现 5.4 二叉树的存储结构及实现二叉树的存储结构及实现ADBC69访问结点序列访问结点序列:A栈栈S内容内容:B D A前序遍历的前序遍历的非递归非递归实现实现 5.4 二叉树的存储结构及实现二叉树的存储结构及实现ADBC D70访问结点序列访问结点序列:A栈栈S内容内容:B D C前序遍历的前序遍历的非递归非递归实现实现 5.4 二叉树的存储结构及实现二叉树的存储结构及实现ADBCC711.栈栈s初
31、始化；初始化；2.循环直到循环直到root为空且栈为空且栈s为空为空 2.1 当当root不空时循环不空时循环2.1.1 输出输出root-data;2.1.2 将指针将指针root的值保存到栈中；的值保存到栈中；2.1.3 继续遍历继续遍历root的左子树的左子树2.2 如果栈如果栈s不空，则不空，则2.2.1 将栈顶元素弹出至将栈顶元素弹出至root；2.2.2 准备遍历准备遍历root的右子树；的右子树；前序遍历前序遍历非递归算法（伪代码）非递归算法（伪代码）5.4 二叉树的存储结构及实现二叉树的存储结构及实现72前序遍历前序遍历非递归算法非递归算法5.4 二叉树的存储结构及实现二叉树的
32、存储结构及实现template void BiTree:PreOrder(BiNode*root)top=-1;/采用顺序栈，并假定不会发生上溢采用顺序栈，并假定不会发生上溢 while(root!=NULL|top!=-1)while(root!=NULL)coutdata;s+top=root;root=root-lchild;if(top!=-1)root=stop-;root=root-rchild;73中序遍历中序遍历递归算法递归算法 template void BiTree:InOrder(BiNode*root)if(root=NULL)return;else InOrder(r
33、oot-lchild);cout-data;InOrder(root-rchild);5.4 二叉树的存储结构及实现二叉树的存储结构及实现74后序遍历后序遍历递归算法递归算法template void BiTree:PostOrder(BiNode*root)if(root=NULL)return;else PostOrder(root-lchild);PostOrder(root-rchild);cout-data;5.4 二叉树的存储结构及实现二叉树的存储结构及实现75层序遍历层序遍历5.4 二叉树的存储结构及实现二叉树的存储结构及实现ABCDEFG遍历序列：遍历序列：AAB CBDCE
34、F GD E F G76层序遍历层序遍历 队列队列Q初始化；初始化；2.如果二叉树非空，将根指针入队；如果二叉树非空，将根指针入队；3.循环直到队列循环直到队列Q为空为空 3.1 q=队列队列Q的队头元素出队；的队头元素出队；3.2 访问结点访问结点q的数据域；的数据域；3.3 若结点若结点q存在左孩子，则将左孩子指针入队；存在左孩子，则将左孩子指针入队；3.4 若结点若结点q存在右孩子，则将右孩子指针入队；存在右孩子，则将右孩子指针入队；5.4 二叉树的存储结构及实现二叉树的存储结构及实现77二叉树的建立二叉树的建立为了建立一棵二叉树，将二叉树中每个结点的空指为了建立一棵二叉树，将二叉树中每
35、个结点的空指针引出一个虚结点，其值为一特定值如针引出一个虚结点，其值为一特定值如“#”，以，以标识其为空，把这样处理后的二叉树称为原二叉树标识其为空，把这样处理后的二叉树称为原二叉树的扩展的扩展二叉树。二叉树。为什么如此处理为什么如此处理?5.4 二叉树的存储结构及实现二叉树的存储结构及实现如何由一种遍历序列生成该二叉树？如何由一种遍历序列生成该二叉树？遍历遍历是是二叉树二叉树各种操作的基础，可以在遍历的过程各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。中进行各种操作，例如建立一棵二叉树。78扩展二叉树的前序遍历序列扩展二叉树的前序遍历序列:A B#D#C#5.4 二叉树
36、的存储结构及实现二叉树的存储结构及实现DBAC#DBAC#二叉树的建立二叉树的建立79前序前序遍历遍历序列：序列：A B D C二叉树的二叉树的遍历遍历操作操作 5.4 二叉树的存储结构及实现二叉树的存储结构及实现DBAC80二叉树的二叉树的遍历遍历操作操作 5.4 二叉树的存储结构及实现二叉树的存储结构及实现DBAC81template BiTree:BiTree(BiNode*root)creat(root)；void BiTree:Creat(BiNode*root)cinch;if(ch=#)root=NULL;else root=new BiNode;root-data=ch;cre
37、at(root-lchild);creat(root-rchild);建立二叉递归算法建立二叉递归算法5.4 二叉树的存储结构及实现二叉树的存储结构及实现82线索链表线索链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现为什么要线索？为什么要线索？1）二叉树的存储结构中没有反映出某结点的直接）二叉树的存储结构中没有反映出某结点的直接前驱结点和直接后继结点是什么。前驱结点和直接后继结点是什么。2）二叉树的二叉链表存储结构中的那些空指针域二叉树的二叉链表存储结构中的那些空指针域 可利用。可利用。83线索链表线索链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现84 ltag lchil
38、d data child rtag0:lchild指向该结点的左孩子指向该结点的左孩子1:lchild指向该结点的前驱结点指向该结点的前驱结点0:rchild指向该结点的右孩子指向该结点的右孩子1:rchild指向该结点的后继结点指向该结点的后继结点ltag=rtag=5.4 二叉树的存储结构及实现二叉树的存储结构及实现结点结构结点结构线索链表线索链表85enum flag Child,Thread;template struct ThrNode T data;ThrNode *lchild,*rchild;flag ltag,rtag;5.4 二叉树的存储结构及实现二叉树的存储结构及实现线索
39、链表线索链表 ltag lchild data child rtag结点结构结点结构86二叉树的遍历方式有二叉树的遍历方式有4种，故有种，故有4种意义下的前驱和后种意义下的前驱和后继，相应的有继，相应的有4种线索二叉树：种线索二叉树：前序线索二叉树前序线索二叉树 中序线索二叉树中序线索二叉树 后序线索二叉树后序线索二叉树 层序线索二叉树层序线索二叉树5.4 二叉树的存储结构及实现二叉树的存储结构及实现线索二叉树线索二叉树875.4 二叉树的存储结构及实现二叉树的存储结构及实现885.4 二叉树的存储结构及实现二叉树的存储结构及实现895.4 二叉树的存储结构及实现二叉树的存储结构及实现90分析
40、：分析：建立线索链表，实质上就是将二叉链表中的空建立线索链表，实质上就是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历该二叉树时才能得到。息只有在遍历该二叉树时才能得到。5.4 二叉树的存储结构及实现二叉树的存储结构及实现建立二叉链表建立二叉链表遍历二叉树，将遍历二叉树，将空指针改为线索空指针改为线索中序线索链表的建立中序线索链表的建立构造函数构造函数91在遍历过程中，访问当前结点在遍历过程中，访问当前结点root的操作为：的操作为：如果如果root的左、右指针域为空，则将相应标志置的左、右指针域为空，则将相应标志置1；
41、若若root的左指针域为空，则令其指向它的前驱，这的左指针域为空，则令其指向它的前驱，这需要设指针需要设指针pre始终指向刚刚访问过的结点，显然始终指向刚刚访问过的结点，显然pre的初值为的初值为NULL；若若pre的右指针域为空，则令其指向的右指针域为空，则令其指向它的后继，即当前访问的结点它的后继，即当前访问的结点root;令令pre指向刚刚访问过的结点指向刚刚访问过的结点root；5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序线索链表的建立中序线索链表的建立921.建立二叉链表，将每个结点的左右标志置为建立二叉链表，将每个结点的左右标志置为0；2.遍历二叉链表，建立线索；遍历二
42、叉链表，建立线索；2.1 如果二叉链表如果二叉链表root为空，则空操作返回；为空，则空操作返回；2.2 对对root的左子树建立线索；的左子树建立线索；2.3 对根结点对根结点root建立线索；建立线索；2.3.1 若若root没有左孩子，则为没有左孩子，则为root加上前驱线索加上前驱线索;2.3.2 若若root没有右孩子没有右孩子，则将则将root右标志置为右标志置为1；2.3.3 若结点若结点pre右标志为右标志为1，则为，则为pre加上后继线索；加上后继线索；2.3.4 令令pre指向刚刚访问的结点指向刚刚访问的结点root；2.4 对对root的右子树建立线索。的右子树建立线索。
43、5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序线索链表的建立中序线索链表的建立构造函数构造函数935.5 树、森林与二叉树的转换树、森林与二叉树的转换是哪些树结构的是哪些树结构的存储结构存储结构?树和二叉树之间具有对应关系树和二叉树之间具有对应关系AEBCFDGA BCED F GABCDEFG945.5 树、森林与二叉树的转换树、森林与二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系 树：兄弟关系树：兄弟关系二叉树：双亲和右孩子二叉树：双亲和右孩子 树：双亲和长子树：双亲和长子二叉树：双亲和左孩子二叉树：双亲和左孩子AEBCFDGABCDEFG955.5 树、森林与二叉
44、树的转换树、森林与二叉树的转换 1.兄弟加线兄弟加线.树和二叉树之间的对应关系树和二叉树之间的对应关系ABCDEFG965.5 树、森林与二叉树的转换树、森林与二叉树的转换2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线.ABCDEFG树和二叉树之间的对应关系树和二叉树之间的对应关系 1.兄弟加线兄弟加线.973.顺时针转动顺时针转动,使之使之层次分明层次分明.5.5 树、森林与二叉树的转换树、森林与二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线.1
45、.兄弟加线兄弟加线.ABCDEFG983.顺时针转动顺时针转动,使之使之层次分明层次分明.5.5 树、森林与二叉树的转换树、森林与二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线.1.兄弟加线兄弟加线.GDABECF99树转换为二叉树树转换为二叉树 加线加线树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。去线去线对树中的每个结点，只保留它与第一个对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间孩子结点之间的连线，删去它与其它孩子结点之间的连线。的连
46、线。层次调整层次调整以根结点为轴心，将树顺时针转动以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。一定的角度，使之层次分明。5.5 树、森林与二叉树的转换树、森林与二叉树的转换100森林转换为二叉树森林转换为二叉树 将森林中的每棵树转换成二叉树；将森林中的每棵树转换成二叉树；从第二棵二叉树开始，依次把后一棵二叉树的根从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点结点作为前一棵二叉树根结点的右孩子，当所有二的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树换得到的二叉树。5.5 树、森林与二叉树的
47、转换树、森林与二叉树的转换101二叉树转换为树或森林二叉树转换为树或森林 加线加线若某结点若某结点x是其双亲是其双亲y的左孩子，则把结点的左孩子，则把结点x的右孩子、右孩子的右孩子、的右孩子、右孩子的右孩子、，都与结点，都与结点y用线连用线连起来；起来；去线去线删去原二叉树中所有的双亲结点与右孩子结删去原二叉树中所有的双亲结点与右孩子结点的连线；点的连线；层次调整层次调整整理由、两步所得到的树或森林，整理由、两步所得到的树或森林，使之层次分明。使之层次分明。5.5 树、森林与二叉树的转换树、森林与二叉树的转换102FHGEAICDBFHGDCEBAIFEDCBAHGI加线加线去线去线层次调整层
48、次调整IHGBCDAFE5.5 树、森林与二叉树的转换树、森林与二叉树的转换103森林的遍历森林的遍历森林有两种遍历方法：森林有两种遍历方法：前序（根）遍历：前序遍历森林即为前序遍历森前序（根）遍历：前序遍历森林即为前序遍历森林中的每一棵树。林中的每一棵树。后序（根）遍历：后序遍历森林即为后序遍历森后序（根）遍历：后序遍历森林即为后序遍历森林中的每一棵树。林中的每一棵树。5.5 树、森林与二叉树的转换树、森林与二叉树的转换104相关概念相关概念叶子结点的权值：叶子结点的权值：对叶子结点赋予的一个有意义的对叶子结点赋予的一个有意义的数值量。数值量。二叉树的带权路径长度：二叉树的带权路径长度：设二
49、叉树具有设二叉树具有n个带权值的个带权值的叶子结点，从根结点到各个叶子结点的路径长度与叶子结点，从根结点到各个叶子结点的路径长度与相相应叶子结点权值的乘积之和。应叶子结点权值的乘积之和。记为：记为：WPL=5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码=nkkklw1第第k个叶子的权值；个叶子的权值；从根结点到第从根结点到第k个叶子的路径长度个叶子的路径长度105哈夫曼树：哈夫曼树：给定一组具有确定权值的给定一组具有确定权值的叶子叶子结点，带权结点，带权路径路径长度最小的二叉树长度最小的二叉树。例：给定例：给定4个叶子结点，其权值分别为个叶子结点，其权值分别为2，3，4，7，可以构造出形状不
50、同的可以构造出形状不同的多个二叉树。多个二叉树。5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码WPL=32 WPL=41 WPL=30234723477423106哈夫曼树的特点：哈夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。叶子结点越远离根结点。2.只有度为只有度为0（叶子结点）和度为（叶子结点）和度为2（分支结点）的结（分支结点）的结点，不存在度为点，不存在度为1的结点的结点.5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码2347WPL=32 WPL=41 WPL=3023477423107哈夫曼算法基
