请教:2012年3月全国计算机等级《二级C语言》模拟试题(7)第1大题第1小题如何解答?

Question

【题目描述】

对下列二叉树进行中序遍历的结果是（　　）。

A)ABCDEFGH

B)ABDGEHCF

C)GDBEHACF

D)GDHEBFCA

【我提交的答案】： B

【参考答案与解析】：

正确答案：C

答案分析：

遍历就是不重复地访问二叉树的所有结点。二叉树遍历的方法有3种：前序遍历、中序遍历和后序遍历。记住3种遍历的顺序：①前序，访问根一按前序遍历左子树一按前序遍历右子树。②中序，按中序遍历左子树一访问根一按中序遍历右子树。③后序，按后序遍历左子树一按后序遍历右子树->访问根。所以对该二叉树的中序遍历结果为GDBEHACF。

【我的疑问】（如下，请求专家帮助解答）

前序，中序，后序，到底怎样？？举个例子

Answer 1

若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf,则其后序遍历的节点访问顺序是

A．bdgcefha  
B．gdbecfha  
C．bdgaechf  
D．gdbehlca

a为根，dgb为左子树,echf为右子树
接下来看左子树的前序遍历为bdg
b首先被访问
可以知道b为左子树的根，与a相连
再看左子树的中序遍历dgb
d和g都在b之前就被访问
所以b和g应该在b的左子树上
形状如下
---a
--/
--b
-/
dg
而dg的确定再根据前序遍历
d先被访问
则d为根
再看中序遍历也是d先被访问
可以确定g为d的右子树
左边就可以确定出来了
如果上面看懂了
右边就很简单，一样的道理
前序遍历cefh
确定c为右子树的根
再看中序遍历echf
e为c的左子树，hf为c的右子树
hf的确定在看前序遍历f先被访问
f为根
中序遍历h先被访问
h为f的左子树
整棵树就出来了
如下图
在做后序就是小菜一碟了