有一二叉树，中序遍历为DBAECF,前序遍历为ABDCEF，求后续遍历

数据结构二叉树，已知中序遍历、后序遍历，如何求先序遍历？~

Preorder遍历:访问根节点的操作发生在遍历左和右子树之前。
中间顺序遍历:访问根节点的操作发生在左边和右边的子树中。
顺序遍历:访问根节点的操作发生在遍历左边和右边的子树之后。
下面的序列遍历了DBCEFGHA，序列遍历是EDCBAHFG，以及preorder遍历(在线示例)
解决方案:首先，看到后序遍历DBCEFGHA, A是总根节点。
然后发现中间顺序遍历A在EDCBAHFG中的位置，然后在A的左分支上的EDCB，在A的右分支上的HFG;
重复前两个步骤，最后一个从后序遍历，在中间顺序遍历中搜索相应的点，以及左和右分支…
最后，AECDBHGF可以自行验证。

给定的信息不足够，无法推断出正确的遍历顺序。
只有在给出下列条件才能推算正确的遍历顺序：
1、给定前序与中序可以得到后序(还原二叉树)；
2、给定中序与后序可以得到前序(还原二叉树)；

注意：给出前序与后序是无法还原二叉树的。原理很简单，因为无法正确推导树根的左右孩子。

先给出结果吧，后序遍历为DBAEFC。解释有些麻烦，尽量能说得清楚一些吧。

前序遍历先访问根节点，然后前序遍历左子树，最后前序遍历右子树，这是一种递归的算法，由于第二步是前序遍历左子树，这样可以设想根节点的左子树还有一左子树，就会再先访问左子树的根节点，再前序遍历。中序遍历先中序遍历左子树，然后访问根节点，最后中序遍历右子树。

我们看到前序遍历的结果为ABDCEF，可以知道根节点是A，再看中序遍历的结果为DBAECF，可以看到根节点A在中间，两个节点DB肯定在根节点的左子树，节点ECF肯定在根节点的右子树。再看前序遍历的结果，根节点A后访问B（所以B肯定是D的根节点），最后是D，所以再看中序遍历（先中序遍历左子树），所以D是B的左子树。右子树部分也类推。很容易看到C是右子树的根节点（前序遍历先访问根节点），然后可推出E是左子树，F是右子树。

画了一幅图片，可能看图好理解一些

自己画几遍就清楚了 DBEFCA

---

江源县17686863879： 若某棵二叉树的后根遍历序列为DBEFCA,中根遍历序列为DBAECF,请画出这棵二叉树 - ？
才旦品金水： 后根遍历:DBEFCA 中根遍历:DBAECF 则还原二叉树如下:

江源县17686863879： 是的,是已知前序遍历和中序遍历,建立二叉树具体应该怎么办呢 - ？
才旦品金水： =可以采用二分法. 比如说先序遍历是ABDCEF 中序遍历是DBAECF 因为先序是中左右,所以先序遍历第一个必定是根节点,所以根节点是A 因为中序遍历是左中右,所以中序遍历的根节点的左子树必然在根节点前面,右子树必然在后面,也就是说 DB是A的左子树,ECF是右子树.这样就先建立A,然后开始二分. 以左右分别为一种情况,左子树先序是DB,中序是BD,所以B是D的左孩子,然后另一边也是一样,就可以得出C是A的右孩子,然后再以C二分.得出C的左孩子是E,右孩子是F,所以后续遍历就是DBEFCA. 无论如何复杂的二叉树都是用这种方法、

江源县17686863879： 一颗二叉树的先序遍历序列为:ABDCEFG,中遍历为:DBAECF,请画出这棵二叉树的逻辑结构,并给写出其后序遍历序列 - ？
才旦品金水： 结构图: AB C D E FG 后序遍历:DBEGFCA

江源县17686863879： 设一棵二叉树的中序遍历结果为DBEAFC,前序遍历的结果为ABDECF,则后序遍历结果为 - ？
才旦品金水： 依据前序遍历序列可确定根结点为A;再依据中序遍历序列可知其左子树由DBE构成,右子树为FC;又由左子树的前序遍历序列可知其根结点为B,由中序遍历序列可知其左子树为D,右子树由E构成...... 同理推算FC的排列顺序,在草稿纸上画出树的结构,再自己写写后序遍历吧!

江源县17686863879： 遍历序列的基本定义是什么? ？
才旦品金水： 2.遍历序列⑴中序序列中序遍历二叉树时,对结点的访问次序为中序序列【例】中序遍历上图所示的二叉树时,得到的中序序列为:DBAECF⑵先序序列先序遍历二叉树时,对结点的访问次序为先序序列【例】先序遍历上图所示的二叉树时,得到的先序序列为:ABDCEF⑶后序序列后序遍历二叉树时,对结点的访问次序为后序序列【例】后序遍历上图所示的二叉树时,得到的后序序列为:DBEFCA遍历注意⑴在搜索路线中,若访问结点均是第一次经过结点时进行的,则是前序遍历;若访问结点均是在第二次(或第三次)经过结点时进行的,则是中序遍历(或后序遍历)

江源县17686863879： 已知二叉树的中序遍历是DBEAFC.前序遍历是ABDECF.后序遍历怎么算? - ？
才旦品金水： 先理解前序和中序的涵义: 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树.在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树. 中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树.在遍历左...

江源县17686863879： 设一颗二叉树的中序遍历结果是DBEAFC,前序遍历结果是ABDECF,则后序便利结果是什么?？
才旦品金水： 这种题就是根据这两个序列画出对应的树. 前序遍历结果是ABDECF 中序遍历结果是DBEAFC 1.先看前序,那么最先遍历的就是A,因为是前根遍历,所以A就是最根的结点,也就是所说的root结点.(这要看懂,这个不懂理解就有点恼火) 2.先在确立了一个根A..那么现在去看中序遍历.中序是根是在遍历完左右子树再访问的根,所以DBE是A的左子树的结点.FC是A的右子树. 3.对于左子树的DBE结点.那么哪一个是根结点呢,现在就和步骤1一样.看前根中DBE中的哪个是最先出现的,那么它就是这三个结点的根.那么得出是B.然后找出B的左右子树分别是D和E.如此循环.就可以得出结果了.不明白再问.

江源县17686863879： 根据下图给出的二叉树,求出先序遍历、中序遍历和后序遍历的结点序列 a / \ b c / / d e \ f - ？
才旦品金水： 先序遍历abdcef 中序遍历dbaefc 后序遍历dbfeca 其实这种问题的解法很简单,你绕着二叉树从根节点左边画一条线绕过整个2叉树然后回到根节点,先序遍历就是线经过左边的时候的顺序,中序遍历就是线经过下面的时候的顺序,后续遍历就是经过右边的时候的顺序,掌握方法了终身都不用问别人了!见下图

江源县17686863879： 设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为多少? - ？
才旦品金水： 其实很简单,看前序遍历结果,A肯定是树根,那么从中绪来看,以A为中点,可以分为左右子树,依次类推,结合前、中序的队列,最后可得其后续遍历:DEBFCA