如何根据后序遍历和中序遍历建立二叉树

#include

#include

#include

#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、访问根结点。

注意的是：遍历左右子树时仍然采用后序遍历方法。 

前序遍历:1 2 4 8 9 10 11 5 3 6 7 (规律：根在前；子树在根后且左子树比右子树靠前)；

中序遍历: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. 由右子树的后序序列和中序序列建立右子树。
另外,站长团上有产品团购,便宜有保证