C++利用先序，中序遍历恢复二叉树

/*
 *   This is a small program to recover the binary tree with pre_order and in_order,the
 *   pre_order and in_order are stored by array and the recovered binary tree is stored
 *   in linked type.
 *                                                                 n.comoon
 *
 *								  Apr.16th.2012
 */
#include<stdio.h>
#include<string.h>



#define ORDER_SIZE 50



/*
 * global values that are used to record the info in recurssion
 * 'pre_flag' is the cursor of array 'pre_order' in 'creating_order'
 * 'new_flag' is the cursor of array 'new_order' in 'creating_order'(new_order is the input sequence for creating linked binary tree)
 * 'flag' is the cursor of array 'new_order' in 'create_tree'
 */
int pre_flag=0,new_flag=0,flag=0;



typedef struct binary_tree
{
	char ch;
	struct binary_tree * left;
	struct binary_tree * right;
}binary_tree;



void get_orders(char * pre_order,char * in_order)
{
	printf("please input the pre_order of the binary tree!\n");
	scanf("%s",pre_order);
	printf("please input the in_order of the binary tree!\n");
	scanf("%s",in_order);
}



void creating_order(char * pre_order,char * in_order,char * new_order,int in_left,int in_right)
{
	int i;
	for(i=0;i<strlen(in_order);i++)
	{
	/*
	 * find the current node pointed by 'pre_flag' in in_order
	 */
		if(pre_order[pre_flag]==in_order[i])
		{
			break;
		}
	}
	new_order[new_flag]=pre_order[pre_flag];
	new_flag++;
	pre_flag++;
	if(i==in_left && i==in_right)
	{
	/*
	 * if the current node has no left child and right child
	 */
		new_order[new_flag]='#';
		new_flag++;
		new_order[new_flag]='#';
		new_flag++;
		return;
	}
	if(i==in_left)
	{
	/*
	 * if the current node has no left child
	 */
		new_order[new_flag]='#';
		new_flag++;
		creating_order(pre_order,in_order,new_order,i+1,in_right);
	}
	else if(i==in_right)
	{
	/*
	 * if the current node has no right child
	 */
		creating_order(pre_order,in_order,new_order,in_left,i-1);
		new_order[new_flag]='#';
		new_flag++;
	}
	else
	{
	/*
	 * if the current node has both left child and right child
	 */
		creating_order(pre_order,in_order,new_order,in_left,i-1);
		creating_order(pre_order,in_order,new_order,i+1,in_right);
	}
}



binary_tree * create_tree(char * new_order)
{
	binary_tree * tmp_tree;
	if(new_order[flag]=='#')
	{
		tmp_tree=NULL;
		flag++;
	}
	else
	{
		tmp_tree=(binary_tree *)malloc(sizeof(binary_tree));
		tmp_tree->ch=new_order[flag];
		flag++;
		tmp_tree->left=create_tree(new_order);
		tmp_tree->right=create_tree(new_order);
	}
	return tmp_tree;
}



void print_tree(binary_tree * my_tree,int spaces)
{
	int i;
	if(my_tree==NULL)
	{
		return;
	}
	print_tree(my_tree->right,spaces+1);
	for(i=0;i<spaces;i++)
	{
		printf(" ");
	}
	printf("%c\n",my_tree->ch);
	print_tree(my_tree->left,spaces+1);
}



int main()
{
	char pre_order[ORDER_SIZE],in_order[ORDER_SIZE],new_order[ORDER_SIZE];
	binary_tree * my_tree;
	get_orders(pre_order,in_order);
	creating_order(pre_order,in_order,new_order,0,strlen(in_order)-1);
	my_tree=create_tree(new_order);
	printf("the recovery binary tree is as following!\n");
	print_tree(my_tree,1);
	return 0;
}