- /*
- * 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;
- }
- //该片段来自于http://www.codesnippet.cn/detail/260620134301.html
来源: http://www.codesnippet.cn/detail/260620134301.html