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