/*
* 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;
}