问答题 对于二叉树T的两个结点N1和N2,我们应该选择树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先,并给出判断的方法。不需证明判断方法的正确性。【复旦大学1999五(10分)】
【正确答案】正确答案:采用前序和后序两个序列来判断二叉树上结点n1必定是结点n2的祖先。在前序序列中某结点的祖先都排在其前。若结点n1是n2的祖先,则n1必在n2之前。而在后序序列中,某结点的祖先排在其后,即若结点n1是n2的祖先,则n1必在n2之后。根据这条规则来判断若结点n1在前序序列中在n2之前,在后序序列中又在n2之后,则它必是结点n2的祖先。对本题的解答还可以参见上面第59题。
【答案解析】