L第12讲[二叉树的性质及其遍历].pptVIP

数据结构与算法 ---第十二讲;12、二叉树的性质及二叉树的遍历 ;目 录;12.2 二叉树的遍历 12.3 二叉树的存储结构 12.3.1 顺序存储结构 12.3.2 链式存储; 12.1 二叉树的基本性质; 证：结点总数＝　　　　　　　   ＝　 （定理 1）　　　　　　  ＝   ＝2k-1.证毕。;证：显然，n=n0+n1+n2另一方面，由于二叉树除根外每个结点恰好有一个前趋，所以，非根结点恰与分枝一一对应，故有 n=B+1（分支实际上就是树中的连线） 这里，B为分枝数目。又分枝是由度为1和2的结点射出的，故有 B=n1+2n2 结合上面三式，即可导出n0=n2+1与n=2n0+n1-1; 证：设k为顺序二叉树的深度，由定理 4知 n ≤ 2k-1 由于这里n与2k均为整数，故n2k，从而 klog2n …………(a）另一方面，由于是顺序二叉树，去掉最后一层后必为满二叉树，故(k-1)层以上结点总数为2k-1-1，因此有n2k-1-1。由于n与2k-1均为整数，为2k-1-1加一后，有可能与n相等，但不会变得大于n，故n≥2k-1，即  k≤log2n+1 …………..(b ) 现在，我们已得到(a)与（b）两式，即 log2n k≤log2n+1由于k为整数，故必有k=[log2n]+1（见图 12?0）;1单位; 定理 7：若对一棵顺序二叉树的结点按层序编号（即从根所在层起，依次从层号较小的层到层号较大的层、同层从左到右，给各结点依次编以连续的号码），则对任一结点i（1≤i≤n，n为结点数目，1为根的编号），有 (a)若i=1，则结点i是根，无父亲，若i1，则其父亲的编号为[i/2]; (b)若2in，则结点i无左儿子(从而也无右儿，为叶子)，否则i的左儿子的编号为2i。 (c)若2i+1n，则结点i无右孩子，否则它的右孩子结点的编号为2i+1。;1;?证：先证(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有右儿子（当然也有左儿子），则编号为(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 二叉树的遍历的概念 ; 二叉树前序遍历定义为： 若树为空，则不作任何动作，返回，否则，先访问根结点，然后按前序方式分别遍历根的左子树和右子树。 简言之，前序遍历是按“根─左子树─右子树”的次序遍历二叉树。显然，这是个递归定义，下面的中序遍历和后序遍历也是按递归方式定义的。前序遍历实例见图 12?1.; 简言之，中序遍历是按“左子树─根─右子树”的次序遍历树。其实例见图 12?1; 简言之，后序遍历是按“左子树─右子树─根”的次序遍历二叉树。其实例见图12?1. ?;实例见图 ?;遍历是树结构的一种重要的操作（我们在后面还要给出一般树的遍历的概念），许多对树的操作，都是基于遍历的。另外，遍历也是树的一种串行化，即将树中结点按某种方式线性输出。;12.3二叉树的