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