苗火 Nicholas

[Data structures]Create binary tree by sequence

2019-8-8 萧 写技术

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

#define MAX 20

typedef struct _BiTree{
	char data;
	struct _BiTree *left;
	struct _BiTree *right;
}BiTree;

void CreateByPreInOrder(BiTree **T, char *pre, int pre_begin, int pre_end, char *in, int in_begin, int in_end)
{
	int len;
	int i;

	if(pre_begin > pre_end){
		return;
	}

	*T = (BiTree *)malloc(sizeof(BiTree));
	(*T)->data = pre[pre_begin];
	
	for(i=in_begin; i<=in_end; i++){
		if((*T)->data == in[i]){
			break;
		}
	}
	len = i - in_begin;

	CreateByPreInOrder(&(*T)->left, pre, pre_begin+1, pre_begin+len, in, in_begin, i-1);
	CreateByPreInOrder(&(*T)->right, pre, pre_begin+1+len, pre_end, in, i+1, in_end);

}


void PreOrderTranvers(BiTree *T)
{
	if(T){
		printf(" %c(", T->data);
		PreOrderTranvers(T->left);
		printf(",");
		PreOrderTranvers(T->right);
		printf(")");
	}
}

void main()
{
	BiTree *T;	
	char pre[] = {'A','B','C','D','E','F','G'};
	char in[]  = {'C','B','E','D','A','F','G'};
	int n = sizeof(pre)/sizeof(char);
	int i;

	printf("log.anycle.com\n\n");
	printf("Pre order sequence:\n");
	for(i=0; i<n; i++){
		printf(" %c", pre[i]);
	}
	printf("\n");
	printf("In order sequence:\n");
	for(i=0; i<n; i++){
		printf(" %c", in[i]);
	}
	printf("\n");


	printf("Create binary tree by pre and in order:\n");
	CreateByPreInOrder(&T, pre, 0, n-1, in, 0, n-1);
	printf("\n");

	printf("Pre order traverse:\n");
	PreOrderTranvers(T);
	printf("\n");
}

标签: Data Structures data_structures