L第十二讲(二叉树的性质及其遍历)

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构与算法,-第十,二,讲,王伦津 研究员,二叉树的性质及其遍历,1,12、二叉树的性质及二叉树的遍历,本讲给出二叉树基本性质的七个定理的证明，介绍二叉树的前序遍历、中序遍历、后序遍历和层序遍历思想，和二叉树的存储结构。,本讲的基本要求是：掌握二叉树的性质及其遍历思想,2,目 录,12.1二叉树的基本性质,12.1.1 定理1 满二叉树第i层上恰有2,i-1,个结点。（i1）,12.1.2 定理2 二叉树的第i层上结点个数不超过2,i-1,个。 （i1）,12.1.3 定理3 深度为k的满二叉树有2,k,-1个结点。,12.1.4 定理4 深度为k的二叉树，至多有2,k,-1 个结点。,12.1.5 定理5 对任意一棵二叉树，有n,0,=n,2,+1,n=2n,0,+n,1,-1,其中，n,0,n,1,和n,2,分别为度为0、1和2的结点的数目，n 表示结点总数。,12.1.6 定理6 具有n个结点的二叉树的深度为log2n+1。,3,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）若2i+1n，则结点i无右儿子；否则右儿子是结点2i+1。,4,12.1 二叉树的基本性质,证：使用归纳法。i=1时，结论显然成立。设i=k时结论成立，则考虑i=k+1的情形。由于(k+1)层上结点是k层上结点的儿子，而且满二叉树每个非叶子结点恰好有两个儿子，故(k+1)层上结点个数为k层上结点个数的2倍，即22,k-1,= 2,k,=,2(k+1)-1,. 这表明，i=k+1时结论也成立。由归纳法原理，结论对任意的k都成立，证毕。,定理 1：满二叉树第i层上恰好有2,i-1,个结点(i1).,5,证：结点总数,（定理,1,）,2,k,-1.,证毕。,定理 2：二叉树的第i层上结点个数不超过2,i-1,.(i1).,事实上，这是定理 1的直接推论，因为任何二叉树，只有满二叉树的结点最多。,定理 3：深度为k的满二叉树有2,k,-1个结点。,6,证：显然，,n=n,0,+n,1,+n,2,另一方面，由于二叉树除根外每个结点恰好有一个前趋，所以，非根结点恰与分枝一一对应，故有,n=B+1（分支实际上就是树中的连线）,这里，,B,为分枝数目。又分枝是由度为,1,和,2,的结点射出的，故有,B=n,1,+2n,2,结合上面三式，即可导出,n,0,=n,2,+1,与,n=2n,0,+n,1,-1,定理 4：深度为k的二叉树，至多有(2,k,-1)个结点。,此乃定理 3的直接推论。,定理 5：对任一棵二叉树，有 n,0,=n,2,+1 n=2n,0,+n,1,-1这里，n,0,、n,1,和n,2,分别为度为0、1和2的结点的数目，n表示结点总数。,7,证：设,k,为顺序二叉树的深度，由定理,4,知,n,2,k,-1,由于这里,n,与,2,k,均为整数，故,nlog,2,n (a,）,另一方面，由于是顺序二叉树，去掉最后一层后必为满二叉树，故,(k-1),层以上结点总数为,2,k-1,-1,，因此有,n2,k-1,-1,。由于,n,与,2,k-1,均为整数，为,2,k-1,-1,加一后，有可能与,n,相等，但不会变得大于,n,，故,n,2,k-1,，即,k,log,2,n+1 .(b ),现在，我们已得到,(a),与（,b,）两式，即,log,2,n k,log,2,n+1,由于,k,为整数，故必有,k=log,2,n+1,（见图,120,）,定理 6：具有n个结点的顺序二叉树的深度为log,2,n+1（这里，符号x表示不大于x的最大整数）。,8,1单位,1单位，k所在区间,log,2,n,log2n,+1,log,2,n,图12 0 log,2,n1,，则其父亲的编号为,i/2;,(b),若,2in,，则结点,i,无左儿子,(,从而也无右儿，为叶子,),，否则,i,的左儿子的编号为,2i,。,(c),若,2i+1n,，则结点,i,无右孩子，否则它的右孩子结点的编号为,2i+1,。,10,1,8,3,7,6,5,4,2,1,8,3,7,6,5,4,2,11,9,10,上述是两种顺序二叉树，从根结点开始编号，我们发现所有左结点编号均为偶数，所有右结点均为奇数。还有两种顺序二叉树一种就是满二叉树，一种是缺一个元素即为满二叉树的情况。它们的编号同样满足上面的规律。,11,证：先证(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时结论成立,；,12,若k+1有右儿子（当然也有左儿子），则编号为(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)的式子变换而来，证毕。,13,12.2 二叉树的遍历的概念,(一) 基本概念,遍历就是无重复无遗漏的访问。对于树的遍历，是指,按一定方式访问树中的结点，使得每个结点恰好被访问,一次。访问方式是指访问次序。假定执行访问机构是单处理机的，任何时刻只能对一个目标进行访问，,所以，访问的轨迹是被访问结点的线性序列，即遍历,结果是树中各结点按某种次序的一个线性序列。通过遍,历，非线性结构被映射成了线性结构。,二叉树的遍历方式有前序遍历、中序遍历、后序遍历与层序遍历四种，现分述如下。,14,二叉树前序遍历定义为： 若树为空，则不作任何动作，返回，否则，先访问根结点，然后按前序方式分别遍历根的左子树和右子树。,简言之，前序遍历是按“根左子树右子树”的次序遍历二叉树。显然，这是个递归定义，下面的中序遍历和后序遍历也是按递归方式定义的。前序遍历实例见图,121.,1,2,3,4,5,6,7,前序遍历结果：1 2 4 5 3 6 7,图12 1 二叉树遍历示例,(二) 前序遍历,1,2,3,4,5,6,7,15,简言之，中序遍历是按“左子树根右子树”的次序遍历树。其实例见图,121,(三) 中序遍历,二叉树中序遍历定义为： 若树为空，则不作任何动作，返回，否则，先按中序方式遍历根的左子树，然后访问根，最后再按中序方式遍历根的右子树。,7,1,2,3,4,5,6,中序遍历结果：2 5 4 1 3 7 6,16,简言之，后序遍历是按“左子树右子树根”的次序遍历二叉树。其实例见图121.,(四) 后序遍历,二叉树后序遍历定义为： 若树为空，则不作任何动作，返回，否则，先分别按后序遍历方式遍历根的左子树与右子树，然后访问根。,1,2,3,4,5,6,7,后序遍历结果：5 4 2 7 6 3 1,17,实例见图,(五) 层序遍历,层序遍历是按树的层序编号的次序访问各结点，即按从上层到下层，同层内从左到右的次序访问结点。,1,2,3,4,5,6,7,层序遍历结果：1 2 3 4 6 5 7,18,遍历是树结构的一种重要的操作（我们在后面还要给出一般树的遍历的概念），许多对树的操作，都是基于遍历的。另外，遍历也是树的一种串行化，即将树中结点按某种方式线性输出。,在前三种方式的定义中，采用了递归描述方式，这种描述方式简洁而准确。但注意这种描述必须有始基。在上面的定义中，始基就是“若树为空，则不做任何动作”，若无此句，所定义的遍历将是个无限动作。,19,12.3二叉树的存储结构,二叉树存储结构应能体现二叉树的逻辑关系，即单前驱多后继的关系。在具体的应用中，可能要求从任一结点能直接访问到它的后继（即儿子），或直接访问到它的前驱（父亲），或同时直接访问父亲和儿子。所以，存储结构的设计，要按这些要求进行。,20,12.3.1顺序存储结构,(一) 顺序二叉树的顺序存储结构,这种存储结构是按结点的层序编号的次序，将结点存储在一片连续存储区域内。由定理 7知，对顺序二叉树，若已知结点的层序编号，则可推算出它的父亲和儿子的编号，所以，在这种存储结构中，很容易根据结点的相对地址计算出它的父亲和儿子的相对地址，方法是：,x的相对地址,x的编号,x的父亲/儿子的编号(性质7),x的父亲/儿子的相对地址。,21,至于结点的相对地址与编号之间的换算，有下列关系：,结点相对地址 = （结点编号,1）每个结点所占单元数目,a,b,f,c,e,g,h,d,1 2 3 4 5 6 7 8,a b f c e g h d ,图 122 顺序二叉树的顺序存储,图 122给出了这种存储结构的示例。这种存储方式，逻辑结构用存储次序体现，故若不进行插入与删除操作，是一种很经济的存储方式,22,(二) 一般二叉树的顺序存储,由于定理 7只对顺序二叉树（包括满二叉树）成立，所以，对一般的二叉树而言，若要利用定理 7访问一个结点的父亲与儿子，则需在该二叉树中补设一些虚结点，使它成为一棵顺序二叉树，然后对结点按层序编号。这样处理后，再按顺序二叉树的顺序存储方式存储。这种带虚结点的树，虚结点也要对应存储位置，但要设立虚结点标志。,23,a,b,c,1 2 3 4 5 6 7 9 ,a x b x x x c ,图 12 3一般二叉树的连续存储(x表示虚结点的位置),这种存储方式中，实结点是不连续出现的，所以，若虚结点对应的存储位置不能被利用，则是一种很大的浪费（虚结点数目可能很大），图 123给出了这种存储结构的示例。,24,12.3.2 链式存储,二叉树一般多采用链式存储。这种存储方式的基本思想是，令每个树结点对应一个链结点，链结点除存放与树结点有关的信息外，还要根据具体应用的需要设置指示父亲、儿子的指针。根据指针设置情况，存储方式分为一指针式、二指针式和三指针式。,25,为每个结点只设立指向其前驱的指针。由于每个结点的前驱是唯一的，故每个结点只需设一个前驱指针。在树中，前驱称为父亲，所以这种方式也称父指针式。,显然，这种存储方式下，已知某结点的指针，很容易找到它的父亲，但要找到它的儿子，需从叶子起搜索，很耗时。另一问题是，虽可知道儿子，但不能区分是左儿还是右儿。,(一) 一指针式,26,为了解决该问题，可在结点上设立左右儿标志位。因此，一指针式存储在存储了左右儿标志的情况下，是关系完备的（即存储了全部关系信息）。,对一指针结构，只有知道每个叶子的地址，才能访问到一棵树中的每个结点。因此，需要将一棵树中各个叶子的地址记录下来。为此，对每棵树，设立一个数组，将各叶子地址分别保存在数组的各个元素中。一指针式的结点结构如图 124(a)，示例如图 125(b)。,27,内容,父指针,(a) 一指针结点,内容,左儿指针,右儿指针,(b) 二指针结点,内容,父指针,左儿指针,右儿指针,(c) 三指针结点,图 12 4二叉树链式存储方式的结点结构,28,1,2,3,4,5,(a) 二叉树,1,2,3,4,5,(b) (a)树的一指针存储,1,2,3,4,5,(c) (a)树的二指针存储,1,2,4,5,(d) (a)树的三指针存储,图 12 5二叉树链式存储结构示例,29,这种方法是，为每个结点只设立指向其后继的指针。由于二叉树每个结点的后继最多有两个，故每个结点需设二个后继指针，分别称为左儿指针和右儿指针。 显然，在这种储存方式下，从根出发可以访问到所有结点，所以，记录下根的地址后，就可以访问到各个元素。因此，二指针式在已知根的情况下，是关系完备的。 虽然已知某结点的指针，很容易找到它的儿子，但要找到它的父亲，一般需从根起搜索，很耗时。二指针式的结点结构如图,124 (b),，示例如图,125 (c),。,(二)二指针式,30,三指针式是一指针和二指针的结合，即每个结点分别设立三个指针，分别指向其前驱和两个后继。三指针式同时具有一指针和二指针的的优点，当然是通过存储空间换来的。三指针式的结点结构如图,124 (c),，示例如图,125 (d),。,显然，三指针式在关系存储方面有冗余（我们前面已指出，二指针是关系完备的）。与普通链式存储一样，二叉树的链式存储也既可以是“静态”的，也可以是“动态”的。不过，由于动态链式更多地隐蔽了存储管理细节，使我们能用更多的精力考虑其他问题，所以，我们下面一般以动态为主。当然，也将适当介绍静态方法。,(三)三指针式,31,下面给出二叉树结点（三指针）的数据部分的C+描述。关于它的完整对象描述，将在后面给出。,template /对树结点内容使用可变类型,struct TBinTreeNode,TElem info; /树结点内容，类型为可变类型（类模板）,TBinTreeNode *father; /父指针,TBinTreeNode *lc, *rc; /左儿指针、右儿指针,;,(四) 存储结构的高级语言描述,32,本讲小结,本讲介绍了二叉树的基本性质的7个定理，定理1至5是用来计算二叉树的结点个数的，定理6是用来计算顺序二叉树深度的，定理7在顺序二叉树的搜索中非常有用，可以根据结点编号确定父结点或左右儿子结点的编号。本讲的另一个重点是二叉树的遍历的直观理解和二叉树的存储结构。,33,思考与练习,1、设一棵顺序二叉树具有10 个结点，请计算其中一子结点的数目。,2、请给出下列二叉树的前序、后序、中序和层序遍历结果,(a),a,b,c,d,e,f,g,a,b,c,d,e,f,（b),34,