求一个2叉树解题步骤已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为A)GEDHFBCAB)DGEBHFCAC)ABCDEFGHD)ACBFEDHG

Question

求一个2叉树解题步骤
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为
A) GEDHFBCA B) DGEBHFCA
C) ABCDEFGH D) ACBFEDHG

Answer 1

前序遍历：根、左、右
中序遍历：左、根、右
后序遍历：左、右、根
步骤：
1、由前序遍历ABDEGCFH可知根为A
2、由中序遍历DBGEACHF可知DBGE为A左树,CHF为A右树
3、A左树DBGE在前序遍历中的排列为BDEG,可知B为A左树的根、D在B根之左、GE在B根之右；前序遍历中为EG中序遍历为GE,可知E为根、G为E根之左
4、A右树CHF在前序遍历中的排列为CFH,可知C为A右树的根、HF在C根之右；前序遍历中为FH中序遍历为HF,可知F为根、H为F根之左
由上则可画出二叉树：
A
B C
D E F
G H
根据后序遍历：左、右、根
知DGEBHFCA,选B
其实,不必如此麻烦,用排除法即可.
由1知根为A,排除C、D；由2知DBGE在左,排除A；可知选B