[工学]数据结构第6章树和二叉树.ppt

1,数据结构课程的内容,2,第6章 树和二叉树（ Tree & Binary Tree ）,6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用,3,6.1 树的基本概念,1. 树的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,4,1. 树的定义,注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即树中还有树。,由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树 。,5,树的表示法有几种：,图形表示法 嵌套集合表示法 广义表表示法 目录表示法,6,树的抽象数据类型定义,（见教材P118-119）,ADT Tree 数据对象D: 数据关系R: 基本操作 P： ADT Tree,若D为空集，则称为空树；/允许n=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 /关于子树的子树不相交的说明,D是具有相同特性的数据元素的集合。,7,6.1 树的基本概念,1. 树的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,8,2. 若干术语,即上层的那个结点(直接前驱) 即下层结点的子树的根(直接后继) 同一双亲下的同层结点（孩子之间互称兄弟） 即双亲位于同一层的结点（但并非同一双亲） 即从根到该结点所经分支的所有结点 即该结点下层子树中的任一结点,根 叶子 森林 有序树 无序树,即根结点(没有前驱) 即终端结点(没有后继) 指m棵不相交的树的集合(例如删除A后的子树个数),双亲 孩子 兄弟 堂兄弟 祖先 子孙,结点各子树从左至右有序，不能互换（左为第一） 结点各子树可互换位置。,9,2. 若干术语（续）,即树的数据元素 结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）,结点 结点的度 结点的层次 终端结点 分支结点,树的度 树的深度 (或高度),从根到该结点的层数（根结点算第一层） 即度为0的结点，即叶子 即度不为0的结点（也称为内部结点）,所有结点度中的最大值（Max各结点的度） 指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数 ；树的度 ；树的深度,13,3,4,10,6.1 树的基本概念,1. 树的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,11,3. 树的逻辑结构,(特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。,12,6.1 树的基本概念,1. 树的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,13,4. 树的存储结构,讨论1：树是非线性结构，该怎样存储？ 仍然有顺序存储、链式存储等方式。,14,讨论3：树的链式存储方案应该怎样制定？,可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难（不能唯一复原就没有实用价值）。,讨论2：树的顺序存储方案应该怎样制定？,可用多重链表：一个前趋指针，n个后继指针。 细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？ 缺点：等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。,解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。,15,6.1 树的基本概念,1. 树的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,16,5. 树的运算,要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！ （遍历指每个结点都被访问且仅访问一次，不遗漏不重复）。,17,第6章 树和二叉树（ Tree & Binary Tree ）,6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用,18,6.2 二叉树,为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树。,1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构,19,1. 二叉树的定义,定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1：2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。 基本形态：,问：具有3个结点的二叉树可能有几种不同形态？普通树呢？,5种/2种,20,二叉树的抽象数据类型定义（见教材P121-122）,ADT BinaryTree 数据对象D: 数据关系R: 基本操作 P： ADT BinaryTree,若D=，则R= ； 若D，则R= H；存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 /关于根和左右子树有唯一联系的说明 /关于左子树和右子树的说明,D是具有相同特性的数据元素的集合。,21,6.2 二叉树,1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构,22,2. 二叉树的性质 (3+2),讨论1：第i层的结点数至多是多少？ （利用二进制性质可轻松求出）,性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。,性质2: 深度为k的二叉树至多有2k-1个结点（k0）。,2i-1个,提问：第i层上至少有 个结点？,1,讨论2：深度为k的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出）,2k-1,提问：深度为k时至少有 个结点？,k,23,讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？,性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2+1）,证明： 二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数) 又二叉树中全部结点数nB+1 ( 总分支数根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个) 三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1 实际意义：叶子数2度结点数1,24,对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：,性质4: 具有n个结点的完全二叉树的深度必为 log2n 1,性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i1；其双亲的编号必为i/2（i1 时为根,除外）。,证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1n2k-1 或2k-1n2k 三边同时取对数，于是有：k-1log2nk 因为k是整数， 所以k= log2n +1,x -表示不大于x的最大整数 X -表示不小于x的最小整数,25,满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点）,完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。,为何要研究这两种特殊形式？ 因为它们在顺序存储方式下可以复原！,解释：完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。 这其实是顺序二叉树的含义。,26,3. 深度为9的二叉树中至少有 个结点。 )9 )8 ) )91,2.深度为k 的二叉树的结点总数，最多为 个。 )k-1 ) log2k ) k )k,课堂练习： 1. 树中各结点的度的最大值称为树的 。 ) 高度 ) 层次 ) 深度 ) 度,课堂讨论：,满二叉树和完全二叉树有什么区别？ 答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。,27,6.2 二叉树,1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构,28,3. 二叉树的存储结构,一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,A B C D E F G H I,问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5） 例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0一般不用,29,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,A B C D E,缺点：浪费空间；插入、删除不便,30,二、链式存储结构 用二叉链表即可方便表示。,二叉树结点数据类型定义： typedef struct node *tree_pointer; typedef struct node int data; tree_pointer left_child, right_child; node;,一般从根结点开始存储。 （相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,31,例：,32,第6章 树和二叉树（ Tree & Binary Tree ）,6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用,33,6.3 遍历二叉树和线索二叉树,一、遍历二叉树（Traversing Binary Tree） 二、线索二叉树（Threaded Binary Tree）,34,遍历定义指按某条搜索路线遍访每个结点且不重复（又称周游）。 遍历用途它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 遍历方法牢记一种约定，对每个结点的查看都是“先左后右” 。,一、遍历二叉树（Traversing Binary Tree）,35,遍历规则,二叉树由根、左子树、右子树构成，定义为D、 L、R D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，则有三种实现方案： DLR LDR LRD 先 (根)序遍历 中 (根)序遍历 后(根)序遍历 注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。,36,例1：,先序遍历的结果是： 中序遍历的结果是： 后序遍历的结果是：,A B D E C D B E A C D E B C A,DLR先序遍历，即先根再左再右 LDR中序遍历，即先左再根再右 LRD后序遍历，即先左再右再根,37,例2：用二叉树表示算术表达式,先序： -+a*b-cd/ef 中序 A+b*c-d-e/f 后序 abcd-*+ef/-,38,先序遍历算法 DLR(Node *root ) if (root !=NULL) /非空二叉树 printf(“%d”,root-data); /访问D DLR(root-lchild); /递归遍历左子树 DLR(root-rchild); /递归遍历右子树 return(0); ,中序遍历算法 LDR(Node*root) if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0); ,后序遍历算法 LRD (Node *root) if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0); ,结点数据类型自定义 typedef struct Node int data; struct Node *lchild,*rchild； Node, *root;,39,对遍历的分析：,1. 从前面的三种遍历算法可以知道：如果将printf语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,从虚线的出发点到终点的路径 上，每个结点经过3次。,第1次经过时访问先序遍历 第2次经过时访问中序遍历 第3次经过时访问后序遍历,2. 二叉树遍历的时间效率和空间效率 时间效率:O(n) /每个结点只访问一次 空间效率:O(n) /栈占用的最大辅助空间,40,例：【严题集6.42】编写递归算法，计算二叉树中叶子结点的数目。,思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。,DLR(Node *root) /采用中序遍历的递归算法 if ( root!=NULL ) /非空二叉树条件，还可写成if(root) if(!root-lchild ,41,思路：利用前序遍历来建树 （结点值陆续从键盘输入，用DLR为宜） status createBTree(Bintree ,建树见教材P131程序,42,习题讨论：,1. 求二叉树深度，或从x结点开始的子树深度。 算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。 2. 按层次输出二叉树中所有结点。 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。 技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，由此便可产生按层次输出的效果。,43,3 中序遍历的非递归(迭代)算法,算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。 4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。 算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。 技巧:按层序遍历方式，先把所有结点（不管当前结点是否有左右孩子）都入队列.若为完全二叉树,则层序遍历时得到的肯定是一个连续的不包含空指针的序列.如果序列中出现了空指针，则说明不是完全二叉树。,44,特别讨论：若已知先序/后序遍历结果和中序遍历结果，能否“恢复”出二叉树？,【严题集6.31】 证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。,例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析： 由后序遍历特征，根结点必在后序序列尾部（即A）； 由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）； 继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。,45,中序遍历：B D C E A F H G 后序遍历：D E C B H G F A,（B D C E）,（ F H G）,A,B,F,（D C E）,（ H G）,C,D E,G,H,A,B,B,F,F,46,问：用二叉链表法（l_child, r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？,分析：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域（见二叉链表数据类型说明）。 除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n1个结点的链域存放指针，指向非空子女结点（即直接后继）。,思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？ 我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。,所以， 空指针数目2n(n-1)=n+1个。,n+1,47,6.3 遍历二叉树和线索二叉树,一、遍历二叉树（Traversing Binary Tree） 二、线索二叉树（Threaded Binary Tree）,48,二、线索二叉树（Threaded Binary Tree）,普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。 若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。,存放前驱指针,存放后继指针,如何预存这类信息？,例如中序遍历结果：B D C E A F H G，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！,可能是根、或最左（右）叶子,49,规 定：,1）若结点有左子树，则lchild指向其左孩子； 否则， lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右孩子； 否则， rchild指向其直接后继(即线索) 。,为了避免混淆，增加两个标志域，如下图所示：,约定:,当Tag域为0时,表示正常情况;,当Tag域为1时,表示线索情况.,50,有关线索二叉树的几个术语：,线索链表：用上一页结点结构所构成的二叉链表 线 索：指向结点前驱和后继的指针 线索二叉树：加上线索的二叉树（图形式样） 线 索 化：对二叉树以某种次序遍历使其变为线索二叉树的过程,注：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。,51,A,G,E,I,D,J,H,C,F,B,例1：带了两个标志的某先序遍历结果如表所示，请画出对应二叉树。,52,悬空？,悬空？,解：该二叉树中序遍历结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行：,例2：画出以下二叉树对应的中序线索二叉树。,为避免悬空态，应增设一个头结点,53,对应的中序线索二叉树存储结构如图所示：,注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G,54,4.【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。,解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。,55,上堂课例题讨论,问: 设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点。,先计算树的深度 k=log2n1 =10; 末层节点数=1000-(29-1)=489 第9层节点数=28=256 第9层叶子节点数=(256*2-489)/2=11 法1：先求全部叶子数。n0489(末层)11(第9层)=500个； 法2：先求2度结点数。n2=255(前8层)244(第9层)=499个；,法3：无需求树深k，便可快捷求出完全二叉树的叶子数： n0= n/2 / 取大于n/2的最小整数值 可由二叉树性质5轻松证明！ (编号为i的结点，其孩子编号必为2i和2i+1),已知最后一个结点编号为n，则其双亲（n/2或(n-1)/2)肯定是最后一个非叶子结点。其编号之后的全部结点都是叶子了！ 故，n0=n-n/2或n-(n-1)/2= n/2,56,线索二叉树的生成算法（算法6.6, 见教材P134）,目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。,注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针当前结点之指针； pre指针前驱结点之指针。,技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针p应当送到前驱结点的空右域中。,若p-lchildNULL,则p-Ltag=1;p-lchildpre; /p的前驱结点指针pre存入左空域 若pre-rchildNULL, 则pre-Rtag1;pre-rchild=p; /p存入其前驱结点pre的右空域,57,3. 线索二叉树的遍历,理论上，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空时结束。,但是，在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，R_child=右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继。,以中序线索二叉树为例： 对叶子结点（RTag=1），直接后继指针就在其rchild域内； 对其他结点（RTag=0），直接后继是其右子树最左下的结点； （因为中序遍历规则是LDR，先左再根再右）,58,程序注解 (非递归，且不用栈）： P=T-lchild; /从头结点进入到根结点； while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍历起点 if(!visit(p-data) return ERROR; /若起点值为空则出错告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后继标志，则直接提取p-rchild中线索并访问后继结点； p=p-rchild; /当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复 的全部过程。 Return OK;,线索二叉树的中序遍历算法（算法6.5, 参见教材P134）,LTag=0,RTag=1,59,算法流程：,60,提前介绍：二叉树的应用,平衡树 排序树 字典树 判定树 带权树 最优树,特点：左右子树深度差 1 特点：“左小右大” 由字符串构成的二叉树排序树 例如，12个球只称3次分出轻重 特点：路径长度带权值 带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。,61,二叉树小结,1、定义和性质,2、存储结构,3、遍历,4、线索化：线索树,霍夫曼编码,62,第6章 树和二叉树（ Tree & Binary Tree ）,6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用,63,6.4 树和森林,1. 树和森林与二叉树的转换 2. 树和森林的存储方式 3. 树和森林的遍历,64,1. 树和森林与二叉树的转换,转换步骤： step1: 将树中同一结点的兄弟相连; step2: 保留结点的最左孩子连线，删除其它孩子连线； step3: 将同一孩子的连线绕左孩子旋转45度角。,加线,抹线,旋转,讨论1：树如何转为二叉树？,65,方法：加线抹线旋转,树转二叉树举例：,兄弟相连,长兄为父,孩子靠左,根结点肯定没有右孩子！,66,讨论2：二叉树怎样还原为树？,要点：把所有右孩子变为兄弟！,67,法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。,讨论3：森林如何转为二叉树？,法二：森林直接变兄弟，再转为二叉树,（参见教材P138图6.17）,68,森林转二叉树举例：（法二）,兄弟相连 长兄为父 孩子靠左 头根为根,A,69,讨论4：二叉树如何还原为森林？,要点：把最右边的子树变为森林，其余右子树变为兄弟,70,6.4 树和森林,1. 树和森林与二叉树的转换 2. 树和森林的存储方式 3. 树和森林的遍历,71,2. 树和森林的存储方式,树有三种常用存储方式： 双亲表示法 孩子表示法 孩子兄弟表示法,1、用双亲表示法来存储,思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。,72,缺点：求结点的孩子时需要遍历整个结构。,-1,0,0,1,例1: 双亲表示法,73,思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（n个结点要设立n个链表）； 再将n个表头用数组存放起来，这样就形成一个混合结构。,例如：,2、用孩子表示法来存储,74,思路：用二叉链表来表示树，但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子； 右指针指向该结点的下一个兄弟结点。,3、用孩子兄弟表示法来存储,指向左孩子,指向右兄弟,75,问：树转二叉树的“连线抹线旋转” 如何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可。 存储的过程就是转换的过程！,例如：,76,6.4 树和森林,1. 树和森林与二叉树的转换 2. 树和森林的存储方式 3. 树和森林的遍历,77,3、树和森林的遍历,先序遍历 访问根结点； 依次先序遍历根结点的每棵子树。,树的遍历,例如：,先序序列：,后序序列：,a b c d e,b d c e a,后序遍历 依次后序遍历根结点的每棵子树； 访问根结点。,树没有中序遍历（因子树不分左右）,78,讨论：若采用“先转换，后遍历”方式，结果是否一样？,d e c b a,a b c d e,b d c e a,1. 树的先序遍历二法相同； 2. 树的后序遍历相当于对应二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。,结论：,79,先序遍历 若森林为空，返回； 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历 若森林为空，返回； 中序遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 中序遍历除去第一棵树之后剩余的树构成的森林。,森林的遍历,80,讨论：若采用“先转换，后遍历”方式，结果是否相同？,例如：,先序序列：,中序序列：,A B C D E F G H I J,B C D A F E H J I G,A B C D E F G H I J,B C D A F E H J I G,结论：森林的先序和中序遍历在两种方式下的结果相同。,81,第6章 树和二叉树（ Tree & Binary Tree ）,6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用,82,路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： 霍 夫 曼 树：,由一结点到另一结点间的分支所构成,路径上的分支数目,从树根到每一结点的路径长度之和。,结点到根的路径长度与结点上权的乘积,预备知识：若干术语,树中所有叶子结点的带权路径长度之和,带权路径长度最小的树。,ae的路径长度,树长度,2,10,6.5 Huffman树及其应用最优二叉树（霍夫曼树）,83,Huffman树简介：,树的带权路径长度如何计算？,经典之例：,WPL=36,WPL=46,WPL= 35,哈夫曼树则是：WPL 最小的树。,WPL最小,Weighted Path Length,84,(1) 由给定的 n 个权值w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林F = T0, T1, T2, , Tn-1 ，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F。,构造霍夫曼树的基本思想：,构造Huffman树的步骤（即Huffman算法）：,权值大的结点用短路径，权值小的结点用长路径。,85,例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2, 4，怎样编码才能使它们组成的报文在网络中传得最快？,法1：等长编码。例如用二进制编码来实现。 取 d=00，i=01，a=10，n=11,怎样实现Huffman编码？,法2：不等长编码，例如用哈夫曼编码来实现。 取 d=0; i=10, a=110, n=111,最快的编码是哪个？,是非等长的Huffman码！,先要构造Huffman树！,86,操作要点1：对权值的合并、删除与替换 在权值集合7,5,2,4中，总是合并当前值最小的两个权,构造Huffman树的步骤：,注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。,87,操作要点2：按左0右1对Huffman树的所有分支编号！,Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1725+3*(2+4)=35,特点：每一码都不是另一码的前缀，绝不会错译! 称为前缀码,将 Huffman树 与 Huffman编码 挂钩,88,例2（严题集6.26）：假设用于通信的电文仅由8个字母 a, b, c, d, e, f, g, h