第六章+树和二叉树4.20

《第六章+树和二叉树4.20》由会员分享，可在线阅读，更多相关《第六章+树和二叉树4.20（232页珍藏版）》请在金锄头文库上搜索。

1、6 树和二叉树,1,数据结构,6 树和二叉树,6 树和二叉树,2,树的类型定义 二叉树的类型定义 二叉树的存储结构 遍历二叉树和线索二叉树 树和森林 赫夫曼树,主要内容,6 树和二叉树,3,社会的组织结构 家族的族谱 计算机中的目录组织,描述层次结构，是一种一对多的逻辑关系,树型结构实例,6 树和二叉树,4,1.树的类型定义,树的定义(Tree) 树是由n(n0)个结点组成的有限集合 如果n=0，称为空树 如果n0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱 除根以外的其它结点划分为m(m=0)个互不相交的有限集合T0,T1,Tm-1，每个集合又是一棵树，并且称

2、之为根的子树,递归定义,6 树和二叉树,5,A,B,C,D,E,F,G,H,I,J,K,L,M,根,子树,树(逻辑上)的特点,每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继,6 树和二叉树,6,A,B,C,D,E,F,G,H,I,J,K,L,M,树的基本概念,结点,分支结点,叶子结点,根结点,内部结点,结点,度不为0的结点,度为0的结点,6 树和二叉树,7,树的基本概念,结点的度和树的度,结点的度即结点拥有的子树个数。 树的度是树内各结点的度的最大值。,A,B,C,D,E,F,G,H,I,J,K,L,M,3,2,1,3,2,0,0,1,0,0,0,0,0,6 树和二叉树,8,

3、树的基本概念,结点的层次和树的深度(高度),结点的层次从根开始定义。根位于第1层，根的孩子位于第2层，余则类推。 树的深度即树中结点的最大层次。,第1层,第2层,第3层,第4层,6 树和二叉树,9,树的基本概念,孩子、双亲、兄弟,结点的子树的根称为结点的孩子。 该结点称为其孩子的双亲。 同一双亲的孩子间互称兄弟。,A,B,C,D,E,F,G,H,I,J,K,L,M,孩子,双亲,6 树和二叉树,10,树的基本概念,祖先、子孙,结点的祖先是从根到该结点所经分支上的所有结点；,以某结点为根的子树中的任一结点都称该结点的子孙。,A,B,C,D,E,F,G,H,I,J,K,L,M,A,B,C,D,E,F

