Appearance
题目
若将一棵树 T 转化为对应的二叉树 BT,则下列对 BT 的遍历中,其遍历序列与 T 的后根遍历序列相同的是( )。
错因
A
把"后根 → 先序"配错对了。背诵时只记得"树的根序遍历对应二叉树的先序"这条结论,忽略了"先根"和"后根"是两条独立的对应规则——题目问的是后根,不能套先根的结论。
C
凭名字直接对照。看到"后根"就联想"后序",按字面相似度选答案。但在"左孩子右兄弟"转换下,原树根节点最后访问的位置在二叉树里落到了中序的根访问点,而不是后序的根访问点,单纯对名字推不出结论。
D
按层遍历是非递归的迭代访问,与原树"先所有子树后根"的递归性质完全不同范畴。两者结果除非平凡情形(单节点)一般都不相等。
总解析
树→二叉树规则("左孩子右兄弟"):
- 节点 v 在原树中的最左孩子 → 二叉树中作为 v 的左孩子
- v 的兄弟(按从左到右顺序)→ 顺次接在左孩子的右孩子链上
由此得到两条对应关系:
| 原树遍历 | 转换后二叉树遍历 |
|---|---|
| 先根遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 |
直观推导:在二叉树里中序遍历到节点 v 时,先递归遍历 v 的左子树(在原树里就是 v 的全部子树——因为 v 的所有孩子在二叉树中通过"左孩子+右兄弟链"挂在 v 的左子树下),再访问 v 自己。这正好与原树后根"先所有子树、后访问根"的次序一致。
最终答案是 B。