设一棵二叉树的中序遍历结果为ABCDEFG，前序遍历结果为DBACFEG，则后序遍历结果为______。

admin2010-12-16 66

问题设一棵二叉树的中序遍历结果为ABCDEFG，前序遍历结果为DBACFEG，则后序遍历结果为______。

选项

答案ACBEGFD

解析由于在前序遍历中首先访问根结点，因此，前序序列中的第一个结点为二叉树的根结点，即D为二叉树的根结点。又由于在中序遍历中访问根结点的次序为居中，而访问左子树上的结点为居先，访问右子树上的结点为最后，因此，在中序序列中，以根结点(D)为分界线，前面的子序列(ABC)一定在左子树中，后面的子序列(EFG)一定在右子树中。同样的道理，对于已经划分出的每一个子序列的所有结点中，位于前序序列最前面的一个结点为子树的根结点，而在中序序列中位于该根结点前面的结点构成左子树上的结点子序列，位于该根结点后面的结点构成右子树上的结点子序列。这个处理过程直到所有子序列为空为止。
根据上述道理，该二叉树恢复的过程如下图所示：

根据后序遍历的方法，对该二叉树后序遍历的结果为ACBEGFD。

转载请注明原文地址:https://kaotiyun.com/show/SLVp777K

本试题收录于：二级C题库NCRE全国计算机二级分类

二级C

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

设一棵二叉树的中序遍历结果为ABCDEFG，前序遍历结果为DBACFEG，则后序遍历结果为______。

二级C

NCRE全国计算机二级

关于switch语句的叙述正确的是()。

下列定义变量的语句中错误的是()。

下面结构体的定义语句中，错误的是（）。

若变量已正确定义并赋初值，以下合法的赋值语句是

某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的深度（根结点在第1层）为

在单链表中，增加头结点的目的是()。

儿童手的动作日益灵活，其中最重要的是五指分工动作开始发展，这是()阶段的特点。

下述CT表现中，提示为脑外肿瘤的征象是

下列有关原始玻璃体增生症描述正确的是

患者，男，34岁。右上齿痛半年，隐隐作痛，时作时止，脉沉。针灸治疗在合谷、颊车、下关的基础上，应加取

脏腑湿热证的共同特点是

根据《中华人民共和国证券投资基金法》的规定，中国基金业协会的权力机构是()。

幼儿常把没有发生的或期望的事情当做真实的事情，这说明幼儿()

巴黎画派注重意境创造和抒情性，以__________为代表。

1845年，马克思、恩格斯合作编写的第一次比较系统地阐述历史唯物主义基本原理的著作是()