知树的前序遍历，后序遍历，怎么求中序遍历

已知前序遍历和后序遍历，怎么求可能的中序遍历~

仅供参考，
int creat(BiTree &T, ElemType pre[],ElemType post[],int low_x,int high_x,int low_h,int high_h)
{//根据先序序列和后序序列建立二叉链表，先序序列和后序序列存于一维数组中，四个整型变量表示数组的范围,0号单元留空，函数返回可建立二叉树的数目
count=1;
if(low_x>high_x || low_h >high_h) {T==NULL;return count;}
if(low_x high_h])
{
T=new BiNode;
T->data=pre.elem[low_x];
}
if(low_x+1= low_h)
{
if(pre [low_x+1] ! = post [high_h-1])
{
顺序查找pre [low_x+1]在后序序列的位置a；
顺序查找post [high_h-1]在先序序列的位置b；
creat(T->lchild,pre,post,low_x+1,b-1,low_h,a);
creat(T->rchild,pre,post,b,high_x,a+1,high_h-1);
}
else if(pre [low_x+1] = = post [high_h-1])
{
count*=2;
请选择建立左子树或右子树，左输入0，右输入1，用L_R表示
cin>>L_R;
if(L_R= =0)
{
creat(T->lchild,pre,post,low_x+1,high_x,low_h,high_h-1);
creat(T->rchild,pre,post,1,0,1,0);
else {
creat(T->lchild,pre,post,1,0,1,0);
creat(T->rchild,pre,post,low_x+1,high_x,low_h,high_h-1);
}
}
if (low_x+1> high_x || high_h-1 < low_h)
{
creat(T->lchild,pre,post,1,0,1,0);
creat(T->rchild,pre,post, 1,0,1,0);
}
}

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

通过对同一棵二叉树三种遍历方式的分析，概括出由前序、中序或由中序、后序遍历结果快速还原二叉树的方法。�
二叉树是最为常用的数据结构，它的实际应用非常广泛。二叉树的遍历方式有三种，前序遍历、中序遍历、后序遍历。先序遍历的顺序为：NLR，即先根结点，然后左子树、右子树；中序遍历顺序为：LNR先左子树，然后根结点、右子树；后序遍历顺序为：LRN先左子树、然后右子树、根结点。由前序和中序遍历、由中序和后序遍历序列可以唯一确定一棵二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树。�
二叉排序树对二叉树作了进一步的限定：根结点的权值大于（或小于）左子树中所有结点的权值；根结点的权值小于（或大于）其右子树中所有结点的权值。�
那么如何根据三种遍历序列之间的关系及二叉排序树来快速还原一棵二叉树？下面以二叉树的前序和中序遍历序列为基础，利用二叉排序树的性质，给出快速还原二叉树的方法。�
1由给定前序和中序序列或中序和后序序列还原二叉树的方法�
例：前序序列：ABDECFGH 中序序列：DEBACGFH （后序序列：EDBGHFCA）�
（1）给中序序列中的每个结点从小到大、从左到右赋以权值，如下：�
D（1）E（2）B（3）A（4）C（5）G（6）F（7）H（8）�
（2）还原时读入的序列为前序序列，从左到右依次读入序列中的各个结点值和相应的权值； �

（3）由读入的序列，根据第1）步中给定的权值按照二叉排序树的构造规则构造二叉排序树。第一个读入的结点为根结点，其他结点分别为左右子树中的结点。设根结点为TT，权值为NN，当前读入结点为SS，权值为MM，若MM
（4）将SS插入到TT的左子树或右子树的过程中，仍然遵循3）中的规则，直至左子树或右子树为空时止。�
（5）读入序列结束时，二叉树还原成功。�

6）对于由中序序列和后序序列还原二叉树是，读入的序列为后序序列，从右向左读入，构造规则同上。还原结果与上述结果完全一致。�

2还原方法的确定依据�
二叉树遍历过程中，在中序序列中，根结点的左子树中的所有结点都在根结点的左侧，根结点的右子树中的所有结点都在根结点的右侧，这个特点恰好与二叉排序树具有相同的性质；在读入序列时，前序序列则从左向右读，这恰好与遍历二叉树的顺序相同；后序序列从右向左读，则按照根结点、右子树、左子树的顺序还原。�
（1）设二叉树共有N个结点（N为大于1的正整数），我们按照还原方法给中序序列中的这N个结点分别赋予权值1,2…N，设根结点的权值为M（1
（2）由二叉树的遍历规则可知，权值为1,2…M-1的结点为根结点的左子树中的结点，而权值为M+1,…N的结点为根结点的右子树中的结点。�
（3）将这N个结点划分成3个子集AA＝（1,2…M-1）BB＝（M）CC＝（M+1,…N），由于前序序列第一个读入的结点必定为二叉根的根结点，所以BB为根结点，AA集为左子树，CC集为右子树。�
（4）同理不断读入前序序列中的结点，依次递归还原BB对应的左子树和CC对应的右子树，最后将三棵子树合并成以BB为根结点、AA的根结点为BB的左子树、CC的根结点为BB的右子树的一棵二叉排序树。�
（5）同理可以得出，由中序序列和后序序还原二叉树的规则也成立。�
（6）在还原过程中，读入序列的顺序也遵循也先根结点，后子树的规律。�
3总结�
在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。

上面说的是二叉树，树只有先根和后根，没有中序，森林只要先序中序，没有后序

1) 先序遍历：
先访问根结点，再先序遍历左子树，最后再先序遍历右子树。
2) 中序遍历：
先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树。
3) 后序遍历：
先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点。