4、,G,H,I,J,K,L,M,6 树和二叉树,11,树的基本概念,森林：m(m=0)棵互不相交的树的集合,6 树和二叉树,12,树的有序性：若树中结点的子树的相对位置不能随意改变，则称该树为有序树，否则称该树为无序树。,树的基本概念,=,有序树,无序树,6 树和二叉树,13,有序树中最左边的子树的根称其第一个孩子，最右边的子树的根称其最后一个孩子。,老大,老二,老三,有序树的第一个孩子和最后一个孩子,树的基本概念,6 树和二叉树,14,树的常用表示法,凹入表示,嵌套集合,广义表,A(B(E,F),C,D(G(J),H,I),6 树和二叉树,15,为何要重点研究每结点最多只有两个“叉” 的树？

5、树太一般，子树的个数无限制，表示困难 二叉树的结构最简单，规律性最强 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,2.二叉树,6 树和二叉树,16,二叉树是n0个结点的有穷集合，该集合或者为空、或者由一个根结点和两个分别称为左子树和右子树的互不相交的二叉树组成，当集合为空时，称该二叉树为空二叉树。 逻辑结构：一对二(1:2) 基本特征: 树的一种 每个结点最多有2棵子树(即度=2),二叉树的基本定义,6 树和二叉树,17,二叉树与树的区别,树至少应有一个结点，而二叉树可以为空； 树的孩子结点没有限制，而二叉树中的每个结点最多有2个孩子结点； 树的子树没有顺序，但如果二叉树的根结点只

6、有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。,6 树和二叉树,18,二叉树的五种基本形态,2.只有树根,1.空树,3.只有左子树,4.只有右子树,5.左右子树都有,6 树和二叉树,19,问：具有3个结点的二叉树可能有几种不同形态？,有5种,二叉树的基本形态,6 树和二叉树,20,1.度为2的树是二叉树。,2.度为2的有序树是二叉树。,3.具有三个结点的树可以有以下五种形态：,6 树和二叉树,21,二叉树的性质,性质1： 在二叉树的第i层最多有2i-1个结点(i=1) 证明： 当i=1时，显然成立 假设当i=k时，也成立，即第k层最多2k-1个结点 当i=k+1

7、时，由于二叉树的每个结点最多有2个孩子，所以第k+1层最多有2*2k-1=2(k+1)-1个结点 故对于任意i(i=1)，二叉树的第i层最多有2i-1个结点,提问：第i层上至少有 个结点？,1,6 树和二叉树,22,二叉树的性质,性质2： 深度为k的二叉树最多有2k-1个结点(k=1) 证明： 由性质1可知：第i层最多有2i-1个结点 所以总的结点数最多为,6 树和二叉树,23,二叉树的性质,性质3： 对任何一棵二叉树T，若叶子结点数(即度为0的结点数)为n0，度为2的结点数为n2，则n0=n2+1 证明： 总结点数n=n0+n1+n2 设分支数为B，则n=B+1 又B=n1+2n2,结点无外

8、乎度为0、1、2三种情况,”五个手指四个叉” 除了树根，其余每个结点”上方”都有一个分支,度为2的结点“下方”有2个分支 度为1的结点“下方”有1个分支 度为0的结点“下方”有0个分支,解方程组： 得：n0=n2+1,6 树和二叉树,24,树的叶子数与其它结点数的关系,设度为m的树中度为0,1,2,m的结点数分别为n0,n1,n2,nm，结点总数为n，分支数为B，则下面二式成立 n=n0+n1+n2+nm (1) n=B+1=n1+2n2+mnm (2) 由(1)和(2)得叶子结点数 n0=1+n2+2n3+(m-1)nm,6 树和二叉树,25,满二叉树(Full Binary Tree) 深

9、度为k，结点数为2k-1 即结点数达到最大值,特殊形态的二叉树,完全二叉树(Complete Binary Tree) 树中每个结点的编号（从上到下，从左到右）都与一个同深度的满二叉树的结点一一对应 叶子结点只可能在层次最大的两层上出现,完全二叉树和和满二叉树相比，就是最底层最右边连续缺少一些结点,6 树和二叉树,26,特殊形态的二叉树,2h-1,结论： 深度为h且具有2h-1个结点的二叉树为满二叉树。,思考：深度为h的完全二叉树至少有多少个结点？,6 树和二叉树,27,二叉树的性质,性质4： 具有n个结点的非空完全二叉树的深度为 证明： 设深度为k，则：2k-1-1 n =2k-1 由此推出

10、：2k-1 = n 2k 两边求对数：k-1 = log2n k 所以：,6 树和二叉树,28,二叉树的性质,性质5： 若将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号： (1)若i=1，则结点i是树根，无双亲 若i1，则其双亲是结点 i/2 (2)若2in，则结点i无左孩子(即i为叶结点)，否则其左孩子为2i (3)若2i+1n，则结点i无右孩子，否则其右孩子为2i+1 由(2)(3)可以推导出(1),理解： 结点i如果有左孩子的话，其编号应该为2i 如果2in，则左孩子不存在,6 树和二叉树,29,二叉树的性质,性质6： 具有n个结点的非空二叉树共有n-1个分支。 证明

11、： 除了根结点以外，每个结点有且仅有一个双亲结点，即每个结点与其双亲结点之间仅有一个分支存在，因此，具有n个结点的非空二叉树的分支总数为n-1。,6 树和二叉树,30,1.n(n0)个结点的树的高度最低是多少？最高是多少？ 2.n(n0)个结点的二叉树的高度最低是多少？最高是多少？,推论 n个结点的树：高最多为n，最低为2。 n个结点的二叉树： 高最多为n(单支树)，最低为log2n+1(完全二叉树)。,自测题,6 树和二叉树,31,自测题,3.有关二叉树下列说法正确的是( ) A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都

12、为2,4.已知一棵完全二叉树的第6层(设根是第1层)有8个叶结点，则该完全二叉树的结点个数最多是( ) A. 39 B. 52 C. 111 D. 119,6 树和二叉树,32,完全二叉树性质的推论,n个结点的完全二叉树中： 度为1的结点数为(n+1)%2 度为0的结点数为(n+1)/2 度为2的结点数为(n+1)/2-1 编号最大的分支结点是n/2 编号最小的叶子结点是n/2+1 具有n0个叶子结点的完全二叉树中共有2n0个结点或2n0-1个结点。,6 树和二叉树,33,一棵完全二叉树有1000个结点，则它必 有 个叶子结点； 有 个度为2的结点； 有 个结点只有非空左子树； 有 个结点只有

13、非空右子树。,(1000+1)/2 =500,叶子总数-1=499,1,0,因为最后一个结点坐标是偶数，所以必为左子树。有1个结点只有非空左子树，有0个结点只有非空右子树。,自测题,6 树和二叉树,34,自测题,5.一棵124个叶结点的完全二叉树，最多有( )个结点。 A.247 B.248 C.249 D.250 E.251,6.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。 A.311 B.312 C.313 D.314 E.其他,6 树和二叉树,35,自测题,7.一个具有1025个结点的二叉树的高h为( ) 。 A.11 B.10 C.11至1025之间 D.10至10

14、24之间,8.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。,12,6 树和二叉树,36,二叉树,本节小结 二叉树的概念和类型定义 注意和树的类型定义的对比 二叉树的性质 要求自己能推导、应用、推广,6 树和二叉树,37,3.二叉树的存储结构,二叉树的顺序存储结构,用一维数组来表示 #define MAX_TREE_SIZE 100 typedef datatype SqBiTreeMAX_TREE_SIZE; SqBiTree Bt; 按照满二叉树的顺序存放,6 树和二叉树,38,完全二叉树的顺序存储结构,根据完全二叉树的性质5，对于深度为h

15、的完全二叉树，将树中所有结点的数据信息按编号顺序一次存储到数组BT12h-1中，由于编号与数组下标一一对应，该数组就是该完全二叉树的顺序存储结构。,下标：,BT3的双亲为3/2=1，即在BT1中； 其左孩子在BT2i=BT6中； 其右孩子在BT2i+1=BT7中。,6 树和二叉树,39,一般二叉树的顺序存储结构,BT5的双亲为5/2=2，即在BT2中，与实际矛盾！ 其左孩子在BT2i=BT10中，实际应在BT9中。,对于一般二叉树，需要在二叉树中“增添”一些实际上并不存在的“虚结点”(可以认为这些结点的数据信息为空)，使其在形式上成为一棵“完全二叉树”； 然后按照完全二叉树的顺序存储结构的构造方法将所有结点的信息依次存放到数组BT12h-1中。,结论(对于一般二叉树),6 树和二叉树,40,一般二叉树的顺序存储结构,BT6的双亲为6/2=3，即在BT3中！ 其左孩子在BT2i=BT12中； 其右孩子在BT2i1=BT13中，而BT130，表示无右孩子。,6 树和二叉树,41,一般二叉树的顺序存储结构,极端情形：单支树 深度为k的二叉树，最少只有k个结点 却需要2k-1个存储单元,10,增加1倍之多,6 树和二叉树,42,二叉树的链式存储结构 二叉链表 data为数据域； lchild与rchild分别为指向左、右子树的指针域。,3.二叉树的存储结构,6