4_11.c

《数据结构-使用C语言》第三版

#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define Max 15
typedef char DataType;
void Visit(DataType item)
{
	printf("%c",item);
}

#include"BiTreeNode.h"

int len, lena, flag[Max];
DataType pre[Max], mid[Max];

int main()
{
	void Creat(BiTreeNode *t, int low, int high);
	while(1)
	{
		gets(pre);
		gets(mid);
		BiTreeNode *root;
		Initiate(&root);
		
		len=strlen(pre);
		lena=strlen(mid);
		memset(flag, 0, sizeof(flag));
		
		if(len!=lena)
		{
			printf("error!\n");
			continue;
		}
		
		Creat(root->leftChild, 0, len-1);
		
		printf("前序遍历:\n");
		PreOrder(root->leftChild, Visit);
	
		printf("\n中序遍历:\n");
		InOrder(root->leftChild, Visit);
	
		printf("\n后序遍历:\n");
		PostOrder(root->leftChild, Visit);
	
		Destroy(&root);
		getchar();
	}
}

void Creat(BiTreeNode *t, int low, int high)
{
	int i, j, k, cin_left, cin_right;
	BiTreeNode *p;
	DataType ch;
	
	p=InsertLeftNode(t, pre[low]);
	
	for(i=0; i<len; i++)
		if(mid[i]==pre[low])break;
		
	flag[i]=1;
	cin_left=0;
	cin_right=0;
	
	for(j=0;j<i;j++)  //寻找pre[low]左支上的节点个数 
	{
		if(flag[j])continue;
		for(k=low; k<=high; k++)
		if(pre[k]==mid[j])cin_left++;
	}
	
	/*for(j=i+1;j<len;j++)
	{
		if(flag[j])continue;
		for(k=low; k<=high; k++)
		if(pre[k]==mid[j])cin_right++;
	}*/
	
	Creat(p->leftChild, low+1, low+cin_left);
	Creat(p->rightChild, low+cin_left+1, high);
}