关于C语言的一道题

来源：百度知道 编辑：UC知道 时间：2024/05/15 23:34:03
已经二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是?
A:acbed B:decab C:deabc D:cedba
知道的大侠说下解题过程哦,本人是菜鸟哦,说详细哦.谢谢.

这篇文章的高手写明了遍历的原则：
http://zhidao.baidu.com/question/11341640.html?si=5

------c
----e---
--d---b--
-------a

答案是c。

这题有个简单的算法，
后序遍历最后访问跟节点； 前序遍历最先访问根节点。
这是必然的。
所以，后序的最后一个 C ，前序的第一个也是C 。
答案只有D。

通过后序遍历 得知 头节点是 c (这个基本概念不用我给你讲了)

通过中序遍历得知，此树根节点没有右子树 （因为一般树中序遍历头节点应该在中间，但这里却在最右边）

用上述两个概念依次类推，得出树的结构

c
/
e
/\
d b
/\\
a

所以前序遍历为cedba

D