题17

题17

题目

【2019 统考真题】若将一棵树 转化为对应的二叉树 BT,则下列对 BT 的遍历中, 其遍历序列与 的后根遍历序列相同的是 ( ).
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历

分析

树的后根遍历也就是对应的二叉树的中序遍历

解

B
后根遍历树可分为两步: ①从左到右访问双亲结点的每个孩子 (转化为二叉树后, 先访问根结点, 再访问右子树);
②访问完所有孩子后再访问它们的双亲结点 (转化为二叉树后, 先访问左子树, 再访问根结点), 因此树的后根遍历序列与其相应二叉树的中序遍历序列相同。
对于此类题,采用特殊值法求解通常会更便捷,左下图树 转换为二叉树 BT 的过程如下图所示, 树的后序遍历序列显然和其相应二叉树的中序遍历序列相同, 均为 。