C语言试题：二叉树遍历

试题内容

设二叉树的中序序列为BCDA, 前序序列为ABCD, 则后序序列为()。

〖A〗CBDA

〖B〗CDBA

〖C〗BCDA

〖D〗ACDB

试题解读

‌中序遍历（In-order Traversal）‌：首先遍历左子树，然后访问根节点，最后遍历右子树。对于给定的中序序列 BCDA，我们可以知道根节点 A 位于最后，意味着 BCD 是 A 的左子树中的节点。

‌前序遍历（Pre-order Traversal）‌：首先访问根节点，然后遍历左子树，最后遍历右子树。对于给定的前序序列 ABCD，我们知道 A 是根节点，且 BCD 是它的子节点（由中序遍历知是左子节点）。接下来，B 在前序遍历中紧随 A 之后，所以 B 是 A 的左子节点。CD 则是 B 的子节点，但具体 C 和 D 的关系需要通过中序遍历来确定。

‌构建二叉树‌：

根节点是 A。

B 是 A 的左子节点。

在中序遍历 BCDA 中，C 位于 B 之后，D 之前，所以 C 是 B 的左子节点，D 是 B 的右子节点。

因此，构建的二叉树结构如下：

text

A

/

B

/ \

C   D

‌后序遍历（Post-order Traversal）‌：首先遍历左子树，然后遍历右子树，最后访问根节点。

遍历左子树（B）：先遍历 C（左子节点，没有子节点），然后遍历 D（右子节点，没有子节点），最后访问 B。

遍历完左子树后，最后访问根节点 A。

所以，后序遍历的顺序为 CDBA。

综上，二叉树的后序序列为 CDBA。