建树

输入从根节点开始的路径，输出层次遍历的结果

样例输入

（3，L）

（2，R）

（）

输出：

1 3 2

指针实现

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string.h>
  4 #include<stdlib.h>
  5 using namespace std;
  6 const int maxn=100;
  7 char s[maxn];
  8 int fail=0;
  9 typedef struct tnode
 10 {
 11     int have_val;
 12     int u;
 13     tnode *right,*left;
 14 }node;
 15 node *root;
 16 int cnt,ans[maxn];
 17 node *newnode()
 18 {
 19     node *r=(node *)malloc(sizeof(node));
 20     r->have_val=0;
 21     r->left=r->right=NULL;
 22 }
 23 void addnode(int u,char *s)
 24 {
 25     int len=strlen(s);
 26     node *r=root;
 27     for(int i=0;i<len-1;i++)
 28     {
 29         if(s[i]=='L')
 30         {
 31             if(r->left==NULL)
 32                 r->left=newnode();
 33             r=r->left;
 34         }
 35         else if(s[i]=='R')
 36         {
 37             if(r->right==NULL)
 38                 r->right=newnode();
 39             r=r->right;
 40         }
 41     }
 42     if(r->have_val)
 43         fail=1;
 44     r->have_val=1;
 45     r->u=u;
 46 }
 47 int bfs()
 48 {
 49     int rear=1;
 50     int front=0;
 51     node *q[maxn];
 52     q[0]=root;
 53     while(front<rear)
 54     {
 55         node *r;
 56         r=q[front++];
 57         if(r->have_val==0)
 58             return 0;
 59         ans[cnt++]=r->u;
 60         if(r->left!=NULL)
 61             q[rear++]=r->left;
 62         if(r->right!=NULL)
 63             q[rear++]=r->right;
 64     }
 65     return 1;
 66 }
 67 void remove(node *u)
 68 {
 69     if(u==NULL)
 70         return ;
 71     remove(u->left);
 72     remove(u->right);
 73     free(u);
 74 }
 75 int main()
 76 {
 77     fail=0;
 78     remove(root);
 79     root=newnode();
 80     root->have_val=1;
 81     root->u=1;
 82     cnt=0;
 83     while(scanf("%s",s)==1)
 84     {
 85         if(!strcmp(s,"()"))
 86             break;
 87         int v;
 88         sscanf(&s[1],"%d",&v);
 89         addnode(v,strchr(s,',')+1);
 90     }
 91     if(bfs())
 92     {
 93         for(int i=0;i<cnt;i++)
 94             printf("%d ",ans[i]);
 95         printf("
");
 96 
 97     }
 98     else printf("the tree is incorrect
");
 99     return 0;
100 }

View Code

数组实现

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<string.h>
 4 using namespace std;
 5 const int maxn=100;
 6 int fail=0;
 7 int left[maxn],right[maxn],ans[maxn],pos[maxn],vis[maxn];
 8 char s[maxn];
 9 const int root=1;
10 int cnt;
11 void newtree(){cnt=1;left[root]=right[root]=0;}
12 int newnode(){int u=++cnt;left[u]=right[u]=0;return u;};
13 void addnode(int u,char *s)
14 {
15     int len=strlen(s);
16     int r=1;
17     for(int i=0;i<len-1;i++)
18     {
19         if(s[i]=='L')
20         {
21             if(left[r]==0)
22                 left[r]=newnode();
23             r=left[r];
24 
25         }
26         else if(s[i]=='R')
27         {
28             if(right[r]==0)
29                 right[r]=newnode();
30             r=right[r];
31         }
32 
33     }
34     if(vis[r])
35         fail=1;
36     pos[r]=u;
37     vis[r]=1;
38 }
39 int bfs()
40 {
41     int front=0,rear=1;
42     int r=1;
43     int q[maxn];
44     q[0]=1;
45     cnt=0;
46     while(front<rear)
47     {
48         r=q[front++];
49         if(!vis[r])
50             return 0;
51         ans[cnt++]=pos[r];
52 
53         if(left[r])
54             q[rear++]=left[r];
55         if(right[r])
56             q[rear++]=right[r];
57     }
58     return 1;
59 
60 }
61 int main()
62 {
63 
64     memset(vis,0,sizeof(vis));
65     fail=0;
66     cnt=0;
67     pos[1]=1;
68     vis[1]=1;
69     newtree();
70     while(scanf("%s",s))
71     {
72         if(!strcmp(s,"()"))
73             break;
74         int v;
75         sscanf(&s[1],"%d",&v);
76         addnode(v,strchr(s,',')+1);
77     }
78 
79 
80     if(bfs())
81     {
82 
83         for(int i=0;i<cnt;i++)
84             printf("%d ",ans[i]);
85         printf("
");
86     }
87     else printf("the tree is not correct");
88     return 0;
89 }

View Code