gistfile1.c

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

typedef struct _Tree {
	char		  value;
	struct _Tree* left;
	struct _Tree* right;
} Tree;

Tree * newTree(char v) {
	Tree* t = malloc(sizeof(Tree));
	t->value = v;
	t->left	 = t->right = NULL;
	return t;
}

void printPreorder(Tree* tree) {
	if (NULL != tree) {
		printf("%c ", tree->value);
		printPreorder(tree->left);
		printPreorder(tree->right);
	}
}

void printInorder(Tree* tree) {
	if (NULL != tree) {
		printInorder(tree->left);
		printf("%c ", tree->value);
		printInorder(tree->right);
	}
}

void printPostorder(Tree* tree) {
	if (NULL != tree) {
		printPostorder(tree->left);
		printPostorder(tree->right);
		printf("%c ", tree->value);
	}
}

Tree * treeFromInorderAndPreorder(char inorder[], char preorder[], size_t count) {
	Tree*	 root				= newTree(preorder[0]);
	unsigned indexOfRootInorder = 0;

	if (0 == count) {
		return NULL;
	}
	for (int i = 0; i < count; i++) {
		if (preorder[0] == inorder[i]) {
			indexOfRootInorder = i;
			break;
		}
	}

	size_t leftsize	 = indexOfRootInorder;
	size_t rightsize = count - leftsize - 1;

	char left_inorder[leftsize];
	char left_preorder[leftsize];

	char right_inorder[rightsize];
	char right_preorder[rightsize];

	for (int i = 0; i < leftsize; i++) {
		left_inorder[i]	 = inorder[i];
		left_preorder[i] = preorder[i + 1];
	}

	for (int i = 0; i < rightsize; i++) {
		right_inorder[i]  = inorder[i + leftsize + 1];
		right_preorder[i] = preorder[i + leftsize + 1];
	}
	root->left	= treeFromInorderAndPreorder(left_inorder, left_preorder, leftsize);
	root->right = treeFromInorderAndPreorder(right_inorder, right_preorder, rightsize);
	return root;
}

int main() {
	char   inorder[]  = { 'a', 'd', 'c', 'g', 'b', 'h', 'e', 'f', 'i' };
	char   preorder[] = { 'c', 'd', 'a', 'f', 'g', 'h', 'b', 'e', 'i' };
	size_t count	  = sizeof(inorder) / sizeof(char);
	Tree*  tree		  = treeFromInorderAndPreorder(inorder, preorder, count);

	printPreorder(tree);
	printf("\n");
	printPostorder(tree);
	printf("\n");
	printInorder(tree);

	return 0;
}