题目
已知二叉树[1]的后序序列和中序序列分别是DCBFHGEA 和BCDAFEHG ( 1 ) 画出该二叉树。 ( 2 ) 写出该二叉树的前序序列。
已知二叉树[1]的后序序列和中序序列分别是DCBFHGEA 和BCDAFEHG
( 1 ) 画出该二叉树。
( 2 ) 写出该二叉树的前序序列。
题目解答
答案
（1）根据题目已知：
首先，根据后序序列和中序序列，确定根节点为A，中序序列分为左子树BCD和右子树FEHG。再对左子树BCD进行递归，后序序列为DCB，中序序列为BCD，确定根节点为D，左子树为空，右子树为CB。
最后，对右子树FEHG进行递归，后序序列为HGFE，中序序列为FEHG，确定根节点为H，左子树为FE，右子树为空。由于后序序列的顺序是左右根，所以最终的二叉树为：
```
A
/ \
B C
/ \
D E
/ \
F G
/
H
```
（2）根据前序遍历的定义，先输出根节点A，再递归输出左子树BCD和右子树FEHG，因此该二叉树的前序序列为：ABCFDEGH。
解析
步骤 1：确定根节点
根据后序序列DCBFHGEA，最后一个节点A是根节点。根据中序序列BCDAFEHG，根节点A将序列分为左子树BCD和右子树FEHG。
步骤 2：构建左子树
在后序序列中，左子树的后序序列为DCB，中序序列为BCD。根据后序序列，最后一个节点B是左子树的根节点。根据中序序列，B将序列分为左子树C和右子树D。因此，左子树的结构为B(C, D)。
步骤 3：构建右子树
在后序序列中，右子树的后序序列为HGFE，中序序列为FEHG。根据后序序列，最后一个节点H是右子树的根节点。根据中序序列，H将序列分为左子树FE和右子树空。因此，右子树的结构为H(F, E)。
步骤 4：组合左右子树
将左子树B(C, D)和右子树H(F, E)组合到根节点A上，得到完整的二叉树结构。
步骤 5：写出前序序列
前序遍历的顺序是根节点、左子树、右子树。根据构建的二叉树结构，前序序列为ABCFDEGH。
根据后序序列DCBFHGEA，最后一个节点A是根节点。根据中序序列BCDAFEHG，根节点A将序列分为左子树BCD和右子树FEHG。
步骤 2：构建左子树
在后序序列中，左子树的后序序列为DCB，中序序列为BCD。根据后序序列，最后一个节点B是左子树的根节点。根据中序序列，B将序列分为左子树C和右子树D。因此，左子树的结构为B(C, D)。
步骤 3：构建右子树
在后序序列中，右子树的后序序列为HGFE，中序序列为FEHG。根据后序序列，最后一个节点H是右子树的根节点。根据中序序列，H将序列分为左子树FE和右子树空。因此，右子树的结构为H(F, E)。
步骤 4：组合左右子树
将左子树B(C, D)和右子树H(F, E)组合到根节点A上，得到完整的二叉树结构。
步骤 5：写出前序序列
前序遍历的顺序是根节点、左子树、右子树。根据构建的二叉树结构，前序序列为ABCFDEGH。