已知二叉树的中序遍历结果： BDCEAFHG。后序遍历结果：DECBHGFA,画出此二叉树？具体

发布网友发布时间：2022-05-10 18:30

我来回答

共4个回答

热心网友时间：2023-10-21 21:06

1、先求原始二叉树，后序遍历中最后出现的是根，所以A是整棵树的根，在结合中序遍历来看

BDCE是A的左子树，而FHG是A的右子树；

2、BDCE序列中B是整个序列根，因为后序遍历中B最后出现。此时再看中序中根B左端没有左子

树，右端有DCE,所以DCE是B的右子树；

3、再看D、C、E在后序遍历中C结点最后出现，所以C是根，此时再到中序遍历看可以看到C的左

端是D，右端是E，所以C的左子树是D，右子树是E；

4、再看F、H、G三个结点，后序遍历序列F最后出现，所以F是根结点，再回去看中序HG在F右

端，所以HG是F的右子树；

5、由于H、G在后序遍历序列G最后出现，所以G是H, G中的根，再看中序中G左端只有一个H，

所以H是G的左子树，得到最终原始二叉树。

需要注意的几点：

1、根是相对的，对于整棵树而言只有一个根，但对于每棵子树而言，又有自己的根。

2、前序遍历时，一棵树的根永远在左子树前面，左子树又永远在右子树前面。

3、二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序一样。

热心网友时间：2023-10-21 21:07

中序遍历按左子树、根结点、右子树的顺序；后序遍历按左子树、右子树、根结点的顺序。

后序结果中A最后访问，所以A是根结点，结合中序结果可知，BDCE则都在二叉树的左边。后序结果中DECB最后访问B，则B就是A的左子树；中序最先访问B，说明B没有左子树，只有右子树……总之结合中后序遍历的结果，依次递推即可得到如图的答案。不懂的可以再问我。

热心网友时间：2023-10-21 21:07

上面好像右子树画错了，根据已知的中序和后序，可以确定根结点A和左子树：BDCE右子树：FHG 然后再确定左子树的中序BDCE和后序DECB 确定左子树的根结点为B ，右子树的中序FHG后序HGF确定右子树根结点为F，再确定左子树的左子树及右子树的右子树这样递归下去直到所有的结点！
最后确定图为： A
/ \
B F
\ \
C G
/ \ /
D E H

热心网友时间：2023-10-21 21:08

先序遍历序列：ABCDEFGH