《数据结构 第2版 教学课件 ppt 作者 宗大华 陈吉人 《数据结构》课件-5》由会员分享，可在线阅读，更多相关《数据结构 第2版 教学课件 ppt 作者 宗大华 陈吉人 《数据结构》课件-5（30页珍藏版）》请在金锄头文库上搜索。
1、第5章 二叉树,1.,2.,3.,本章讲述内容：,4.,二叉树的定义及性质 ；,二叉树的存储实现（顺序存储和链式存储） ；,遍历二叉树（即对二叉树存储结点访问的各种形式） ；,哈夫曼树及编码 。,二叉树上一个结点的两棵子树有左、右之分，次序是不能颠倒的。所以，二叉树是有序的 。,5.1 二叉树概述,5.1.1 二叉树的基本概念,二叉树的定义,1.,二叉树具有的特征,2.,.,所谓“二叉树”，是一个由结点组成的有限集合。这个集合或者为空，或者由一个称为根的结点以及两棵不相交的二叉树组成，这两棵二叉树分别称为这个根结点的左子树和右子树。,A,A,B,C,A,B,C,根结点,根结点,根结点,左子树,
2、右子树,左子树,A,B,C,根结点,左子树,右子树,D,E,F,(空二叉树),.,.,二叉树可以是空的，空二叉树没有任何结点，仍用符号“”表示 。,.,二叉树上的每个结点最多可以有两棵子树，这两棵子树是不相交的。,.,当二叉树非空时，是通过结点之间的一条边来表示从一个结点到它的两个子结点（如果有的话）间的联系的，这个结点称为父结点，两个子结点称为父结点的孩子。,A,B,C,根结点,右子树,D,E,F,第0层,第1层,第2层,第3层,二叉树的基本概念,3.,.,从二叉树中的一个结点往下，到达它的某个子、孙结点时所经由的路线，称为一条“路径”。对于一条路径来说，从开始结点到终止结点，中间经过的结点
3、个数，称为路径的“长度”。特别地，从根结点开始、到达某个结点的路径长度，称为该结点的“深度”。,.,在二叉树中，由于每个非根结点只有一个父结点，所以从二叉树的任一结点到它的子、孙结点的路径都是唯一的。,.,二叉树是一种层次结构。通常，把一棵二叉树的根算作第0层，其余结点的层次值，为其父结点所在层值加1。,.,一棵二叉树的“高度”，是指该二叉树的最大层次数值。二叉树的高度，有时也称为是二叉树的深度。,.,所谓一个结点的“度”，是指该结点拥有子树的个数。对于二叉树来说，任何一个结点的度最多是2。通常，把二叉树中那些度为0的结点，称作是“叶结点”。,.,叶结点 ： 没有非空子树（即度为0）的结点。,
4、(1),一棵一般的二叉树，是由如下的3类结点组成的：,根结点 ： 二叉树的起始结点；,(2),分支（或内部）结点 ： 至少有一个非空子树（即度为1或2）的结点；,(3),左子树,满二叉树和完全二叉树,4.,.,所谓“满二叉树”，是指该二叉树的每一个结点，或者有两个非空子树，或者是叶结点，并且每层都必须含有最多的结点个数。,D,H,I,E,J,K,B,F,L,M,G,N,O,C,A,根结点,分支结点,叶结点,不是满二叉树的例子,.,D,E,F,G,B,C,A,D,H,I,E,J,K,B,F,L,M,G,C,A,.,所谓“完全二叉树”，是指该二叉树除最后一层外，其余各层的结点都必须是满的，最后一层
5、的结点都必须集中在左边，右边可以连续缺少若干个结点。,D,H,I,E,J,K,B,F,L,G,C,A,D,H,E,B,F,G,C,A,.,满二叉树与完全二叉树间的关系是：满二叉树一定是一棵完全二叉树，但完全二叉树却不一定是一棵满二叉树。如果一棵二叉树不是完全二叉树，那么它绝不可能是一棵满二叉树。,（用归纳法）二叉树的第0层只有一个结点。所以，当i=0时，2i=20=1成立。 假设第i层最多有2i个结点。那么，由于二叉树每个结点的度最多为2，因此第i+1层结点的个数，最多应该是第i层结点个数的2倍，即22i = 2i+1，命题得证。,5.1.2 二叉树的性质,下面介绍的性质5-1性质5-3对任何
6、二叉树都成立，性质5-4只是对完全二叉树成立。由于满二叉树一定是完全二叉树，因此性质4既适用于完全二叉树，也适用于满二叉树。,性质5-1,在任何一棵二叉树的第i（i0）层上，最多有2i个结点。,.,【证明】,性质5-2,【证明】,树高为k（k0）的二叉树，最多有2k+11个结点。,由性质5-1可知，在树高为k的二叉树里，第0层有20个结点，第1层有21个结点，第2层有22个结点，第k层有2k个结点。因此，要求出树高为k的二叉树的结点个数，就是求和： 20 + 21 + 22 + 2k 这是一个等比数列，求前k+1项的和Sk+1的求和公式为： Sk+1 =（a0 akq）/（1q） 其中a0为第
7、1项，ak为第k+1项，q为公比。于是，该数列前k+1项之和Sk+1为： Sk+1 = (202k2)/(12) = (12k+1)/(12) = 2k+11,一棵高度为9的满二叉树有多少个叶结点？有多少个度为2的结点？总共有多少个结点？,如果一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则有关系：n0 = n2 + 1。,二叉树中度为1的结点个数为n1，那么二叉树总的结点个数n应是： n = n0 + n1 + n2 (1) 另一方面，二叉树中除根结点外，其余结点都将在某个分支边下面。设这个分支边数为m，那么二叉树总的结点个数应该是分支边数加上1（这个1是根结点），即： n
8、= m + 1 (2) 注意到每一条分支边或是由度为1的结点发出，或是由度为2的结点发出，度为1的结点发出一条边，度为2的结点发出两条边。因此，又有关系： m = n1 + 2n2 (3) 把式(3)代入式(2)，得： n = n1 + 2n2 + 1 (4) 综合式(1)和式(4)，立即可以得出所需要的结论。,性质5-3,【证明】,例：,这是一棵高度为9的满二叉树，因此每层上都有最大的结点数。叶结点在最底的第9层。根据性质5-1，在第9层上最多有29=512个结点。另外，满二叉树只由度为0和2的结点组成。根据性质5-3，一棵二叉树度为0和2的结点间有关系n0 = n2 + 1，即是：n2 =
9、 n01。因此，高度为9的满二叉树共有度为2的结点29-1=5121=511个。最后根据性质5-2，就知这棵高度为9的满二叉树总共有2101=10241=1023个结点。,解：,来看结点D，它的序号为41，因此它不是根结点。按性质5-4(2)，它的父结点序号应该是4/2取整，结果是2。从图上看，D的父结点是B，序号正是2。再看E，它的序号51。按性质5-4(2)，它的父结点序号应 是5/2取整，结果是2。从图上看，E的父结点是B，序号正是2。 再看F，它的序号是6。由于26=12n，根据性质5-4(3) 表示它肯定有左子树，且左孩子的序号应该是26=12。 从图上看，F左子树的根结点为L，其序
10、号正是12。对 于F来说，26+1=13n，根据性质5-4(4)表示它没有右 子树。从图上看，它确实没有右子树。,对有n个结点的完全二叉树，将其所有结点按照从上到下、从左到右的顺序进行编号。那么，二叉树中任意一个结点的序号i（1in）满足下面的关系：,性质5-4,(4) 若2i+1n，则序号为i的结点没右子树，否则其右孩子的序号为2i+1。,(1) 若i=1，则该结点为这棵完全二叉树的根结点，它没有父结点；,(2) 若i1，则该结点的父结点的序号为i/2取整数(即i除以2后的整数商)；,(3) 若2in，则序号为i的结点没左子树，否则其左孩子的序号为2i；,.,性质5-4里的4条结论，第1条给
11、出了根据结点序号判定它是否为根结点的方法；第2条给出了由一个结点的序号求其父结点序号的方法；第3条和第4条给出了由结点序号判定该结点是否有左、右子树，以及求左、右孩子序号的方法。,D,H,I,E,J,K,B,F,L,G,C,A,1,2,3,4,5,6,7,8,9,10,11,12,例：,图中的完全二叉树有n=12个结点。,5.2 二叉树的存储结构,5.2.1 二叉树的顺序存储结构,1.,二叉树顺序存储的含义,所谓二叉树的顺序存储，就是用一个一维数组来存放二叉树中的结点。即把二叉树的结点按照从上到下、从左到右的次序排列好，然后顺序存入数组。由于二叉树不是线性结构，因此存放在数组里的二叉树结点间的
12、这种线性序列，并不能真正反映出它们在逻辑上的邻接关系。只有在存储结点中增加一些其他信息，体现出该结点在逻辑上的前驱和后继关系，才能使这样的存储有意义。,2.,完全二叉树的顺序存储,利用性质5-4，将完全二叉树的结点以编号为顺序存储在一维数组中，编号就是数组元素的下标。这样，不必附加存储其他信息，根据存储结点的下标，就能得到它与完全二叉树中其他结点的邻接关系。,D,E,B,F,C,A,1,2,3,4,5,6,完全二叉树Cb ：,Cb ：,A,1,B,2,C,3,D,4,E,5,F,6,7,8,.,.,3.,一般二叉树的顺序存储,为在实现一般二叉树的顺序存储时，能利用性质 5-4 ，就须对一般二叉
13、树进行改造，让它在形式上类同与完全二叉树。由于二叉树每个结点至多只有两个子树，因此可用增添并不存在的空结点的方法，把一般二叉树改造成为一棵完全二叉树。改造过程及顺序存储如(1)(3)所示。,.,D,F,B,E,C,A,1,2,3,4,5,6,7,8,9,10,11,12,D,F,G,B,E,C,A,13,G,A,1,B,2,C,3,D,4,E,5,F,6,7,8,9,10,11,12,G,13,14,15,16,改造,顺序存储,.,用增添空结点改造一般二叉树的方法实现顺序存储，会造成大量存储空间的浪费，最坏的情况出现在单支树时。如下图所示，一棵深度为3的右单支树，只有4个结点，却要为11个空结
14、点分配存储空间，存储浪费是极大的。,C,D,B,A,C,D,B,A,改造,(1),(2),(3),若让一个存储结点包含 3种邻接关系，那么就称是二叉树的三叉链表存储结构。,5.2.2 二叉树的链式存储结构,1.,二叉树链式存储结构的含义,2.,二叉树的三叉链表存储结构,所谓二叉树的链式存储，即是在存储结点里通过指针指示二叉树结点间逻辑关系 的信息。二叉树的结点应该有3种邻接关系：与它父结点的邻接关系，与它左子树根结点的邻接关系，与它右子树根结点的邻接关系。与父结点的邻接关系，是一种向上的邻接关系；与左子树、右子树的关系，是一种向下的邻接关系。,B,E,C,A,D,F,G,指向右孩子,数据元素值,指向左孩子,指向父结点,Lchild,Data,Rchild,Parent,A,B,C,D,G,E,F,这 时，二叉树上每个结点的存储结点由 4个域组 成 。,.,.,3.,二叉树的二叉链表存储结构,若让一个存储结点只包含与其子树的邻接关系，那么就称是二叉树的二叉链表存储结构。这时，二叉树上每个结点的存储结点由3个域组成 。,指向右孩子,数据元素值,指向左孩子,Lchild,Data,Rchild,B,E,C,A,D,F,G,A,B,C,D,G,
