已知二叉树后序遍历序列是dabec,中序遍历序列是debac,求他的前序...

发布网友发布时间：2024-10-03 14:59

共2个回答

热心网友时间：2024-10-19 08:38

这种题，主要考虑个节点的逻辑关系，先序遍历就是：根左右后序遍历就是：左右根，中序遍历就是：左根右。
抓住一个关键，例如本题中后序和中序第一个节点都是D，那么可以确定：D没有右子树，D本身是一个节点的左子树。中序遍历，D后面是E，说明D父节点是E，在草稿上画出来这个关系。在看中序遍历E后面是B，说明B是E的右子树，这样我们确定了3个节点了。再看中序的遍历B后的是A，但我们无法确定是左还是右，先放着，继续看后序遍历E后面是C，通过这个条件，说明C可能是E的父节点的右子树，也可能就是E的父节点，但是本题一共只有5个节点，所以C肯定是E的父节点。这样，我们可以确定4个节点了，这剩下A节点。要区分A是左还是右，我们看后序遍历，A是在D之后，B之前，这个条件也只能说A是B子节点，但仍然不能说明左右。所以我觉得：这道题有2个解：A在左在右，都是正确的。A是左是右，都符合后序和中序的遍历，都为正确。所以，只画这个图是不完整的，应该把A分别为左右节点的图都画出来，作为答案，A的位置不同，虽然先序遍历的结果都一样，但是图是不一样的。
----C
---/
--E
-/-\
D---B
-----\
------A

热心网友时间：2024-10-19 08:44

前序遍历：dabec
如图：
c
e
d b
a