《《6树和二叉树(基础知识)》-精选课件（公开PPT）》由会员分享，可在线阅读，更多相关《《6树和二叉树(基础知识)》-精选课件（公开PPT）（63页珍藏版）》请在金锄头文库上搜索。
1、课程内容（调整）： 第一部分：基础知识 第二部分：算法实现,回顾（栈和队列）： 栈：栈底、栈顶、空栈、满栈 队列：队头、队尾、空队、满队,栈的习题：,一个栈的入栈序列是a,b,c,d,e, 则栈的不可能的输出序列是（）。 A. edcba B. decba C . dceab D. abcde 若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）。 A. 243156 B. 324165 C. 432156 D. 235164 对于栈操作数据的原则是（）。 A. 先进先出 B.后进先出 C.后进后出 D.不分顺序 若已知一个栈的入栈序列是1,2,3,4,n
2、，其输出序列为p1,p2,p3,pn，若p1=n，则pi为（） A. i B. n= =i C. n-i+1 D. 不确定,队列的习题：,一个队列的入队序列是1, 2, 3, 4，则队列的输出序列是（）。 A. 4321 B. 1234 C . 1432 D. 3241,第六章 树和二叉树,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树,6.4 树和森林,6.6 赫夫曼树及其应用,6.1 树的定义和基本术语,6.1.2 基本术语,6.1.1 树的类型定义,家谱,树形结构,树形结构的另外三种表示方法：,一、（祖父（伯父（堂兄（侄子），堂姐），父亲（你），叔父（堂弟）,根,子树,6
3、.1.2 基本术语,结点(node)：数据元素+若干指向子树的分支。 结点的度(degree)：分支个数（子树的个数）。 树的度：树中所有结点的度的最大值。 叶子结点：度为0的结点，也称终端结点。 分支结点：度大于0的结点， 也称非终端结点。,(从根到结点的)路径：由从根到该结点所经分支和结点构成。,孩子：结点子树的根。 双亲：相应的，该结点称为孩子的双亲。 兄弟：同一双亲的孩子。 堂兄弟：双亲在同一层的结点。 祖先：从根到该结点所经分支上的所有结点。 子孙：以该结点为根的子树中的任一结点。,结点的层次:假设根结点的层次为1，第L层的结点的子树根结点的层次为L+1。,树的深度：树中叶子结点所在
4、的最大层次。,森林：,是m（m0）棵互 不相交的树的集合。,B,C,D,E,F,G,H,I,J,M,K,L,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,树的习题：,6.1 已知一棵树边的集合为, , , , , , , , , , , , ,请画出这棵树，并回答下列问题。,6.2 二叉树,6.2.2 二叉树的性质,6.2.1 二叉树的类型定义,6.2.3 二叉树的存储结构,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,6.2.1 二叉树的类型定义,二叉树的
5、五种基本形态：,N,N,N,N,L,R,R,L,二叉树和树是两种不同的树型结构，二叉树不等同于度为2的有序树。 如果根结点只有一棵子树，那么对树而言，它就是一个独生子，无次序可分，但对二叉树而言，必须明确区分它是根的左子树还是根的右子树，两者将构成不同的二叉树。,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结 点。 (i1),6.2.2 二叉树的性质,用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。,假设对所有的 j，1 j i
6、，命题成立；,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。,两种特殊形式的二叉树 满二叉树 定义：指的是深度为k且含有2k-1个结点的二叉树。 特点
7、：每一层上的结点数都是最大结点数。,完全二叉树 定义：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。 特点： 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为 L，则其左分支下子孙的最大层次必为L 或L+1。,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k ， 则根据第二条性质得 2k-1-1 n 2k-1 或 2k-1 n n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,6.3 遍历二叉树和线索二叉树,6.3.2 线索二叉树,6.3.1 遍历二叉树,遍历
8、二叉树 即顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历； 2先左（子树）后右（子树） 的遍历； 3先右（子树）后左（子树） 的遍历。,先（根）序遍历（DLR）,二叉树的典型结构：,中（根）序遍历（LDR）,后（根）序遍历（LRD）,先序遍历二叉树操作定义： 若二叉树为空，则空操作； 否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,D L R,先序遍历序列：A B D C,先序遍历:,中序遍历二叉树操作定义： 若二叉树为空，则空操作； 否则 （1）中序遍历左子树； （2
9、）访问根结点； （3）中序遍历右子树。,L D R,中序遍历序列：B D A C,中序遍历:,后序遍历二叉树操作定义： 若二叉树为空，则空操作； 否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点 。,L R D,后序遍历序列： D B C A,后序遍历:,先序遍历：,中序遍历：,后序遍历：,层次遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,二叉树的习题：,含有10个结点的二叉树中，度为0的节点数为4，则度为2的节点数为（）。 A. 3
10、B.4 C . 5 D. 6 除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）倍。 A. 1/2 B. 1 C. 2 D. 3 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（）。 A. 24 B. 25 C. 98 D.99 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该二叉树。 假设一个二叉树的中序序列为DCBGEAHFIJK 和后序序列为DCEGBFHKJIA。请画出该二叉树。 假设一棵二叉树的层序序列为ABCDEFGHIJ 和中序序列为DBGEHJACIF。请画出该二叉树,先序序列: E (B (
11、A) (D C) (F (H G (I KJ) 中序序列: (A) B (C D) E (F (G H (I JK),E,B,A,D,C,F,H,G,H,I,K,J,6.4 树和森林,6.4.2 森林和二叉树的转换,6.4.1 树的存储结构,6.4.3 树和森林的遍历,6.4.2 树、森林与二叉树转换,树 = 二叉树方法： （1）结点的第一个孩子，转换为该结点的左孩子； （2）结点的右边第一个兄弟，转换为该结点的右孩子。,A,B,C,A,B,C,A,B,C,A,B,C,A,B,C,F,G,I,J,K,H,E,D,A,B,C,E,D,I,F,J,G,K,H,森林 = 二叉树方法： （1）每棵树转
12、换为二叉树； （2）连接,6.4.3 树和森林的遍历,树的遍历： （1）先根遍历：ABCDE （2）后根遍历：BDCEA,森林的遍历： （1）先序遍历:ABCDEFGHIJ （2）中序遍历:BCDAFEHJIG,6.6 赫夫曼树及其应用,6.6.1 最优二叉树,6.6.2 赫夫曼编码,6.6.1 最优二叉树（赫夫曼树）,结点的路径长度：从根结点到该结点的路径上分支的数目。 树的路径长度：从树根到每一个结点的路径长度之和。,结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。,树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作,赫夫曼树（最优二叉树）：带权路径长度之和最小的
13、二叉树。,例如：,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,（1）根据给定的 n 个权值 w1, w2, , wn， 构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树；,如何构造最优二叉树？,（2）在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；,（3）从F中删去这两棵树，同时加入刚生成的新树；,（4）重复 (2) 和
14、 (3) 两步，直至 F 中只 含一棵树为止。,9,例如: 已知权值 W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,目前，数据通信用的二进制编码。,6.6.2 赫夫曼编码 最优二叉树的应用,例如：假设需传送的电文ABACCDA。,编码表1： A: 00 B: 01 C: 10 D: 11,编码表2： A: 0 B: 00 C: 1 D: 10,指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,前缀编码：,赫夫曼树的应用：可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编
15、码是一种最优前缀编码（即：使所传电文的总长度最短）。,赫夫曼编码: 思想：根据字符出现频率编码，使电文总长最短。 编码： （1）根据字符出现频率构造Huffman树；（2）左分支标“0”，右分支标“1”； （3）每个字符的编码：从根到每个叶子的路径上的0、1序列。,例：已知某系统在通信联络中只可能出现8种字符，其概率分别是 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11， 试设计赫夫曼编码。,设权w(5,29,7,8,14,23,3,11),0,0,0,0,0,0,0,1,1,1,1,1,1,1,00,010,0110,0111,10,110,1110,1111,例：已知某系统在通信联络中只可能出现8种字符，其概率分别是 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11， 试设计赫夫曼编码。,设权w(5,29,7,8,14,23,3,11),0,0,0,0,0,0,0,1,1,1,1,1,1,1,译码： 从Huffm
