Question

已知二叉树的前序和后序遍历，怎么求中序遍历啊？

也就是求可以确定多少种树，高手指点一下啊，C或者C++代码也行啊！

Answer 1

按照自己的思路写的，仅供参考，
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<=high_x || high_h-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);
}
}

Answer 2

TLR的第一个和LRT的最后一个一定是树根
TLR的第二个不是左子树的根就是右子树的根
如果TLR第二个与LRT的倒数第二个相同
则他是根的右子树
否则是根的左子树
将上面的方法递归

Answer 3

#include<iostream>
using namespace std;

typedef struct BinaryTree
{
char data;
struct BinaryTree *lchild,*rchild;
}BinaryTree,*BiTree;

void CreateBiTree(BiTree &T)
{
char z;
if((z=getchar())==' ')
T=NULL;
else
{
T=(BinaryTree*)malloc(sizeof(BinaryTree));
T->data=z;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
//先序遍历
void preBiTree(BiTree T)
{
if(T!=NULL)
{
cout<<T->data;
preBiTree(T->lchild);
preBiTree(T->rchild);
}
}
//中序遍历
void InBiTree(BiTree T)
{
if(T!=NULL)
{
InBiTree(T->lchild);
cout<<T->data;
InBiTree(T->rchild);
}
}
//后序遍历
void PostBiTree(BiTree T)
{
if(T!=NULL)
{
PostBiTree(T->lchild);
PostBiTree(T->rchild);
cout<<T->data;
}
}
int Depth(BiTree T)
{
if(T==NULL)
{
return 0;
}
else
return 1+(Depth(T->lchild)>Depth(T->rchild)? Depth(T->lchild):Depth(T->rchild));
}

void main()
{
BiTree T;
cout<<"请输入相应二叉树:"<<endl;
CreateBiTree(T);
cout<<"二叉树的先序遍历为:"<<endl;
preBiTree(T);
cout<<endl;
cout<<"二叉树的中序遍历为:"<<endl;
InBiTree(T);
cout<<endl;
cout<<"二叉树的后序遍历为:"<<endl;
PostBiTree(T);
cout<<endl;
cout<<"二叉树的深度为:"<<endl;
cout<<Depth(T)<<endl;
}

Answer 4

前序遍历的简称为VLR（根结点－左子树－右子树），序为LVR，可以看到最后一个相同，于是我们同位相同的为R（右子树）其它位按组合逻辑取反。我一般用自创撇捺形象图，就是画出撇捺的走势，比如一前序为ABCDEF，中序为CBEDFA，后序就为CEFDBA。

Answer 5

知道前序后序 只能判断出祖先 不能确定树的结构
应该也就不能确定中序吧