Sicily 1156. Binary tree 解题报告

思路：

　　简单的一道二叉树相关的题目，题目会给出一颗树现在的形态，然后用前序遍历这棵树的节点输出数据即可。

　　每个节点会输入该节点的identifier，有点类似于key，然后输入该节点储存的数据（char类型）和该节点左右子节点的identifier。

　　这里直接用开了几个数组存储数据，对于一个节点identifier，将其数据存进data[identifier]里，左右子树分别存进left[identifier],right[identifier]中。输出的时候需要找到树的根root，所以可以开一个bool数组来找根，初始化全为false，读进的node都有可能是根所以都置为true，然后再将确定是左右子树的node置为false，最后数组只剩一个true的下标就是根的位置。

　　输出用递归即可。

代码：

 1 #include<iostream>
 2 #include<memory.h>
 3 using namespace std;
 4 
 5 
 6 void recursive_preorder_print(char *data,int *left,int *right,int sub_root);
 7 
 8 int main(){
 9     int num_of_nodes;
10     while(cin>>num_of_nodes&&num_of_nodes!=0){
11         int left[1001]={0},right[1001]={0},root;
12         char data[1001];
13         bool is_root[1001];
14         memset(is_root,false,sizeof(is_root));
15         //the data,leftchild and rightchild will be stored in index identifier
16         for(int i=0;i<num_of_nodes;i++){
17             int identifier;
18             cin>>identifier;
19             is_root[identifier]=true;//All nodes was assumed to be is_root first.
20             cin>>data[identifier]>>left[identifier]>>right[identifier];
21         }
22         //children nodes are not is_root.
23         for(int i=1;i<=1000;i++){
24             is_root[left[i]]=false;
25             is_root[right[i]]=false;
26         }
27         //find the is_root
28         for(int i=1;i<=1000;i++){
29             if(is_root[i]==true){
30                 root=i;
31                 break;
32             }
33         }
34         recursive_preorder_print(data,left,right,root);
35         cout<<endl;
36     }
37     return 0;
38 }
39 void recursive_preorder_print(char *data,int *left,int *right,int sub_root){
40     //Post:the tree begin from sub_root identifier root is print preorder.
41     //Uses:the function recursive_preorder_print itself.
42     if(sub_root!=0){//not a NULL node
43         cout<<data[sub_root];
44         if(left[sub_root]!=0)
45             recursive_preorder_print(data,left,right,left[sub_root]);
46         if(right[sub_root]!=0)
47             recursive_preorder_print(data,left,right,right[sub_root]);
48     }
49 }