第六章 树与二叉树.ppt

学习提示,基本内容 二叉树的定义、性质和存储结构;二叉树的遍历和线索化以及遍历算法的各种描述形式;树和森林的定义、存储结构与二叉树的转换、遍历;树的多种应用。 教学目的 1、熟练掌握二叉树的结构特性，了解相应的证明方法。 2、熟悉二叉树的各种存储结构的特点及适用范围。 3、遍历二叉树、线索二叉树。 4、熟练掌握二叉树的线索化过程及在中序线索化树上找给定结点的前驱和后继的方法。 5、熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。 6、了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。 教学重点： 树与二叉树的概念和基本术语、存储结构、二叉树性质、二叉树遍历、树与二叉树的转换、赫夫曼编码设计 教学难点：线索二叉树、树与二叉树遍历非递归算法的实现、树的基本操作的实现、赫夫曼树及其应用,学习纲要,6.1 树的定义和基本概念 6.2 二叉树（本课程的重点内容之一） 6.2.1 二叉树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换,6.4.3树和森林的遍历 6.5 赫夫曼树及其应用 6.5.1 最优二叉树（赫夫曼树） 6.5.2 赫夫曼编码,学习纲要,树型结构是一类重要的非线性结构。 树型结构 是结点之间有分支，并且具有层次关系的结构。（直观来看） 树型结构的逻辑特征 树中任一结点都可以有零个或多个后继结点，但至多只能有一个前趋结点，只有根结点无前趋，叶子结点无后继。 最为常用的树型结构 树 二叉树,6.1 树的定义和基本术语,6.1 树的基本概念及相关术语 一、树的定义 定义：树(Tree)是n(n=0)个结点的有限集T，n=0时称为空树，否则对任意一棵非空树，它满足如下两个条件：,6.1 树的定义和基本术语,（1）有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为根的子树(Subtree)。,树的定义是采用递归方法,6.1 树的定义和基本术语,(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构,一、树的定义,6.1 树的定义和基本术语,树的应用举例文件结构,6.1 树的定义和基本术语,每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。是一种分支的、层次的结构,二、树的特点,6.1 树的定义和基本术语,三、树的基本术语,结点的度：结点所拥有的子树的个数。 树的度：树中各结点度的最大值。,6.1 树的定义和基本术语,三、树的基本术语,叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。,6.1 树的定义和基本术语,三、树的基本术语,孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。,6.1 树的定义和基本术语,三、树的基本术语,路径：如果树的结点序列n1, n2, , nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1, n2, , nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。,6.1 树的定义和基本术语,三、树的基本术语,祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。,6.1 树的定义和基本术语,三、树的基本术语,结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。 树的深度：树中所有结点的最大层数，也称高度。,6.1 树的定义和基本术语,三、树的基本术语,层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。,6.1 树的定义和基本术语,三、树的基本术语,有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。,数据结构中讨论的一般都是有序树,6.1 树的定义和基本术语,三、树的基本术语,森林：m (m0)棵互不相交的树的集合。,6.1 树的定义和基本术语,练习：对如下的树，回答以下问题：,根结点、叶结点 G的双亲、 G的孩子 E的子孙、 E的兄弟 C的兄弟 结点B、I的层次 对结点G为根的子树的深度 树的深度 树的度数,四、树的其它表现形式 a、广义表法 b、嵌套集合法 c、凹入表示法,(A(B)(E(K,L),F),C(G),D(H(M),I,J),(a),(b),(c),6.1 树的定义和基本术语,五、树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,6.2 二叉树,6.2.1 二叉树的定义 一、定义 二叉树是n(n=0)个结点的有限集合，此集合或者为空集（n=0），或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。,6.2 二叉树,二、二叉树的特点 1.每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点); 2.该两棵子树可以为空; 3.该两棵子树有次序之分，分别称之为左子树和右子树,其次序不能任意颠倒。,6.2 二叉树,二叉树的五种不同形态,三、二叉树的基本形态,6.2 二叉树,四、二叉树与树和有序树的区别,6.2 二叉树,二叉树与树的区别： A树中结点的最大度数没有限制，二叉树结点最大度数为2。 B树的每个结点的子树无左、右之分，二叉树的结点子树有明确的左、右之分。 二叉树与有序树的区别： C.在有序树中，某个结点只有一个孩子时就无左、右之分,特别要注意：二叉树不是树的特殊情况，它们是两种不同的树型结构。,四、二叉树与树和有序树的区别,练习：画出含有3个结点的树与二叉树的所有不同形态,树,二叉树,6.2 二叉树,6.2 二叉树,特殊的二叉树,斜树 1 .所有结点都只有左子树的二叉树称为左斜树 2 .所有结点都只有右子树的二叉树称为右斜树 3.左斜树和右斜树统称为斜树。,1. 在斜树中，每一层只有一个结点； 2.斜树的结点个数与其深度相同。,斜树的特点：,满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。,特点：,6.2 二叉树,特殊的二叉树,叶子只能出现在最下一层； 只有度为0和度为2的结点。,6.2 二叉树,特殊的二叉树,不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中叶子结点个数最多,6.2 二叉树,完全二叉树-深度为k的，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树（也称为近似满二叉树）,完全二叉树,特点：（1）叶子结点只可能在层次最大的两层上出现 （2）对任一结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙最大层次必为L或L+1,特殊的二叉树,(a)完全二叉树,(b)非完全二叉树,( c)非完全二叉树,满二叉树是完全二叉树的特例。,6.2 二叉树,特殊的二叉树,由此可得出如下结论： 对一棵完全二叉树，有： 1.至多只有最下面两层上结点的度数可以小于2 2.最下面一层结点都集中在该层的最左边 3.满二叉树是完全二叉树，反之不然，在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。,6.2 二叉树,特殊的二叉树,6.2.2 二叉树的性质,性质1： 在二叉树的第i层上至多有2i-1个结点(i=1)。,第三层上(i=3)，有23-1=4个结点。 第四层上(i=4)，有24-1=8个结点。,用数学归纳法证明,6.2.2 二叉树的性质,性质2：深度为k的二叉树至多有2k1个结点（k=1)）.,此树的深度h=4，共有24-1=15个结点。,20 + 21 + 22 + + 2k-1 = 2k-1,6.2.2 二叉树的性质,性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。,n0=8 n2=7,6.2.2 二叉树的性质,性质4：具有n个结点的完全二叉树的深度为 符号 表示不大于x的最大整数。,完全二叉树的两个重要特性,6.2.2 二叉树的性质,性质5： 如果对一棵有n个结点的完全二叉树的结点按层次编号,则对编号为i的结点（11，则其双亲是结点i / 2。 （2）如果2in，则结点i为叶子结点，无左孩子； 否则，其左孩子是结点2i。 （3）如果2i1n， 则结点i无右孩子 否则， 其右孩子是结点2i1。,完全二叉树的两个重要特性,性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。,6.2.2 二叉树的性质,完全二叉树中结点i和i+1,(a)i和i+1结点在同一层,(b)i和i+1结点不在同一层,如图所示为完全二叉树上结点及其左右子树在结点之间的关系。,6.2.2 二叉树的性质,在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此是，结点i无孩子。结点i的右孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。 对于i1，可分为两种情况： （1）设第j（1n，则无左孩子：,6.2.2 二叉树的性质,其右孩子必定为第j1层的第二个结点，编号为2i1。若2i+1n，则无右孩子。 （2）假设第j（11时，如果i为左孩子，即2×（i/2)=i,则i/2是i的双亲；如果i为右孩子，i2p+1,i的双亲应为p，p（i1）/2=i/2. 证毕。,6.2.3 二叉树的存储结构,顺序存储结构,二叉树的顺序存储结构就是用一组连续的存储单元存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树和满二叉树中结点的序号可以惟一地反映出结点之间的逻辑关系 。,6.2.3 二叉树的存储结构,完全二叉树的顺序存储,以编号 为下标,完全二叉树,6.2.3 二叉树的存储结构,二叉树的顺序存储,以编号 为下标,按照完全 二叉树编号,一般二叉树,6.2.3 二叉树的存储结构,一棵斜树的顺序存储会怎样呢？,深度为k的右斜树，k个结点需分配2k1个存储单元。,一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。,二叉树的顺序存储结构一般仅存储完全二叉树,6.2.3 二叉树的存储结构,二叉链表,基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。,二叉树的链表表示,每个结点由数据域、左指针域和右指针域组成。,二叉链表,其中，data：数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。,结点结构,6.2.3 二叉树的存储结构,二叉链表,具有n个结点的二叉链表中，有多少个空指针？,n+1个,6.2.3 二叉树的存储结构,在二叉链表中，如何求某结点的双亲？,二叉链表,6.2.3 二叉树的存储结构,三叉链表,三叉链表,在二叉链表的基础上增加了一个指向双亲的指针域。,6.2.3 二叉树的存储结构,三叉链表,6.2.3 二叉树的存储结构,在二叉链表这种存储结构上，二叉树的多数基本运算如求根、求左、右孩子等很容易实现。但求双亲运算的实现比较麻烦，而且其时间性能较低 空间利用不高，在含有n个结点的二叉链表中有n+1个空链域， 三叉链表 优点： 求双亲运算很容易实现，且时间性能很好,二叉链表与三叉链表的比较,二叉树的二叉链表存储结构类型描述,typedef struct BiTNode /树结点定义 ElemType data; /结点数据域 struct BiTNode *lChild, *rChild; /左右孩子指针 BiTNode ,*BiTree;,6.2.4 二叉树的常用操作,二叉树存储结构课堂练习,练习 分别画出下图所示二叉树的二叉链表、三叉链表和顺序存储结构示意图,6.3 遍历二叉树和线索二叉树,6.3.1遍历二叉树,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果？,6.3.1遍历二叉树,6.3 遍历二叉树和线索二叉树,考虑二叉树的组成：,二叉树的遍历方式： DLR、LDR、LRD、 DRL、RDL、RLD,如果限定先左后右，则二叉树遍历方式有三种： 先序：DLR 中序：LDR 后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,6.3.1遍历二叉树,先序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 访问根结点 (D)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f,.（前缀表示波兰式）,先序遍历 (Preorder Traversal),6.3.1遍历二叉树,void PreOrder (BiTNode *T) if (T = = NULL) return error; /递归调用的结束条件 visit (T-data); PreOrder (T-lChild); PreOrder (T-rChild); ,二叉树递归的先序遍历算法,6.3.1遍历二叉树,中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f,.（中缀表示）,中序遍历 (Inorder Traversal),6.3.1遍历二叉树,void InOrder (BiTNode *T) if (T != NULL) InOrder (T-lChild); visit (T-data); InOrder (T-rChild); ,二叉树递归的中序遍历算法,6.3.1遍历二叉树,后序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。 遍历结果 a b c d - * + e f / -,.(后缀表示逆波兰式),后序遍历 (Postorder Traversal),6.3.1遍历二叉树,void PostOrder (BiTNode *T) if (T != NULL) PostOrder (T-lChild); PostOrder (T-rChild); visit (T-data); ,二叉树递归的后序遍历算法,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,3,3,3,3,先序序列：A B D E H I C F G,中序序列：D B H E I A F C G,后序序列：D H I E B F G C A,3,3,3,3,3,6.3.1遍历二叉树,6.3.1遍历二叉树,写出下图二叉树的先序、中序、后序的遍历序列,先序序列：A B C D E F G H I J,中序序列：B C D A F E H J I G,后序序列：D C B F J I H G E A,课堂练习二,6.3.1遍历二叉树,层序遍历 二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,遍历结果：- + / a * e f b c d,6.3.1遍历二叉树,若已知一棵二叉树的先序（或中序，或后序，或层序）序列，能否惟一确定这棵二叉树呢？,遍历的性质 性质1、由一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树 性质2、由一棵二叉树的后序序列和中序序列可惟一确定这棵二叉树,由遍历序列恢复二叉树,6.3.1遍历二叉树,例如，已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树。,构造二叉树过程如下：,BDCE,FHG,A,FHG,A,B,DCE,由遍历序列恢复二叉树,由遍历序列恢复二叉树,中序序列BDCEAFHG 后序序列DECBHGFA,6.3.1遍历二叉树,6.3.1遍历二叉树,已知二叉树的先序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 试构造该二叉树,练习三,6.3.1遍历二叉树,先序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,HBDF,EKCG,A,EKCG,A,B,H,DF,6.3.1遍历二叉树,KCG,EKCG,A,B,H,DF,EKCG,A,B,H,F,D,E,A,B,H,F,D,E,A,B,H,F,D,C,K,G,先序序列 ABHFDECKG ,6.3.1遍历二叉树,int Height (BiTNode *T) if (T = NULL) return 0; else int m = Height (T-lChild); int n = Height (T-rChild); return (m n) ? m+1 : n+1; ,例一：求二叉树高度的递归算法,二叉树遍历应用,Status CreateBiTree(BiTree ,例二：构建一棵二叉树（使用先序遍历）,6.3.1遍历二叉树,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,3,3,3,3,先序序列：A B D E H I C F G,中序序列：D B H E I A F C G,后序序列：D H I E B F G C A,3,3,3,3,3,6.3.2二叉树遍历的非递归实现,6.3.2二叉树遍历的非递归实现,先序遍历的定义： 1）访问根结点 2）先序遍历左子树 3）先序遍历右子树,先序遍历的非递归算法,(a),(b),6.3.2二叉树遍历的非递归实现,利用栈的先序遍历的非递归算法,先序遍历的定义： 1）访问根结点 2）先序遍历左子树 3）先序遍历右子树,c,d c,c,访问 a 进栈 c 左进 b,访问 b 进栈 d 左进 空,退栈 d 访问 d 左进 空,退栈 c 访问 c 左进 e,访问 e 左进 空 退栈 ,结束,先序遍历的非递归算法,6.3.2二叉树遍历的非递归实现,void PreOrder(BiTree T) stack S; InitStack( /左子树空, 进右子树 ,先序遍历的非递归算法,6.3.2二叉树遍历的非递归实现,a,b,c,d,e,b a,a,d a,a,左空,退栈 访问,左空,退栈 访问,退栈 访问,左空,e c,退栈访问,c,c,右空,退栈访问 栈空结束,利用栈的中序遍历的非递归算法,中序遍历的定义： 1）中序遍历左子树 2）访问根结点 3）中序遍历右子树,中序遍历的非递归算法,6.3.2二叉树遍历的非递归实现,void InOrder(BiTree T) stack S; InitStack(S); /递归工作栈 BiTNode *p = T; /初始化 while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lChild; /根指针进栈，遍历左子树 else Pop(S, p); /退栈 visit(p-data); /访问根结点 p = p-rChild; /遍历右子树 ,中序遍历的非递归算法,6.3.2二叉树遍历的非递归实现,思考： 后序遍历的非递归算法,6.3.2 线索二叉树,如何保存二叉树的某种遍历序列？,将二叉链表中的空指针域指向其前驱结点和后继结点,当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能找到结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到。,6.3.2 线索二叉树,线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索； 线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；加上线索的二叉链表称为线索链表 线索二叉树：加上线索的二叉树称为线索二叉树。,6.3.2 线索二叉树,结点结构,线索链表,例如下图（a）是一棵中序线索二叉树，它的线索链表如图 (b)所示。,（a）,注：不同的遍历次序其得到的线索二叉树也不同(可分别称为先序线索二叉树、中序线索二叉树和后序线索二叉树),6.3.2 线索二叉树,线索链表,pre,p,(b),6.3.2 线索二叉树,如何在线索二叉树中找结点的前驱和后继结点？ 1、找结点的前驱结点的过程 （以中序线索为例）： 1）树中所有叶结点的左链是线索，因此叶结点的左链域直接指向其前驱结点。 2）对于非终端结点，若该结点无左孩子，则其左链域为线索，直接指向其前驱结点。若有左孩子，则该结点的前驱为中序遍历其左子树时最后访问的那个结点，即左子树中最右下的结点为其前驱结点。 2、找结点的后继结点的过程（以中序线索为例）： 1）树中所有叶结点的右链是线索，因此叶结点的右链域直接指示该结点的后继结点。 2）非终端结点若无右孩子，则其右链是线索，指向后继，若有右孩子，则其后继是中序遍历其右子树时访问的第一个结点，即右子树中最左下结点 。,6.3.2 线索二叉树,线索链表,pre,p,T,6.3.2 线索二叉树,如何进行二叉树的线索化呢？ 线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱和后继的信息只有在遍历时才能得到，因此线索化过程即为在遍历的过程中修改空指针的过程。,6.3.2 线索二叉树,6.4 树与森林,实现树的存储结构，关键是什么?,树中结点之间的逻辑关系是什么?,思考问题的出发点：如何表示结点的双亲和孩子,如何表示树中结点之间的逻辑关系。,6.4.1 树的存储结构,父子关系,6.4.1 树的存储结构,双亲表示法,基本思想：用一组连续的存储空间（一维数组）存储树的各个结点（一般按层序存储），同时在每个结点中附设一个指示器指示其双亲结点在数组中的位置。,data：存储树中结点的数据信息 parent：存储该结点的双亲在数组中的下标,结点结构：,6.4.1 树的存储结构,#define MAXNODE typedef struct PTNode /结点结构 elemtype data; int parent; /双亲位置域 PTNode; PTNode tMAXNODE;,树的双亲表示法实质上是一个静态链表。,双亲表示法,6.4.1 树的存储结构,下标 data parent,双亲表示法,不足： 求某结点的孩子结点，即实现Child（t，x，i）操作时，则需要查询整个数组。 不能反映各兄弟结点之间的关系，所以实现RightSibling（t，x）操作也比较困难。,优点： 实现Parent（t，x）操作和Root（x）操作很方便,6.4.1 树的存储结构,链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。,如何确定链表中的结点结构？,孩子链表表示法,6.4.1 树的存储结构,缺点：浪费空间,A,B,C,D,E,F,G,H,I,孩子链表表示法,6.4.1 树的存储结构,链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。,如何确定链表中的结点结构？,方案二： 指针域的个数等于该结点的度-异构,其中：data：数据域，存放该结点的数据信息； degree：度域，存放该结点的度； child1childd：指针域，指向该结点的孩子,孩子链表表示法,6.4.1 树的存储结构,缺点：结点结构不一致，操作不方便,A 2,B 3,C 2,E 1,I 0,G 0,H 0,F 0,D 0,孩子链表表示法,6.4.1 树的存储结构,孩子链表表示法,基本思想：把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有 n 个孩子链表。这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表，为了便于进行查找采用顺序存储。最后，将存放 n 个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组。,如何确定链表中的结点结构？,将结点的所有孩子放在一起，构成线性表。,6.4.1 树的存储结构,孩子链表表示法,0 1 2 3 4 5 6 7 8,下标 data firstchild,A B C D E F G H I,6.4.1 树的存储结构,双亲孩子表示法,6.4.1 树的存储结构,孩子兄弟表示法,某结点的第一个孩子是惟一的 某结点的右兄弟是惟一的,6.4.1 树的存储结构,类型描述如下： Typedef struct CSNode elemtype data; /结点信息 struct CSNode *firstchild, /指向第一个孩子结点的指针 *nextsibling; /指向下一个兄弟结点的指针 CSNode,*CSTree; /用指向树的根结点的指针来表示一棵树,结点结构,data：数据域，存储该结点的数据信息； firstchild：指针域，指向该结点第一个孩子； nextsibling：指针域，指向该结点的右兄弟结点。,孩子兄弟表示法,6.4.1 树的存储结构,孩子兄弟表示法,优缺点： 可以直接实现树的大部分操作，如找结点的孩子、兄弟等操作。但对树结点作Parent操作时需遍历树。如果要反复执行Parent操作， 则可为每个结点增设一个parent域，这样就能方便地实现parent(T,x)运算,6.4.1 树的存储结构,6.4.1 树的存储结构,画出下列树的孩子兄弟表示法的结构图,(a),(c),树,二叉树,(b),练习,以二叉链表为媒介可导出树与二叉树之间的对应关系。将树转换为二叉树，这样，对树的操作就可以借助二叉树存储，利用二叉树上的操作来实现。,6.4.2 树、森林与二叉树的转换,6.4.2 树、森林与二叉树的转换,1、树转换为二叉树 方法一：借助二叉链表，让该结点的左分枝指向该结点的第一个孩子，右分枝指向该结点的下一个兄弟。,方法二： · 在树中所有的兄弟结点之间加一连线； · 对每个结点，除保留与其长子（最左孩子）的连线外，去除该结点与其它孩子之间的联线； · 以根结点为轴心，将整个树顺时针转45度。,6.4.2 树、森林与二叉树的转换,第一步：在树中所有的兄弟结点之间加一连线,第二步：对每个结点，除保留与其长子（最左孩子）的连线外，去除该结点与其它孩子之间的联线；,第三步：以根结点为轴心，将整个树顺时针转45度。,6.4.2 树、森林与二叉树的转换,将下列的树转换为二叉树,课堂练习（一）,6.4.2 树、森林与二叉树的转换,将下列的树转换为二叉树,转换后的二叉树,课堂练习（一）,6.4.2 树、森林与二叉树的转换,2. 森林转换为二叉树 森林转换为二叉树的方法： 将森林中的每一棵树分别转换成二叉树； 将各二叉树的根结点视为兄弟用线连起来； 以第一棵树的根结点作为二叉树的根结点，按顺时针方向适当旋转。,6.4.2 树、森林与二叉树的转换,将如图所示的森林转换为二叉树,二、二叉树转换成树、森林,方法一 1.二叉树的根作为森林中第一棵树的根 2.二叉树的左子树转换成森林中第一棵树的子树森林 3.二叉树的右子树转换成森林中其它的树,6.4.2 树、森林与二叉树的转换,6.4.2 树、森林与二叉树的转换,二叉树转换为森林,方法二 1）将结点的左孩子的右孩子、右孩子的右孩子与该结点连接起来 2）去掉所有结点与其右孩子的连线,6.4.2 树、森林与二叉树的转换,将如图所示的森林转换为二叉树,6.4.2 树、森林与二叉树的转换,课堂练习,将如图所示的森林转换为二叉树,6.4.2 树、森林与二叉树的转换,最后转换成的二叉树,6.4.3 树与森林的遍历,1、先序（根）遍历树-先访问树根结点n，然后从左到右，依次先序遍历根的每棵子树T1,T2,Tk 。 2、后序（根）遍历树-先从左到右，依次对树的每棵子树T1,T2,Tk进行后序遍历，最后访问树根结点n。,设T以n为树根，树根的子树从左到右依次为T1,T2,Tk，那么有：,6.4.3 树与森林的遍历,先根：A B E F C D G H I 后根：E F B C G H I D A,例如,右图树,A,E,I,二叉树,右图二叉树 先序: A B E F C D G H I 中序：E F B C G H I D A,先根遍历树 先序遍历该树对应的二叉树 后根遍历树 中序遍历该树对应的二叉树,6.4.3 树与森林的遍历,按照树与森林相互递归定义，可推出森林的两种遍历方法： 一、先序遍历森林 若森林非空，则可按下述规则遍历： 1.访问森林中第一棵树的根结点; 2.先序遍历第一棵树中根结点的子树森林; 3.先序遍历除去第一棵树之后剩余的树构成的森林。 二、中序遍历森林 若森林非空，则可按下述规则遍历： 1.中序遍历森林中第一棵树的根结点的子树森林; 2.访问第一棵树的根结点; 3.中序遍历除去第一棵树之后剩余的树构成的森林,6.4.3 树与森林的遍历,先序遍历序列： A B C D E F G H J I 中序遍历序列： B C D A F E J H I G,先序遍历森林 先序遍历该森林对应的二叉树 中序遍历森林 中序遍历该森林对应的二叉树,相关概念,1.结点间的路径长度-从树中一个结点到另一个结点之间的分支数目,6.5 赫夫曼树及其应用,2.叶子结点的权值-对叶子结点赋予的一个有意义的数值量。,3.结点带权的路径长度-从该结点到树根之间的路径长度与结点上权的乘积。,6.5 赫夫曼树及其应用,4.二叉树的带权路径长度（weighted path length of tree）-二叉树中所有叶子结点的带权路径长度之和。,WPL=,WPL=2*2+3*2+4*2+7*2=32,6.5 赫夫曼树及其应用,5.赫夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。,例：给定4个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的多个二叉树。,WPL=32 WPL=41 WPL=30,6.5 赫夫曼树及其应用,赫夫曼树的特点： 1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.,2,3,4,7,WPL=32 WPL=41 WPL=30,2,3,4,7,7,4,2,3,6.5 赫夫曼树及其应用,赫夫曼算法基本思想： 初始化：由给定的n个权值w1，w2，wn构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合FT1，T2，Tn； 选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和； 删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中； 重复、两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是赫夫曼树。,怎样构造一棵赫夫曼树呢？,第1步：初始化,例：给定权值 W2，3，4，5 ，构造赫夫曼树,第2步：选取与合并,第3步：删除与加入,赫夫曼树的构造过程,6.5 赫夫曼树及其应用,W2，3，4，5 赫夫曼树的构造过程,重复第2步,5,4,3,2,5,重复第3步,6.5 赫夫曼树及其应用,W2，3，4，5 赫夫曼树的构造过程,重复第2步,重复第3步,6.5 赫夫曼树及其应用,6.5 赫夫曼树及其应用,给定权值7，18，3，32，5，26，12，8，构造相应的赫夫曼树,要求左子树根结点的权值小于右子树根结点的权值。,课堂练习（三）,赫夫曼树的应用-判定树 在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法。 例1 将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的，可用图（a)二叉树结构来实现。,输入10000个数据，则需进行31500次比较。,6.5 赫夫曼树及其应用,(b),学生成绩分布不是均匀的情况：,以比例数为权构造一棵赫夫曼树，如（b)判断树所示。,再将每一比较框的两次比较改为一次，可得到（c)判定树。,输入10000个数据，仅需进行22000次比较。,6.5 赫夫曼树及其应用,赫夫曼树的应用-赫夫曼编码 利用赫夫曼树构造通讯中电文编码 例如：要传输一个电文：CAS；CAT；SAT；AT; 要传输的字符集是 D=C，A，S，T， ； 每个字符出现的频率是W= 2，4， 2，3， 3 ,6.5 赫夫曼树及其应用,等长编码：C(000)A(001)S(010)T(011);(100) 000001010100000001011100010001011100001011 42位 不等长编码：C(0)A(00)S(1)T(01);(10) 000110000011010001100001 24位 无法翻译 前缀编码：任一个字符的编码都不是另一个字符编码的前缀 C(0)A(10)S(110)T(1110);(1111) 0101101111010111011111101011101111101110 40位前缀码,6.5 赫夫曼树及其应用,电文总长达到最短的前缀编码的方法-构造一棵赫夫曼树 （1）用频率作为叶子结点的权值生成一棵赫夫曼树，并将对应权值wi的叶子结点注明对应的字符； （2）约定左分支表示字符“0”，右分支表示字符1 则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为赫夫曼编码。 编码的过程：从叶子结点出发走一条从叶子到根的路径 译码的过程：从根出发走一条从根到叶子的路径,怎样才能使总的串长达到最小呢？,例子：要传输的电文是CAS；CAT；SAT；AT 要传输的字符集是 D=C，A，S，T， ； 每个字符出现的频率是W= 2，4， 2，3， 3 ,各字符编码是 T ； A C S 00 01 10 110 111,上述电文编码：（32位） 11010111011101000011111000011000,6.5 赫夫曼树及其应用,赫夫曼树的存储结构及其算法的实现,1. 设置一个数组huffTree2n-1保存赫夫曼树中各点的信息，数组元素的结点结构 ： 其存储结构为： Typedef