假定只有四个结点A、B、C、D的二叉树，其前序遍历序列为ABCD，则下面哪个序列是不可能的中序遍历序列？ ​

根据二叉树的前序遍历和中序遍历的性质，可以确定根节点为A。因此，可以列出每个节点的左右子树：

A
/ \
B C
/
D

根据中序遍历的性质，对于任意一个节点，它的左子树的所有节点都在它的左边，右子树的所有节点都在它的右边。因此，中序遍历的结果必须满足以下条件：

1. B必须在A的左边。
2. D必须在C的左边。
3. C必须在A的右边。

因此，下面不可能的中序遍历序列是：ACBD。

相关问题

设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为

根据前序遍历序列的第一个元素可以确定该二叉树的根节点，即C。而根据中序遍历序列，C的左侧元素A和B应该位于C的左子树中，C的右侧元素D应该位于C的右子树中。因此，该二叉树的结构如下：

   C
 /   \
A     D
     /
    B

接下来考虑如何构造后序遍历序列。后序遍历是先遍历左子树，再遍历右子树，最后遍历根节点。因此，该二叉树的后序遍历序列应为：ABDC。

已知二叉树的前序遍历序列为ABDCEFG,中序遍历序列是DBCAFEG,则其后序遍历序列为

根据二叉树遍历的性质，先求出二叉树的左右子树分布情况：

前序遍历：A B D C E F G
中序遍历：D B C A F E G

可以看出，根节点为A，因此左子树的前序遍历为B D，中序遍历为D B，右子树的前序遍历为C E F G，中序遍历为F E G。

将左右子树分别递归求解，直到子树为空，此时对应的后序遍历序列即为：

左子树的后序遍历序列：D B
右子树的后序遍历序列：F E G C
根节点的后序遍历序列：A

因此，整个二叉树的后序遍历序列为：DBFEGCA。