邪恶少女漫画飞机:这个二级基础知识怎么做啊

来源:百度文库 编辑:高校问答 时间:2024/05/04 05:39:34
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为
是怎么做的

这个是一个数据结构的题,
首先你需要懂得什么是二叉树
二叉树有一个根(结点),从跟上发展出左右两个枝,从每个枝(结点)又发展出左右两个枝,这种数据结构叫做二叉树。
二、二叉树的遍历
在二叉树的许多应用中,需要对其进行遍历操作,即系统地访问二叉树的每一个结点,并且每个结占只被访问一次。
遍历二叉树主要有三种方式:
1、前序遍历访问根结点;按先根次序遍历左子树;按先根次序遍历右子树。
2、中序遍历 按中根次序遍历左子树;访问根结点;按中根次序遍历右子树。
3、后序遍历 按所根次序遍历左子树;按后根次序遍历右子树;访问根结点
那么知道了这个我们就可以来分析这个题了。
首先根据前序遍历知道A为根,根据中序遍历我们知道DBGE是根的左枝的延伸。CHF为根的右枝延伸
那么我们可以确定了 A
/ \
B C
又根据中间遍历DB,所以D为B的左枝。根据前序遍历的BDEG的关系也就是说B的右枝有可能是E(当为E时G为其枝),也有可能G为B的右枝(此时E为D的枝),那根据中序遍历DBGE来分析。G可能为D的右枝,也可能为E的左作,根据两个分析可知,G为E的左枝叶,图为
A
/ \
B
/ \
D E
/
G
如此方法分析右面。得整个树为:
A
/ \
B C
/ \ \
D E F
/ /
G H

再根据他写出后序二叉树:DGEBHFCA