bitree.c

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

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define MAXN 50
char b[MAXN],m[MAXN];       //b[]，m[]分别为存贮后序遍历结点序列，中序遍历结点序列的数组
struct node
{
	char data;
	struct node *lchild,*rchild;
};
typedef struct node NODE;
NODE *create(b,b_start,b_end,m,m_start,m_end)
//b_start,b_end分别为b[]的起始下标和结尾下标，m_start,m_end分别为m[]的起始下标和结尾下标
char b[MAXN],m[MAXN];
int b_start,b_end,m_start,m_end;
{
	NODE *r;
	int i,k;
    if(b_end>=b_start)               //建立树的结束标志
	{
		for(i=m_start;i<=m_end;i++)
		    if(m[i]==b[b_end])
			    k=i;
        r=(NODE *)malloc(sizeof(NODE));
        r->data=b[b_end];            
        r->lchild=create(b,b_start,b_end-m_end+k-1,m,m_start,k-1); //建立左子树
	    r->rchild=create(b,b_end-m_end+k,b_end-1,m,k+1,m_end); //建立右子树     
	}
	else return NULL;
	return r;
}
void r_preorder(t)
NODE *t;
{
	if(t!=NULL)
	{
		printf("%c",t->data);
		r_preorder(t->lchild);
		r_preorder(t->rchild);
	}
}
void main()
{
	NODE *root;
	int n,i;
	printf("Please input the array of backordered:");
	scanf("%s",b);
	printf("Please input the array of midordered:");
	scanf("%s",m);
	for(i=0;b[i]!='\0';i++);
	n=i;
	root=create(b,0,n-1,m,0,n-1);
	printf("The pre_order array is:");
	r_preorder(root);
	printf("\n");
}