栈的应用和串图.ppt

6.1 树 6.2 二叉树 二叉树的5种形态： 二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。 假设对所有的j，1≤ji成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。 【性质2】 深度为K的二叉树最多有2K-1个结点（K≥1）。 其中 a1为第一项，an为第n项，q为比值。可以得到，该数列前K项之和为： 完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。 【性质4】 具有n个结点的完全二叉树的深度为 ?log2n?+1。其中，?log2n? 的结果是不大于log2n的最大整数。 证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出： 2K-1-1n≤2K-1 将不等式两端加1得到： 2K-1≤n2K 将不等式中的三项同取以2为底的对数，并经过化简后得到： K-1≤log2nK 由此可以得到：?log2n? =K-1。整理后得到：K= ?log2n?+1。 【性质5】 对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1≤i≤n），都有： （1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为 ?i/2?。 （2）如果2in，则结点i没有左孩子；否则其左孩子结点的编号为2i。 （3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。 下面我们利用数学归纳法证明这个性质。 我们首先证明（2）和（3）。 当i=1时，若n≥3，则根的左、右孩子的编号分别是2，3；若n3，则根没有右孩子；若n2，则根将没有左、右孩子；以上对于（2）和（3）均成立。 假设：对于所有的1≤j≤i 结论成立。即：结点j的左孩子编号为2j；右孩子编号为2j+1。 由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。 可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i 的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编号为2(i+1)；右孩子编号为2(i+1)+1。 又因为二叉树由n个结点组成，所以，当2(i+1)+1n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)n，结点i+1既没有左孩子也没有右孩子。 以上证明得到（2）和（3）成立。 下面利用上面的结论证明（1）。 对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而 ?2i/2?=i；若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而 ?(2i+1)/2? =i，由此可以得出（1）成立。 6.2.3 二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。 1. 顺序存储结构 这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。 3．2 链式存储结构 在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。 常见的二叉树结点结构如