如何根据后序遍历和中序遍历建立二叉树
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 100
typedef char ElemType;
//声明二叉树结构体
typedef struct node
{
ElemType data;
struct node *lchild,*rchild;
}BitTree;
BitTree *createBinTreeByPostIn(char *post,char *in,int number)
{
if(number==0) return NULL;
char c = post[number-1];
int i = 0;
while(in[i]!=c && i < number)i++;
int leftNumber = i;
int rightNumber = number - i - 1;
BitTree *node = (BitTree *)malloc(sizeof(BitTree));
node->data = c;
node->lchild = createBinTreeByPostIn(&post[0],&in[0],leftNumber);
node->rchild = createBinTreeByPostIn(&post[leftNumber],&in[i+1],rightNumber);
return node;
}
void PreOrder(BitTree *bt)
{
if(bt!=NULL)
{
printf("%c ",bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
int main(int argc,char **argv)
{
char a[SIZE],b[SIZE];
BitTree *p;
while(scanf("%s%s",a,b)!=EOF)
{
p = createBinTreeByPostIn(a,b,strlen(a));
PreOrder(p);
printf("\n");
}
return 0;
}
扩展资料：
注意事项
一、中序遍历（LDR）
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
1、中序遍历左子树
2、访问根结点
3、中序遍历右子树。
注意的是：遍历左右子树时仍然采用中序遍历方法。
二、后序遍历（LRD）后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：
若二叉树为空则结束返回，否则：
1、后序遍历左子树。
2、后序遍历右子树。
3、访问根结点。
注意的是：遍历左右子树时仍然采用后序遍历方法。
中序遍历:8 4 10 9 11 2 5 1 6 3 7 (规律：根在中；左子树在跟左边，右子树在根右边)；
后序遍历:8 10 11 9 4 5 2 6 7 3 1 (规律：根在后；子树在根前且左子树比右子树靠前)；
其它例子：
前序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA
前序遍历:1 2 4 3 5 7 6
中序遍历:2 4 1 5 7 3 6
后序遍历:4 2 7 5 6 3 1
做类似的题目，你可以先由两个遍历画出二叉树。通过形象的二叉树来写出另一个遍历，写的方法如上（递归）。画出二叉树的方法如下：
已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。
已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。
另外,站长团上有产品团购,便宜有保证
这个我知道，我要的是递归条件。而且我已经解决了。
