pre_mid_bitree.cpp

由二叉树的前序遍历结果与中序遍历结果来确定一棵二叉树。

#include<stdio.h>
#include<malloc.h>
#include<string.h>
struct node
{
	char data;
	struct node *lchild,*rchild;
};
typedef struct node NODE;
#define MAXN 50
char p[MAXN],m[MAXN];

NODE *create(char p[],char m[],int n)
{
	NODE *root;
	int posi;
	if(n<=0)return NULL;
	root=(NODE *)malloc(sizeof(NODE));
	root->data=p[0];
	for(posi=0;posi<n&&m[posi]!=root->data;posi++);
	root->lchild=create(p+1,m,posi);
	root->rchild=create(p+1+posi,m+posi+1,n-posi-1);
	return root;
}
void midorder(NODE *t)
{
	if(t!=NULL)
	{
		midorder(t->lchild);
		printf("%c",t->data);
		midorder(t->rchild);
	}
}
void main()
{
	NODE *root;
	int n,i;
	printf("Please input the array of preordered:");
	scanf("%s",p);
	printf("Please input the array of midordered:");
	scanf("%s",m);
	for(i=0;p[i]!='\0';i++);
	n=i;
	root=create(p,m,n);
	printf("The midorder array is:");
	midorder(root);
	printf("\n");
}