已知一棵二叉树的先序序列是 ABCDEFGH，中序序列是BDCEAFHG ，则其后序序列为。

1个回答

雪峰教育

专业答主服务有保障

关注

展开全部

摘要亲亲,很高兴为您解答哦

可以利用二叉树的遍历规律来求解，后序遍历的顺序是：左子树-右子树-根节点。我们先分析出根节点在前序遍历序列中的位置，由于先序遍历的第一个结点为根节点，即 A 为根节点。然后我们在中序遍历序列中定位出根节点的位置，BDCE为根节点的左子树，FGH为根节点的右子树，所以中序遍历顺序是 BDCEAFHG。接下来，我们就可以分别对左子树和右子树使用同样的方法递归求得它们的后序遍历序列。那么这棵二叉树的后序遍历为 DECBHGFA。

咨询记录 · 回答于2023-05-10

已知一棵二叉树的先序序列是 ABCDEFGH，中序序列是BDCEAFHG ，则其后序序列为。

亲亲,很高兴为您解答哦

亲亲相关拓展：已知一棵二叉树的先序序列是 ABCDEFGH，中序序列是 BDCEAFHG ，则其后序序列为 DECBHGFA。我们先找到后序序列中的根节点，由后序遍历的规律可以知道，根节点在后序遍历序列中一定是最后一个，即为H。接下来，我们需要在中序遍历序列中定位出根节点的位置，由于中序遍历的顺序是左子树-根节点-右子树，所以，BDCE为根节点的左子树，AFHG为根节点的右子树。然后，我们可以根据中序遍历序列中根节点的位置，将前序和中序遍历分别分成左子树和右子树两个结构，再递归处理，直到只有一个结点为止。对于当前的这颗子树，在中序遍历时是在根节点的左子树，前序遍历的第一个非根节点元素是B，因此左子树的根节点是B，递归进入到左子树的处理过程中。在左子树的处理中，后序遍历最后比较的是左子树的的结尾序列，由于左子树是BDCE，后序遍历序列中的这部分是ECDB，即左子树的后序序列，这也是符合后序遍历的规律的。同样的操作递归进入到右子树的处理过程中，最终可得后序遍历序列为DECBHGFA。