(53)已知二叉树后序遍历序列是dabec,中序遍历序列是d-查字典问答网

来自房朝晖的问题

　　(53)已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是______.A.cedbaB.acb

1回答

2020-09-0315:47

我要回答

提示：回答问题需要登录哦！

万毅

　　（53）[答案]A

　　[考点]数据结构与算法

　　[评析]

　　后序又叫后根,一次递归过程是先左再右最后根；中序是先左再根最后右.

　　比如下图：

　　前序是：abc

　　中序是：bac

　　后序是：bca

　　题中据后序遍历序列,一眼得知c结点是根,那么据中序deba结点都在一边,或都在根结点左边,或右边；据中序遍历序列得知全在根结点的左边.

　　接下来据后序得出e结点是紧挨着c结点的左子女,再据中序得知d是e的左子女,ba是右子树.

　　再据后序得b是e的右子女,再据中序得a是b的右子女.

　　分析结果得二叉树图示如下：

　　因为我数据结构是自学的,分析此类型的题我都是用自己的方法（递归分析的方法）,要边分析边画图,一步一步连结起来,最后再根据题中的遍历检查图是否画对,如果都符合题目,最后再可根据图来得所求的遍历.

　　再次声明,此所有二级公基题全是我一人的思路写的,如果你觉得不可靠,可以看其它的书.

2020-09-03 15:49:23

大家都在问