二叉树的先序序列为ABDGCEF 中序序列为DGBAECF 则其后序序列是___________。
已帮助 人
二叉树的先序序列为ABDGCEF，中序序列为DGBAECF，则其后序序列是___________。
A．ABDGCEF
B．GDBEFCA
C．DGBAECF
D．FGEBDCA
回答
共1条回复-
B 树的一种遍历序列是无法确定二叉树的具体形态的。而根据二叉树的先序遍历序列和中序遍历序列是可以唯一确定一棵二叉树的。本题我们可以利用排除法，对每个答案进行检验，最后得到答案。A：根据先序遍历序列，A是二叉树的根结点。根据选项，则二叉树的形态一定如图4—3所示。但如果这样，那么此二叉树的先序遍历序列一定为AC×××××，这与题设矛盾，因此排除A。B：根据先序遍历序列，A是二叉树的根结点。根据选项，则二叉树的形态一定如图4—4所示。我们接着对A的右子树进行考虑。对于BCDEFG组成的二叉树，根据题设的先序遍历序列，去除结点A，有BCDEFG，可见B是根结点，且二叉树的形态一定如图4—5所示。然后再对B的右子树进行考虑。对于CDEFG组成的二叉树，根据题设的先序遍历序列，去除结点A和B，有CDEFG，可见C是根结点，且二叉树的形态一定如图4—6所示。依此类推，可以得到由题设和选项B所确定的二叉树，如图4—7所示。C：根据先序遍历序列，A是二叉树的根结点。根据选项，则二叉树的形态一定如图4—8所示。但如果这样，那么此二叉树的先序遍历序列一定为AD×××××，这与题设矛盾，因此排除C。D：B结点未被访问到，不符合二叉树遍历的定义，因此排除D。因此本题的答案为B。