4-1.c

来自「《数据结构-使用C语言》第三版」· C语言 代码 · 共 95 行

#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, int f);
	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, 0, len-1, 0);
		
		printf("\n前序遍历:\n");
		PreOrder(root->leftChild, Visit);
	
		printf("\n中序遍历:\n");
		InOrder(root->leftChild, Visit);
	
		printf("\n后序遍历:\n");
		PostOrder(root->leftChild, Visit);
		printf("\n\n");
	
		Destroy(&root);
		//getchar();
	}
}

void Creat(BiTreeNode *t, int low, int high, int f)
{
	int i, j, k, cin_left, cin_right;
	BiTreeNode *p;
	
	if(low>high)return ;
	
	if(f==0)p=InsertLeftNode(t, pre[low]);
	else p=InsertRightNode(t, pre[low]);
	
	if(low==high)return ;
	
	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++;
			break;
		}
	}

	/*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, low+1, low+cin_left, 0);
	Creat(p, low+cin_left+1, high, 1);
}