---

平江县17737413606： 树的先序遍历,中序遍历,后序遍历 - ？
寸冯利分： 先序就是根结点在开始位置展开全部在经过其结点时,就将它进行遍历 中序就是根结点在中间位置在遍历完它所有的左孩子时,将它进行遍历 后序就是根结点在最后位置在遍历完它所有的(左右)孩子时,将它进行遍历

平江县17737413606： 知树的前序遍历,后序遍历,怎么求中序遍历 - ？
寸冯利分： 通过对同一棵二叉树三种遍历方式的分析,概括出由前序、中序或由中序、后序遍历结果快速还原二叉树的方法.إ 二叉树是最为常用的数据结构,它的实际应用非常广泛.二叉树的遍历方式有三种,前序遍历、中序遍历、后序遍历.先序遍历...

平江县17737413606： 已知二叉树的前序和后序遍历,怎么求中序遍历 - ？
寸冯利分： 前序遍历的简称为VLR(根结点-左子树-右子树),序为LVR,可以看到最后一个相同,于是我们同位相同的为R(右子树)其它位按组合逻辑取反.我一般用自创撇捺形象图,就是画出撇捺的走势,比如一前序为ABCDEF,中序为CBEDFA,后序就为CEFDBA.

平江县17737413606： 已知二叉树前序遍历和后序遍历如何求中序遍历?如题,希望能够给出实例和说明. - ？
寸冯利分：[答案] TLR的第一个和LRT的最后一个一定是树根 TLR的第二个不是左子树的根就是右子树的根 如果TLR第二个与LRT的倒数第二个相同 则他是根的右子树 否则是根的左子树 将上面的方法递归

平江县17737413606： 二叉树的中序遍历和前序遍历知道怎样求后序遍历 - ？
寸冯利分： 从前序的第一个结点开始确定根,中序决定左子树和右子树,如第一个结点A,根据中序可知,A的左子树是DBE,右子树是FC,再从前序中确定第二个根B,根据中序可知B的左子树是D,右子树为E,依次重复执行,直到遍历完所有结点.所以后序遍历DEBFCA

平江县17737413606： 已知二叉树的前序遍历和中序遍历,怎样得到它的后序 - ？
寸冯利分： 1. 已知二叉树的前序遍历和中序遍历就可以知道二叉树的形状,然后即可得到它的后序序列.(方法一) 2. 已知二叉树的前序遍历和中序遍历 步骤一:从前序遍历序列中找到根结点(首结点) 步骤二:然后从中序序列中找到该节点的左右两个中序序列,取出该结点放置到两序列之后. 步骤三:针对划分后的两个中序序列重复步骤一和步骤二,直到中序序列无法再次划分.此时得到的序列即为后序序列.(方法二)

平江县17737413606： 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是什么? - ？
寸冯利分： 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA. 前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点.中序遍历的根节点前面的节点均为左子树的节点,所以左子树上...

平江县17737413606： 已知二叉树前序遍历和后序遍历如何求中序遍历? - ？
寸冯利分： TLR的第一个和LRT的最后一个一定是树根 TLR的第二个不是左子树的根就是右子树的根 如果TLR第二个与LRT的倒数第二个相同 则他是根的右子树 否则是根的左子树 将上面的方法递归

平江县17737413606： 已知二叉树的后序遍历序列和中序遍历序列,怎样求其前序遍历序列 - ？
寸冯利分： 首先理解概念: 前序遍历:访问根结点的操作发生在遍历其左右子树之前. 中序遍历:访问根结点的操作发生在遍历其左右子树之中(间). 后序遍历:访问根结点的操作发生在遍历其左右子树之后. eg:后序遍历为DBCEFGHA,中序遍历为EDCBAHFG,求前序遍历(网上例子) 解:首先 看后序遍历DBCEFGHA,A为总根节点然后 寻找中序遍历EDCBAHFG中A位置,则EDCB在A的左枝,HFG在A的右枝;重复前两步,从后序遍历最后一位找,在中序遍历寻找对应点,得出左右分枝...最后得到AECDBHGF,再自己验证即可...

平江县17737413606： 知道二叉树的前序和后序,问中序排列怎么排?有什么方法吗?希望有图 - ？
寸冯利分： 中序遍历的规则就是把根放在中间,从左到右.即左——根——右. 以下图为例: 则是先遍历左子树(即以B为根的子树),再遍历根结点,最后遍历右子树(以E为根结点的子树). 首先在遍历左子树(以B为根的子树)的时候,同样用中序...