Question

二叉树的遍历

二叉树的遍历前序：ABCDEFG
中序：CBDAFGE
求后序。我求出的后序答案是CDBGFEA。但是画出二叉树后在看中序，我得到的跟题不一样的答案。麻烦大神讲解一下中序后序怎么遍历，每次都不一样。

Answer 1

前序：ABCDEFG

中序：CBDAFGE

先来画二叉树。前序中第一个必定是根，那么A必定是根。

再看中序,既然A是根，那么CBD在A左边，必定是A的左子树。

FGE在A的右边必定是A的右子树。

在分别看CBD 和 FGE

前序：BCD  那么B必定是左子树的根。

而中序：CBD，C必定在B左边，D必定在B右边。所以左子树你画对的。

而右子树。前序：EFG。E必定是右子树的根。

而中序：FGE，意思是F、G都在E的左边。为确定FG的位置关系，

前序：FG  中序FG。也就是说G应该是F的左子树

简而言之，你二叉树画错了。

根据图在看后序，即是CDBGFEA

不管有多复杂的树，你可以根据上面的步骤，分块分步地画出整个二叉树。