Skip to content

2019年 408 数据结构 第 2 题

数据结构2019年选择题2分

题目

若将一棵树 T 转化为对应的二叉树 BT,则下列对 BT 的遍历中,其遍历序列与 T 的后根遍历序列相同的是( )。

错因

A

把"后根 → 先序"配错对了。背诵时只记得"树的根序遍历对应二叉树的先序"这条结论,忽略了"先根"和"后根"是两条独立的对应规则——题目问的是后根,不能套先根的结论。

C

凭名字直接对照。看到"后根"就联想"后序",按字面相似度选答案。但在"左孩子右兄弟"转换下,原树根节点最后访问的位置在二叉树里落到了中序的根访问点,而不是后序的根访问点,单纯对名字推不出结论。

D

按层遍历是非递归的迭代访问,与原树"先所有子树后根"的递归性质完全不同范畴。两者结果除非平凡情形(单节点)一般都不相等。

总解析

树→二叉树规则("左孩子右兄弟"):

  • 节点 v 在原树中的最左孩子 → 二叉树中作为 v 的左孩子
  • v 的兄弟(按从左到右顺序)→ 顺次接在左孩子的右孩子链上

由此得到两条对应关系:

原树遍历转换后二叉树遍历
先根遍历先序遍历
后根遍历中序遍历

直观推导:在二叉树里中序遍历到节点 v 时,先递归遍历 v 的左子树(在原树里就是 v 的全部子树——因为 v 的所有孩子在二叉树中通过"左孩子+右兄弟链"挂在 v 的左子树下),再访问 v 自己。这正好与原树后根"先所有子树、后访问根"的次序一致。

最终答案是 B

最后更新:

🎬 可视化演示
加载中...

提示:可在可视化区直接操作播放、步进、修改参数