《l第十二讲(二叉树的性质及其遍历)》由会员分享,可在线阅读,更多相关《l第十二讲(二叉树的性质及其遍历)(34页珍藏版)》请在金锄头文库上搜索。
1、数据结构与算法 -第十二讲,北方民族大学 计算机科学与工程学院 王伦津 研究员,二叉树的性质及其遍历,12、二叉树的性质及二叉树的遍历,本讲给出二叉树基本性质的七个定理的证明,介绍二叉树的前序遍历、中序遍历、后序遍历和层序遍历思想,和二叉树的存储结构。 本讲的基本要求是:掌握二叉树的性质及其遍历思想,目 录,12.1二叉树的基本性质 12.1.1 定理1 满二叉树第i层上恰有2i-1个结点。(i1) 12.1.2 定理2 二叉树的第i层上结点个数不超过2i-1 个。 (i1) 12.1.3 定理3 深度为k的满二叉树有2k-1个结点。 12.1.4 定理4 深度为k的二叉树,至多有2k-1 个
2、结点。 12.1.5 定理5 对任意一棵二叉树,有n0=n2+1,n=2n0+n1-1,其中,n0,n1和n2分别为度为0、1和2的结点的数目,n 表示结点总数。 12.1.6 定理6 具有n个结点的二叉树的深度为log2n+1。,12.2 二叉树的遍历 12.3 二叉树的存储结构 12.3.1 顺序存储结构 12.3.2 链式存储,12.1.7 定理7 若对一棵有n个结点的顺序二叉树的结点按层序编号,则对任一结点i(1in),有(1)若i=1, 则结点i是根,无父亲;若i1,则其父亲是结点i/2。(2)若2in,则结点i无左儿子(从而也无右儿子,为叶子);否则i的左儿子是结点2i。(3)若2
3、i+1n,则结点i无右儿子;否则右儿子是结点2i+1。,12.1 二叉树的基本性质,证:使用归纳法。i=1时,结论显然成立。设i=k时结论成立,则考虑i=k+1的情形。由于(k+1)层上结点是k层上结点的儿子,而且满二叉树每个非叶子结点恰好有两个儿子,故(k+1)层上结点个数为k层上结点个数的2倍,即22k-1 = 2k = 2(k+1)-1. 这表明,i=k+1时结论也成立。由归纳法原理,结论对任意的k都成立,证毕。,定理 1:满二叉树第i层上恰好有2i-1个结点(i1).,证:结点总数 (定理 1) 2k-1.证毕。,定理 2:二叉树的第i层上结点个数不超过2i-1.(i1).,事实上,这
4、是定理 1的直接推论,因为任何二叉树,只有满二叉树的结点最多。,定理 3:深度为k的满二叉树有2k-1个结点。,证:显然,n=n0+n1+n2 另一方面,由于二叉树除根外每个结点恰好有一个前趋,所以,非根结点恰与分枝一一对应,故有 n=B+1 (分支实际上就是树中的连线) 这里,B为分枝数目。又分枝是由度为1和2的结点射出的,故有 B=n1+2n2 结合上面三式,即可导出n0=n2+1与n=2n0+n1-1,定理 4:深度为k的二叉树,至多有(2k-1)个结点。,此乃定理 3的直接推论。,定理 5:对任一棵二叉树,有 n0=n2+1 n=2n0+n1-1 这里,n0、n1和n2分别为度为0、1
5、和2的结点的数目,n表示结点总数。,证:设k为顺序二叉树的深度,由定理 4知 n 2k-1 由于这里n与2k均为整数,故nlog2n (a) 另一方面,由于是顺序二叉树,去掉最后一层后必为满二叉树,故(k-1)层以上结点总数为2k-1-1,因此有n2k-1-1。由于n与2k-1均为整数,为2k-1-1加一后,有可能与n相等,但不会变得大于n,故n2k-1,即 klog2n+1 (b ) 现在,我们已得到(a)与(b)两式,即 log2n klog2n+1 由于k为整数,故必有k=log2n+1(见图 120),定理 6:具有n个结点的顺序二叉树的深度为log2n+1(这里,符号x表示不大于x的
6、最大整数)。,定理 7:若对一棵顺序二叉树的结点按层序编号(即从根所在层起,依次从层号较小的层到层号较大的层、同层从左到右,给各结点依次编以连续的号码),则对任一结点i(1in,n为结点数目,1为根的编号),有 (a)若i=1,则结点i是根,无父亲,若i1,则其父亲的编号为i/2; (b)若2in,则结点i无左儿子(从而也无右儿,为叶子),否则i的左儿子的编号为2i。 (c)若2i+1n,则结点i无右孩子,否则它的右孩子结点的编号为2i+1。,11,9,10,上述是两种顺序二叉树,从根结点开始编号,我们发现所有左结点编号均为偶数,所有右结点均为奇数。还有两种顺序二叉树一种就是满二叉树,一种是缺
7、一个元素即为满二叉树的情况。它们的编号同样满足上面的规律。,证:先证(b)和(c),用归纳法。当i=1时,结论是显然的。现设i=k时结论(b)成立,考虑i=k+1的情形。若k结点无左儿子或无右儿子,则(k+1)亦必为叶子(否则就不是顺序二叉树了),故证明(b)时无需考虑此情况,而只需考虑k有两个儿子的情况。先考虑k与k+1在同一层上,则由顺序二叉树的结构知,若(k+1)有儿子,则必然出现在下一层上k的两个儿子的紧右边,由于k的两个儿子的编号为2k与2k+1(归纳假设),故(k+1)若有左儿子,则编号为(2k+1)+1即2(k+1),这表示i=k+1时结论成立;,若k+1有右儿子(当然也有左儿子
8、),则编号为(2k+1)+2,即2(k+1)+1,这表明(iii)在k+1时仍成立。再考虑k与k+1不在同一层的情况,此时,k必在它所在层的最右,而k+1必在下一层的最左,由于顺序二叉树编号是编完上层最右结点时从下层最左结点起编号,所以若k+1有儿子,则编号必然为(2i+1)+1与(2i+1)+2,这与k与k+1位于同层的情况相同。至于(a),则可由(b)与(c)的式子变换而来,证毕。,12.2 二叉树的遍历的概念,(一) 基本概念 遍历就是无重复无遗漏的访问。对于树的遍历,是指 按一定方式访问树中的结点,使得每个结点恰好被访问 一次。访问方式是指访问次序。假定执行访问机构是单处理机的,任何时
9、刻只能对一个目标进行访问, 所以,访问的轨迹是被访问结点的线性序列,即遍历 结果是树中各结点按某种次序的一个线性序列。通过遍 历,非线性结构被映射成了线性结构。,二叉树的遍历方式有前序遍历、中序遍历、后序遍历与层序遍历四种,现分述如下。,二叉树前序遍历定义为: 若树为空,则不作任何动作,返回,否则,先访问根结点,然后按前序方式分别遍历根的左子树和右子树。 简言之,前序遍历是按“根左子树右子树”的次序遍历二叉树。显然,这是个递归定义,下面的中序遍历和后序遍历也是按递归方式定义的。前序遍历实例见图 121.,前序遍历结果:1 2 4 5 3 6 7,图12 1 二叉树遍历示例,(二) 前序遍历,7
10、,简言之,中序遍历是按“左子树根右子树”的次序遍历树。其实例见图 121,(三) 中序遍历,二叉树中序遍历定义为: 若树为空,则不作任何动作,返回,否则,先按中序方式遍历根的左子树,然后访问根,最后再按中序方式遍历根的右子树。,中序遍历结果:2 5 4 1 3 7 6,简言之,后序遍历是按“左子树右子树根”的次序遍历二叉树。其实例见图121.,(四) 后序遍历,二叉树后序遍历定义为: 若树为空,则不作任何动作,返回,否则,先分别按后序遍历方式遍历根的左子树与右子树,然后访问根。,7,后序遍历结果:5 4 2 7 6 3 1,实例见图,(五) 层序遍历,层序遍历是按树的层序编号的次序访问各结点,
11、即按从上层到下层,同层内从左到右的次序访问结点。,层序遍历结果:1 2 3 4 6 5 7,遍历是树结构的一种重要的操作(我们在后面还要给出一般树的遍历的概念),许多对树的操作,都是基于遍历的。另外,遍历也是树的一种串行化,即将树中结点按某种方式线性输出。,在前三种方式的定义中,采用了递归描述方式,这种描述方式简洁而准确。但注意这种描述必须有始基。在上面的定义中,始基就是“若树为空,则不做任何动作”,若无此句,所定义的遍历将是个无限动作。,12.3二叉树的存储结构,二叉树存储结构应能体现二叉树的逻辑关系,即单前驱多后继的关系。在具体的应用中,可能要求从任一结点能直接访问到它的后继(即儿子),或
12、直接访问到它的前驱(父亲),或同时直接访问父亲和儿子。所以,存储结构的设计,要按这些要求进行。,12.3.1顺序存储结构,(一) 顺序二叉树的顺序存储结构 这种存储结构是按结点的层序编号的次序,将结点存储在一片连续存储区域内。由定理 7知,对顺序二叉树,若已知结点的层序编号,则可推算出它的父亲和儿子的编号,所以,在这种存储结构中,很容易根据结点的相对地址计算出它的父亲和儿子的相对地址,方法是: x的相对地址x的编号x的父亲/儿子的编号(性质7) x的父亲/儿子的相对地址。,至于结点的相对地址与编号之间的换算,有下列关系: 结点相对地址 = (结点编号 1)每个结点所占单元数目,图 122给出了
13、这种存储结构的示例。这种存储方式,逻辑结构用存储次序体现,故若不进行插入与删除操作,是一种很经济的存储方式,(二) 一般二叉树的顺序存储,由于定理 7只对顺序二叉树(包括满二叉树)成立,所以,对一般的二叉树而言,若要利用定理 7访问一个结点的父亲与儿子,则需在该二叉树中补设一些虚结点,使它成为一棵顺序二叉树,然后对结点按层序编号。这样处理后,再按顺序二叉树的顺序存储方式存储。这种带虚结点的树,虚结点也要对应存储位置,但要设立虚结点标志。,这种存储方式中,实结点是不连续出现的,所以,若虚结点对应的存储位置不能被利用,则是一种很大的浪费(虚结点数目可能很大),图 123给出了这种存储结构的示例。,
14、12.3.2 链式存储,二叉树一般多采用链式存储。这种存储方式的基本思想是,令每个树结点对应一个链结点,链结点除存放与树结点有关的信息外,还要根据具体应用的需要设置指示父亲、儿子的指针。根据指针设置情况,存储方式分为一指针式、二指针式和三指针式。,为每个结点只设立指向其前驱的指针。由于每个结点的前驱是唯一的,故每个结点只需设一个前驱指针。在树中,前驱称为父亲,所以这种方式也称父指针式。 显然,这种存储方式下,已知某结点的指针,很容易找到它的父亲,但要找到它的儿子,需从叶子起搜索,很耗时。另一问题是,虽可知道儿子,但不能区分是左儿还是右儿。,(一) 一指针式,为了解决该问题,可在结点上设立左右儿
15、标志位。因此,一指针式存储在存储了左右儿标志的情况下,是关系完备的(即存储了全部关系信息)。 对一指针结构,只有知道每个叶子的地址,才能访问到一棵树中的每个结点。因此,需要将一棵树中各个叶子的地址记录下来。为此,对每棵树,设立一个数组,将各叶子地址分别保存在数组的各个元素中。一指针式的结点结构如图 124(a),示例如图 125(b)。,这种方法是,为每个结点只设立指向其后继的指针。由于二叉树每个结点的后继最多有两个,故每个结点需设二个后继指针,分别称为左儿指针和右儿指针。 显然,在这种储存方式下,从根出发可以访问到所有结点,所以,记录下根的地址后,就可以访问到各个元素。因此,二指针式在已知根的情况下,是关系完备的。 虽然已知某结点的指针,很容易找到它的儿子,但要找到它的父亲,一般需从根起搜索,很耗时。二指针式的结点结构如图 124 (b) ,示例如图 125 (c)。,(二)二指针式,三指针式是一指针和二指针的结合,即每个结点分别设立三个指针,分别指向其前驱和两个后继。三指针式同时具有一指针和二指针的的优点,当然是通过存储空间换来的。三指针式的结点结构如图 124 (c),示例如图 125 (d)。 显然,三指针式在关系存储方面有冗余(我们前