《二叉树基本题型.doc》由会员分享，可在线阅读，更多相关《二叉树基本题型.doc（3页珍藏版）》请在金锄头文库上搜索。
1、1、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_。 2、某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序为：_。 350个 699N（N1） 二叉树中的结点分为三种： 度为2，度为1，度为0。即这个结点有两个子结点，有一个子结点，没有子结点（叶结点）。 结点总数度为2的结点度为1的结点度为0的结点 在任意二叉树中，度为2的结点的数目比度为0的结点(叶结点)数目少一个。 例如，只有三个结点的二叉树，其度为2的结点数目为1（根结点），度为0的结点（叶结点）有两个。 0 0 0 完全二叉数中，没有度为1的结点。所以 结点
2、总数度为2的结点度为0的结点 699N（N1） -首先我们知道，前序遍历的规则是：根结点左子结点右子结点 中序遍历是：左子结点根结点右子结点 后序遍历是：左子结点右子结点根结点 那么，对于一棵二叉树，前序遍历的第一个结点一定是这棵树的根结点，即根结点是a。 在中序遍历的顺序dgbaechf中，以a分成左、右两边，左边是dgb，右边是echf。 所以，这棵树现在可以确定如下： a / dgb echf 接下来再分别对左子树和右子树进行类似的操作。 对于左子树dgb来说，在前序遍历abdgcefh中找到bdg，证明这子树的根是b，那么现在可以确定的树结构如下： a / b echf / dg 再看
3、dg，前序遍历中的顺序为dg，所以d是dg这部分子树的根，那么又因为中序遍历的dg顺序也是dg，所以g是右子结点。 即： a / b echf / d g 现在看echf这部分子树，前序中顺序是cefh，所以子树根结点是c，那么左子结点是e，右子树是hf： 得到： a / b c / / d e hf g 最后只剩下hf部分了，前序遍历中是fh，所以根是f，那么h就是左子结点。 现在得到了整棵树： abdgcefh dgbaechf a / b c / / d e f / g h 对这棵树再进行后序遍历就行了，结果就是：gdbehfca 第一题解答：前面有两个公式要使用。1。假设完全二叉树有k
4、+1层，那么肯定有k层是满二叉树，这一点你好好想一想是可以想通的。所以先求出k层共有多少结点。2。根据公式1，可以列下式公式1=699，然后求k的最大值，得k = 9，说明有9层的“满二叉树”，9层共有结点2的9次方减1为 5 1 1。另外加1层的最下面一层，所以是10层。且第10层上全是叶子结点。第10层共有多少节点呢？3。699 - 511 = 188，188就是第10层的叶子结点。但是这不是全部叶子结点，因为是完全二叉树，所以在第9层的右侧部分仍有一部分叶子结点。下面来求。4。下面计算第10层上最多可容纳多少节点。利用公式2得出公式2（i =10）= 512个，除去已经计算过的188个，
5、还剩512 - 188 = 324个，这324个实际并不存在，但是这个数字和上一层所剩的叶子节点有直接关系，是上一层叶子结点的2倍5。324 / 2 = 162个，也就是说有162个第9层的叶子结点。6。求和。162 + 188 = 350个，总共有350个叶子结点。此前计算有误，已改正。第二题解答我的解答方法我自己非常习惯，需要你记住的是，要会分段，如何来分？有几个方法。一、前序的开头第一个就是根。二、在前序中排后，中序中排前，中序中排前的部分肯定是左子树三、在前序中排后，中序中排后，中序中排后的部分肯定是右子树1。根据前序中序的排列，很容易将访问序列分两段，步骤1所示。注意两段的部分要么都在前半部分，要么都在后半部分，绝对不是平分。2。确定根a，步骤23。步骤3中所示bdg和dgb，注意位置变化的部分，只有b，符合第二种情况，前序中的bdg说明b是a中左子树的根；中序中的dgb，说明dg是b的左子树，因为位置在b的前面。4。步骤4中，所示，前序和中序都是dg，符合第二种情况，所以g是d的右子树。5。做成图步骤5。6。步骤6中，将a的右子树部分继续分段，从前序判断右子树的根是c。7。步骤7中，根据ce和ec的顺序判断出e是c的左子树。8。步骤9中，道理与步骤7相同。
