1、第六章第六章 树和二叉树树和二叉树(2)主要内容主要内容 树的定义和基本术语树的定义和基本术语 二叉树二叉树 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树、森林与二叉树树、森林与二叉树 赫夫曼树及其应用赫夫曼树及其应用4、线索二叉树、线索二叉树4.1 何谓线索二叉树？何谓线索二叉树？4.2 线索二叉树的存储结构线索二叉树的存储结构4.3 线索二叉树的遍历线索二叉树的遍历4.1 何谓线索二叉树？何谓线索二叉树？为什么要线索？为什么要线索？1）二叉树的存储结构中没有反映出某结点的直接）二叉树的存储结构中没有反映出某结点的直接前驱结点和直接后继结点是什么。前驱结点和直接后继结点是什么。2）二叉树的
2、二叉链表存储结构中的那些空指针域二叉树的二叉链表存储结构中的那些空指针域 可利用。可利用。ABCDEFGHK例如:先序先序序列:A B C D E F G H K中序中序序列:B D C A H G K F E后序后序序列:D C B H K G F E A遍历二叉树的结果是，求得结点的一个线性序列。遍历二叉树的结果是，求得结点的一个线性序列。A B C D E F G H K D C B E 指向该线性序列中的指向该线性序列中的“前驱前驱”和和“后继后继”的的指针，称作指针，称作“线索线索”。包含包含“线索线索”的存储结的存储结构，称作构，称作“线索链表线索链表”。加上线索的二叉树，加上线索
3、的二叉树，称作称作“线索二叉树线索二叉树”。lchild ltag data rtag rchild0:lchild指向该结点的左孩子指向该结点的左孩子1:lchild指向该结点的前驱结点指向该结点的前驱结点0:rchild指向该结点的右孩子指向该结点的右孩子1:rchild指向该结点的后继结点指向该结点的后继结点ltag=rtag=4.2 线索二叉树的存储结构线索二叉树的存储结构结点结构结点结构线索链表线索链表如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”。5、树、森林与二叉树、树、森林与二叉树5.1 树的三种存储结构树的三种存储结构5.2 树、森林和二叉树
4、的转换树、森林和二叉树的转换5.1 树的三种存储结构树的三种存储结构一、双亲表示法一、双亲表示法二、孩子链表表示法二、孩子链表表示法三、树的二叉链表三、树的二叉链表(孩子孩子-兄弟）兄弟）存储表示法存储表示法ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent一、双亲表示法一、双亲表示法:typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述:typedef
5、struct PTNode nodes MAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;树结构树结构:ABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 4 data firstchild 1 2 34 56二、孩子链表表示法二、孩子链表表示法:-1000224typedef struct CTNode int child;struct CTNode*next;*ChildPtr;孩子结点结构孩子结点结构:child nextC语言的类型描述语言的类型描述:typedef struct Elem data;ChildPtr fi
6、rstchild;/孩子链的头指针 CTBox;双亲结点结构双亲结点结构 data firstchildtypedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;树结构树结构:ABCDEFG AB C E D F Groot AB C E D F G 三、树的二叉链表三、树的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法typedef struct CSNode Elem data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;C语言的类型描述语言的类型
7、描述:结点结构结点结构:firstchild data nextsibling5.2 树、森林和二叉树的转换树、森林和二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系 树：兄弟关系树：兄弟关系二叉树：双亲和右孩子二叉树：双亲和右孩子 树：双亲和长子树：双亲和长子二叉树：双亲和左孩子二叉树：双亲和左孩子AEBCFDGABCDEFG 1.兄弟加线兄弟加线.树转换为二叉树示例树转换为二叉树示例ABCDEFG2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线.ABCDEFG 1.兄弟加线兄弟加线.树转换为二叉树示例树转换为二叉树示例3.顺时针转动顺时
8、针转动,使之使之层次分明层次分明.2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线.1.兄弟加线兄弟加线.ABCDEFG树转换为二叉树示例树转换为二叉树示例3.顺时针转动顺时针转动,使之使之层次分明层次分明.2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线.1.兄弟加线兄弟加线.GDABECF树转换为二叉树示例树转换为二叉树示例树转换为二叉树树转换为二叉树 步骤步骤加线加线树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。去线去线对树中的每个结点，只保留它与第一个对树中的每个结点，只保留它与第一个
9、孩子结点之间的连线，删去它与其它孩子结点之间孩子结点之间的连线，删去它与其它孩子结点之间的连线。的连线。层次调整层次调整以根结点为轴心，将树顺时针转动以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。一定的角度，使之层次分明。森林转换为二叉树森林转换为二叉树 步骤步骤 将森林中的每棵树转换成二叉树；将森林中的每棵树转换成二叉树；从第二棵二叉树开始，依次把后一棵二叉树的根从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点结点作为前一棵二叉树根结点的右孩子，当所有二的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转叉树连起来后，此时所得到的二叉树就是由森林转换得
10、到的二叉树换得到的二叉树。二叉树转换为树或森林二叉树转换为树或森林 步骤步骤 加线加线若某结点若某结点x是其双亲是其双亲y的左孩子，则把结点的左孩子，则把结点x的右孩子、右孩子的右孩子、的右孩子、右孩子的右孩子、，都与结点，都与结点y用线连用线连起来；起来；去线去线删去原二叉树中所有的双亲结点与右孩子结删去原二叉树中所有的双亲结点与右孩子结点的连线；点的连线；层次调整层次调整整理由、两步所得到的树或森林，整理由、两步所得到的树或森林，使之层次分明。使之层次分明。FHGEAICDBFHGDCEBAIFEDCBAHGI加线加线去线去线层次调整层次调整IHGBCDAFE二叉树转换为树或森林二叉树转换
11、为树或森林 示例示例6、赫夫曼树及其应用、赫夫曼树及其应用 6.1 相关概念相关概念 6.2 如何构造最优二叉树（赫夫曼树）如何构造最优二叉树（赫夫曼树）6.3 赫夫曼树应用赫夫曼树应用赫夫曼编码赫夫曼编码6.1 相关概念相关概念叶子结点的权值：叶子结点的权值：对叶子结点赋予的一个有意义的对叶子结点赋予的一个有意义的数值量。数值量。二叉树的带权路径长度：二叉树的带权路径长度：设二叉树具有设二叉树具有n个带权值个带权值的叶子结点，从根结点到各个叶子结点的路径长度的叶子结点，从根结点到各个叶子结点的路径长度与相与相应叶子结点权值的乘积之和。应叶子结点权值的乘积之和。记为：记为：WPL=nkkklw
12、1第第k个叶子的权值；个叶子的权值；从根结点到第从根结点到第k个叶子的路径长度个叶子的路径长度最优二叉树（赫夫曼树）：最优二叉树（赫夫曼树）：在所有含在所有含 n 个叶子结点、个叶子结点、并带相同权值的二叉树中，必存在一棵其并带相同权值的二叉树中，必存在一棵其带权路径长度带权路径长度取最小值取最小值的二叉树，称为的二叉树，称为“最优二叉树最优二叉树”。27 9 75492WPL(T)=72+52+23+43+92 =60WPL(T)=74+94+53+42+21 =89 54赫夫曼树的特点：赫夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的权值越大的叶子结点越靠近根结点，而权值越
13、小的叶子结点越远离根结点。叶子结点越远离根结点。2.只有度为只有度为0（叶子结点）和度为（叶子结点）和度为2（分支结点）的结（分支结点）的结点，不存在度为点，不存在度为1的结点的结点.2347WPL=32 WPL=41 WPL=3023477423 6.2 如何构造最优树如何构造最优树赫夫曼算法基本思想：赫夫曼算法基本思想：初始化初始化：由给定的：由给定的n个权值个权值w1，w2，wn构造构造n棵只有一个根结点的二叉树，从而得到棵只有一个根结点的二叉树，从而得到一个二叉树集合一个二叉树集合FT1，T2，Tn；选取与合并选取与合并：在：在F中选取根结点的权值中选取根结点的权值最小最小的的两棵二叉
14、树分别作为左、右子树构造一棵新的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；、右子树根结点的权值之和；删除与加入删除与加入：在：在F中删除作为左、右子树的两中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到棵二叉树，并将新建立的二叉树加入到F中；中；重复重复、两步，当集合、两步，当集合F中只剩下一棵二叉中只剩下一棵二叉树时，这棵二叉树便是赫夫曼树。树时，这棵二叉树便是赫夫曼树。例：例：W2，3，4，5 赫夫曼树的构造过程赫夫曼树的构造过程重复第重复第2步步5432 554 9重复第重复
15、第3步步 554 932 6.3 赫夫曼树应用赫夫曼树应用赫夫曼编码赫夫曼编码 编码：给每一个对象标记一个二进制位串来表编码：给每一个对象标记一个二进制位串来表示一组对象。示一组对象。前缀编码：前缀编码：一组编码中任一编码都不是其它任一组编码中任一编码都不是其它任何一个编码的前缀何一个编码的前缀。v前缀编码保证了在解码时不会有多种可能。前缀编码保证了在解码时不会有多种可能。利用赫夫曼树可以构造一种不等长的二进制编利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的码，并且构造所得的赫夫曼编码赫夫曼编码是一种是一种最优前最优前缀编码缀编码，即使所传，即使所传电文的总长度最短电文的总长度最短
16、。例：一组字符例：一组字符A,B,C,D,E,F,G出现的频率分出现的频率分别是别是9,11,5,7,8,2,3，设计最经济的编码方案。，设计最经济的编码方案。9523510191126871545000000111111ABDCEFG编码方案：编码方案：A：00B：10C：010D：110E：111F：0110G：0111本章小结本章小结 1.1.理解二叉树线索化的实质是建立结点与其在相理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系。应序列中的前驱或后继之间的直接联系。2.2.熟悉树的各种存储结构及其特点，掌握树和森熟悉树的各种存储结构及其特点，掌握树和森林与二叉
17、树的转换方法。林与二叉树的转换方法。3.3.了解最优树的特性，掌握建立最优树和赫夫曼了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。编码的方法。作业：（11月5日交（一）（一）本或纸（一）本或纸1、对于下图所示的二叉树，请将它转换成森林。、对于下图所示的二叉树，请将它转换成森林。2、设设FT1,T2,T3是森林，请画出其对应的二是森林，请画出其对应的二叉树。其森林如下图所示。叉树。其森林如下图所示。ABCDEFGHIJABCDEFGHJIK3、以数据集、以数据集2,5,7,9,13为权值构造一棵赫夫曼为权值构造一棵赫夫曼树，并计算其带权路径长度。树，并计算其带权路径长度。（二）上机（不交）（二）上机（不交）1、赫夫曼树演示、赫夫曼树演示2、赫夫曼树实验，体会各算法运算过程、赫夫曼树实验，体会各算法运算过程
