《数据结构 教学课件 ppt 作者 宗大华 陈吉人 05二叉树》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 宗大华 陈吉人 05二叉树（115页珍藏版）》请在金锄头文库上搜索。
1、第5章 二叉树,本章讨论二叉树，它是一种重要的非线性数据结构，有着广泛的用途。 本章主要介绍以下几个方面的内容： 二叉树的定义及性质； 二叉树的存储实现（顺序存储和链式存储）； 遍历二叉树（即对二叉树存储结点访问的各种形式）； 哈夫曼树及编码。,5.1 二叉树概述,所谓“二叉树”，是一个由结点组成的有限集合。这个集合或为空，或由一个称为根的结点以及两棵不相交的二叉树组成，这两棵二叉树分别称为根结点的左子树和右子树。,5.1.1 二叉树的基本概念,当二叉树非空时，通过结点间的边来表示从一个结点到它的两个子结点间的联系，这个结点称为父结点，两个子结点称为父结点的孩子。二叉树有如下的特征：, 二叉树
2、可以是空的，空二叉树没有任何结点； 二叉树上的每个结点最多可以有两棵子树，这两棵子树是不相交的； 二叉树上一个结点的两棵子树有左、右之分，次序是不能颠倒的。,图5-2 两棵不同的二叉树,从二叉树中的一个结点往下，到达它的某个子、孙结点时所经由的路线，称为一条“路径”。对于路径来说，从开始结点到终止结点，中间经过的结点个数，称为路径的“长度”。从根结点开始、到某个结点的路径长度，称为该结点的“深度”。,在二叉树中，由于每个非根结点只有一个父结点，所以从二叉树的任一结点到它的子、孙结点的路径都是唯一的。 二叉树是一种层次结构。通常，把它的根算作第0层，其余结点的层次值，为其父结点所在层值加1。在二
3、叉树里位于相同层的结点的深度都是相同的。 一棵二叉树的“高度”，是指该二叉树的最大层次数值。,由4个结点构成的二叉树总共有14种，其中8棵树的高度为3，6棵树的高度为2。,图5-3 大小为4的所有二叉树,例5-4 试分析由5个结点构成的二叉树一共有多少棵。 解：大小为5的不同的二叉树总共有14+5+4+5+14=42种。 所谓一个结点的“度”，是指该结点拥有子树的个数。对于二叉树来说，任何一个结点的度最多是2。通常，把二叉树中那些度为0的结点，称作是“叶”结点。,所谓“满二叉树”，是指该二叉树的每一个结点，或是有两个非空子树的结点，或是叶结点，且每层都必须含有最多的结点个数。,图5-4 一棵满
4、二叉树,图5-5所示的两棵二叉树都不是满二叉树。虽然它们都满足“每个结点或都有两个非空子树，或是叶结点”的条件，但却违背了“每层都必须含有最多的结点个数”的要求。,图5-5 非满二叉树,所谓“完全二叉树”，是指该二叉树除最后一层外，其余各层的结点都是满的，且最后一层的结点都集中在左边，右边可连续缺少若干结点。,图5-6 两棵完全二叉树,由完全二叉树的定义可知，满二叉树一定是一棵完全二叉树，但完全二叉树却不一定是一棵满二叉树。,性质5-1性质5-3对任何二叉树都成立，性质5-4只是针对完全二叉树的。,5.1.2 二叉树的性质,性质5-1 在任何一棵二叉树的第i（i0）层上，最多有2i个结点。 【
5、证明】二叉树的第0层只有一个结点。所以，当i=0时，2i=20=1成立。 假设结论对第i层成立，即第i层最多有2i个结点。由于二叉树每个结点的度最多为2，因此第i+1层结点的个数，最多应该是第i层结点个数的2倍，即22i = 2i+1，命题得证。,性质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 =（
6、a0 akq）/（1q）,其中a0为第1项，ak为第k+1项，q为公比。于是，该数列前k+1项之和Sk+1为：,Sk+1 = (202k2)/(12) = (12k+1)/(12) = 2k+11,性质5-3 如果一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则有关系：n0 = n2 + 1。 【证明】设二叉树中度为1的结点个数为n1，那么二叉树总的结点个数n应该是： n = n0 + n1 + n2 （1）,另一方面，二叉树中除根结点外，其余每个结点都将在一个分支边的下面。设这个分支边数为m，那么二叉树总的结点个数应该是分支边数加上1（这个1是根结点），即： n = m +
7、1 （2）,注意到每一条分支边或是由度为1的结点发出，或是由度为2的结点发出，度为1的结点发出一条边，度为2的结点发出两条边。因此，又有关系： m = n1 + 2n2 （3） 把式（3）代入式（2），得： n = n1 + 2n2 + 1 （4） 综合式（1）和式（4），立即可以得出所需要的结论。,性质5-4 对于有n个结点的完全二叉树，将其所有的结点按照从上到下、从左到右的顺序进行编号。那么，二叉树中任意一个结点的序号i（1in）满足下面的关系：,（1）如果i=1，则该结点为这棵完全二叉树的根结点，它没有父结点； （2）如果i1，则该结点的父结点的序号为i/2取整数（即i除以2后的整数商）
8、； （3）如果2in，则序号为i的结点没有左子树，否则其左孩子（即左子树的根结点）的序号为2i； （4）如果2i+1n，则序号为i的结点没有右子树，否则其右孩子（即右子树的根结点）的序号为2i+1。,图5-7 被编号的完全二叉树,5.2 二叉树的存储结构,利用性质5-4，将完全二叉树中的结点以编号为序存储在一维数组中，编号就是数组元素的下标。这样，根据存储结点的下标，就能得到它与完全二叉树中其他结点的邻接关系。,5.2.1 二叉树的顺序存储结构,图5-8 完全二叉数的顺序实现,可采用增添一些并不存在的空结点的方法，把一般的二叉树改造成为一棵完全二叉树。,图5-9 把一般二叉树改造成完全二叉树,
9、这种为了实现顺序存储，用增添空结点改造一般二叉树的方法，可能会造成大量存储空间的浪费，最坏的情况出现在右单支树。,图5-10 改造一般二叉树会造成存储空间的浪费,所谓二叉树的链式存储，即是在存储结点里通过指针指示二叉树结点间逻辑关系的信息。 为反映二叉树的一个结点的3种邻接关系：与它的父结点、与它左子树的根结点、与它右子树的根结点，二叉树上每个结点的存储结点应由4个域组成，成为二叉树的三叉链表存储结构。,5.2.2 二叉树的链式存储结构,图5-11 二叉树的三叉链表结构,如果让一个存储结点只包含与其子树的邻接关系，那么就是二叉树的二叉链表存储结构。这时，二叉树上每个结点的存储结点由3个域组成。
10、,图5-12 二叉树的二叉链表结构,对于一般的二叉树，目前使用最多的是二叉链表。下面介绍的二叉树的一些基本算法，都是针对二叉链表结构的。 算法5-1 新建一棵只有根结点的二叉树的算法。 创建只有以x为根结点数据域信息的一棵二叉树Bt，该结点的Lchild和Rchild域均取值NULL，算法名为Create_Bt()，最后返回指向根结点的指针。,Create_Bt() ptr = malloc(size); /* 申请一个存储结点 */ Bt=ptr; ptr-Data = x; ptr-Lchild = NULL; ptr-Rchild = NULL; return (Bt); ,算法5-2
11、在指定左孩子处插入一个新结点的算法。 已知一个二叉链表Bt，在指针Parent所指结点的左孩子处插入一个数据元素值为x的新结点，它将成为Pranet所指结点新的左子树根结点。算法名为Inl_Bt()，参数为Bt、x、Parent。,Inl_Bt(Bt, Parent, x) if (Parent = NULL) printf (“位置错！“); return (NULL); ptr = malloc (size); /* 申请存储结点空间 */ ptr-Data = x; ptr-Lchild = NULL; ptr-Rchild = NULL;, if (Parent-Lchild = NU
12、LL) /* Parent所指结点左子树为空 */ Parent-Lchild = ptr; else /* Parent所指结点左子树非空 */ ptr-Lchild = Parent-Lchild; Parent-Lchild = ptr; ,本算法先为插入做一些准备工作，一是判断参数Parent的正确性；二是为插入结点申请存储，并把该结点的Data域置为x，把Lchild、Rchild域分别置为NULL。,插入分两种情况进行。如果Parent所指结点的Lchild为空，如图5-14（a）所示，那么由指针ptr所指的新结点在插入后，就成为了Parent所指结点的左子树根结点，如图5-14（
13、b）所示；如果Parent所指结点的Lchild为非空，如图5-14（c）所示，那么由指针ptr所指的新结点在插入后，就成了Parent所指结点左子树的新根结点，原来左子树的根结点，就成了ptr所指结点的左孩子（即左子树的根结点），如图5-14（d）所示。,图5-14 往二叉树的左子树进行插入,算法5-3 在指定右孩子处插入一个新结点的算法。,5.3 遍历二叉树,所谓“遍历二叉树”，是指按照一定的路线对二叉树进行搜索，保证里面的每个结点被访问一次，而且只被访问一次。 用T、L和R分别表示二叉树的根结点、左子树和右子树。那么在到达每一个结点时，访问结点的顺序可以有以下6种不同的组合形式：,5.3
14、.1 遍历二叉树的含义, TLR先访问根结点，再访问左子树，最后访问右子树； LTR先访问左子树，再访问根结点，最后访问右子树； LRT先访问左子树，再访问右子树，最后访问根结点；, TRL先访问根结点，再访问右子树，最后访问左子树； RTL先访问右子树，再访问根结点，最后访问左子树； RLT先访问右子树，再访问左子树，最后访问根结点。,如果对左、右子树，限定“先访左后访右”，那么访问结点的六种顺序就只剩下三种不同的组合形式：TLR、LTR、LRT。通常，称TLR为二叉树的先序遍历或先根遍历，称LTR为中序遍历或中根遍历，称LRT为后序遍历或后根遍历。,例5-9 以先序遍历（TLR）的顺序访问
15、如图5-15所示的二叉树，给出访问序列。 解：对图5-15所示的二叉树的先序遍历序列应该是： A-B-D-E-H-C-F-I-G,图5-15 先序遍历二叉树例,例5-10 以中序遍历（LTR）的顺序访问如图5-15所示的二叉树，给出遍历序列。 解：对图5-15所示的二叉树进行中序遍历时，遍历的结点序列是： D-B-H-E-A-F-I-C-G 图5-16给出了一种迅速求得二叉树各种遍历序列的实用方法。,图5-16 求二叉树各种遍历序列的实用方法,从3种遍历序列可以总结出：对于任何一棵二叉树，先序遍历时根结点总是处于遍历序列之首；中序遍历时根结点的位置居中，它左子树的所有结点都在其左边，右子树的所
16、有结点都在其右边；后序遍历时根结点的位置在最后，其所有结点都在它的左边。,例5-11 试问，什么样的二叉树其中序遍历序列与后序遍历序列相同？ 解：从图5-16来看，要使一棵二叉树的中序遍历序列与后序遍历序列相同，就必须要求,例5-12 已知一棵二叉树的中序遍历序列是B-D-C-E-A-F-H-G，后序遍历序列是D-E-C-B-H-G-F-A。试根据这些信息，画出这棵二叉树。,解：根据一棵二叉树的中序遍历序列和后序遍历序列，可以唯一地决定出一棵二叉树。方法是：从后序遍历序列的最后一个结点，知道该二叉树的根结点是A。由结点A在中序遍历序列里的位置，知道该根结点的左子树里应该包含有结点B、D、C、E，右子树里应该包含有结点F、H、G，如图5-17（a）所示。,图5-17 画出二叉树的整个过程,可以用递归和非递归两种方式来实现遍历二叉树。先给出二叉树三种遍历形式的非递归算法，然后再给出递归算法。,5.3.2 遍历二叉树的实现,算
