问题 单项选择题

树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转换得到的二叉树叫做这棵树对应的二叉树。结论 (27) 是正确的。

A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同

C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D.以上都不对

答案

参考答案:A

解析:[分析]
本题考查树的遍历和树向二叉树的转换。
树的遍历方法中的前序遍历是首先访问根结点,然后从左到右按前序遍历根结点的各棵子树;后序遍历是首先从左到右按后序遍历根结点的各棵子树,然后访问根结点。而二叉树的遍历方法中前序遍历是首先访问根结点,然后按前序遍历根结点的左子树,再按前序遍历根结点的右子树;后序遍历是首先按后序遍历根结点的左子树,然后按后序遍历根结点的右子树,再访问根结点;中序遍历是首先按中序遍历根结点的左子树,然后访问根结点,再按中序遍历根结点的右子树。
树的转换思想是根据孩子的存储方式而来的,其步骤是:
(1)在各兄弟结点之间用虚线相连;
(2)对每个结点仅保留它与其最左一个孩子的连线,抹去该结点与其他孩子之间的连线;
(3)把虚线改为实线从水平方向向下旋转45℃,成右斜下方向,原树中实线成左斜下方向。
下面,我们来看一个例子,图A是一棵普通树,图B是其转换来的二叉树。
[*]
图A的前序遍历为:A,B,E,C,F,H,G,D
图A的后序遍历为:E,B,H,F,G,C,D,A
图B的前序遍历为:A,B,E,C,F,H,G,D
图B的中序遍历为:E,B,H,F,G,C,D,A
图B的后序遍历为:E,H,G,F,D,C,B,A
由此可见,树的前序遍历序列与其对应的二叉树的前序遍历序列相同。

单项选择题
问答题 简答题