基础数据结构之（Binary Trees)

从头开始刷ACM，真的发现过去的很多漏洞，特别越是基础的数据结构，越应该学习得精，无论是ACM竞赛，研究生考试，还是工程上，对这些基础数据结构的应用都非常多，深刻理解非常必要。不得不说最近感触还是比较多，申请阿里的校招挂了，申请的是算法工程师。然而得到的答复是第一，几乎只招研究生，本科生被Pass掉了，然后第二，问我是否有读研的打算，我说有，然后吐槽我的ACM搞得像屎一样，成绩根本无法让他满意，如果有意向，建议我能研一能拿个像样的成绩，真是2333。自己弱也怪不得别人了。

训练地址：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=84416#overview

uva679

好吧，先贴一道大水题，自习室做得。

链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=620

ps：白书上代码是超时的，真是个坑

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<vector>
 6 using namespace std;
 7 int T;
 8 int main()
 9 {
10     while(cin>>T)
11     {
12         if(T==-1)
13             break;
14         while(T--)
15         {
16         int d,l,k;
17         cin>>d>>l;
18         k=1;
19         for(int i=1;i<d;i++)
20         {
21             if(l%2)
22             {
23                 l=l-l/2;
24                 k=k*2;
25             }
26             else
27             {
28                 l=l/2;
29                 k=k*2+1;
30             }
31         }
32         cout<<k<<endl;
33         }
34 
35     }
36     return 0;
37 }

View Code

uva122

白书上的一道例题，第一棵二叉树，建树，bfs遍历

链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=58

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<cmath>
  6 #include<vector>
  7 #include<queue>
  8 #include<cstdlib>
  9 #include<cctype>
 10 using namespace std;
 11 const int maxn=1000;
 12 char s[maxn+10];
 13 int failed=0;
 14 //结点类型
 15 typedef struct Tnode
 16 {
 17     int have_value;  //是否被赋值过
 18     int v;            //结点值
 19     struct Tnode *left,*right;
 20 }Node;
 21 Node* root;
 22 
 23 Node* newnode()
 24 {
 25     Node* u=(Node*)malloc(sizeof(Node)); //申请动态内存
 26     if(u!=NULL)                           //若申请成功
 27     {
 28         u->have_value=0;                  //初始化为0
 29         u->left=u->right=NULL;            //初始化没有左右儿子
 30     }
 31     return u;
 32 }
 33 
 34 void addnode(int v,char *s)
 35 {
 36     int n=strlen(s);
 37     Node* u=root;    //从根结点开始往下走
 38     for(int i=0;i<n;i++)
 39         if(s[i]=='L')
 40     {
 41         if(u->left==NULL) u->left=newnode();  //结点不存在，建立新结点
 42         u=u->left;                            //往左走
 43     }
 44     else if(s[i]=='R')
 45     {
 46         if(u->right==NULL)  u->right=newnode();
 47         u=u->right;
 48     }                                        //忽略其他情况，即最后那个多余的右括号
 49     if(u->have_value) failed=1;              //已经赋值，表示输入有误
 50     u->v=v;
 51     u->have_value=1;                        //做标记
 52 }
 53 
 54 void remove_tree(Node* u)
 55 {
 56     if(u==NULL) return;          //提前判断比较稳妥
 57     remove_tree(u->left);        //递归释放左子树
 58     remove_tree(u->right);       //递归释放右子树
 59     free(u);                     //释放u本身
 60 }
 61 
 62 int read_input()              //保存读入结点
 63 {
 64     failed=0;
 65     remove_tree(root);       //释放一棵二叉树
 66     root=newnode();          //创建跟结点
 67     for(;;)
 68     {
 69         if(scanf("%s",s)!=1) return 0;  //整个输入结束
 70         if(!strcmp(s,"()")) break;      //结束标志
 71         int v;
 72         sscanf(&s[1],"%d",&v);          //读入结点值
 73         addnode(v,strchr(s,',')+1);     //查找逗号，然后插入结点
 74     }
 75     return 1;
 76 }
 77 
 78 int n=0,ans[maxn];
 79 int bfs()
 80 {
 81     int front=0,rear=1;
 82     Node* q[maxn];
 83     q[0]=root;
 84     while(front<rear)
 85     {
 86         Node* u=q[front++];
 87         if(!u->have_value)  return 0;
 88         ans[n++]=u->v;
 89         if(u->left!=NULL)  q[rear++]=u->left;
 90         if(u->right!=NULL)  q[rear++]=u->right;
 91     }
 92     return 1;
 93 }
 94 
 95 void print()
 96 {
 97     for(int i=0;i<n;i++)
 98     {
 99         if(i) printf(" ");
100         printf("%d",ans[i]);
101     }
102     printf("
");
103     n=0;
104 }
105 int main()
106 {
107     while(read_input())
108     {
109         if(failed||!bfs()) cout<<"not complete"<<endl;
110         else print();
111     }
112     return 0;
113 }

View Code

一个简单的知识点，今天复习数据结构教材的时候写的，已经前序跟中序，打印后序遍历

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<string>
 8 #include<stack>
 9 using namespace std;
10 const int maxn=1000+10;
11 void build(int n,char* s1,char* s2,char* s)
12 {
13     if(n<=0)  return;
14     int p=strchr(s2,s1[0])-s2;
15     build(p,s1+1,s2,s);   //后序遍历左子树
16     build(n-p-1,s1+p+1,s2+p+1,s+p); //后序遍历右子树
17     s[n-1]=s1[0];
18 }
19 int main()
20 {
21     char s1[maxn],s2[maxn],s[maxn];
22     while(scanf("%s%s",s1,s2)==2)
23     {
24         int n=strlen(s1);
25         build(n,s1,s2,s);
26         s[n]='';
27         printf("%s
",s);
28     }
29     return 0;
30 }

View Code

uva112

这题让我学到了cin的用法，不得不感叹C++还是博大精深啊，具体请看我的下一篇文章《cin的用法》

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=48

开始想建树，后来看了别人的一些思路发现并不用建树，cin.clear()确实是新的认知，uva题目质量真心高，我一定坚持刷下去，最近进度有点慢，明天要开始一切恢复正常了，8月了，一切都开始火烧眉毛了。

下面贴一下代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<cstdlib>
 8 #include<cctype>
 9 using namespace std;
10 typedef struct Tnode
11 {
12     Tnode *left,*right;
13 }node;
14 int flag;
15 node* Tree_sum(int n,int sum)
16 {
17     char ch;
18     int v;
19     cin>>ch;
20     if(!(cin>>v)==0)
21     {
22         n+=v;
23         node* root=(node*)malloc(sizeof(node));
24         root->left=Tree_sum(n,sum);
25         root->right=Tree_sum(n,sum);
26         if(!flag&&root->left==NULL&&root->right==NULL)
27         {
28             if(sum==n)
29                 flag=1;
30         }
31         cin>>ch;
32         return root;
33     }
34     else
35     {
36         cin.clear();
37         cin>>ch;
38         return NULL;
39     }
40 }
41 int main()
42 {
43     int sum;
44     while(cin>>sum)
45     {
46         flag=0;
47         node *root=Tree_sum(0,sum);
48         if(flag)
49             cout<<"yes"<<endl;
50         else
51             cout<<"no"<<endl;
52     }
53     return 0;
54 }

View Code

二叉树一个重要知识点：（已知中序+后序，求先序）

ps:白书上是已知先序+中序,求后序，这个稍有改动，说一下，严奶奶书上这个地方代码好像有问题

下面是我的代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<string>
 8 #include<stack>
 9 #include<sstream>
10 using namespace std;
11 const int maxn=1000+10;
12 int k;
13 bool read_input(int* a)
14 {
15     string line;
16     if(!getline(cin,line))  return false;
17     stringstream ss(line);
18     int x;
19     k=0;
20     while(ss>>x) a[k++]=x;
21     return k>0;
22 }
23 int i=0;
24 void build(int n,int* s1,int* s2,int* s)
25 {
26     if(n<=0)  return;
27     int p=n-1;
28     s[0]=s2[p];
29     while(s1[p]!=s2[n-1])  p--;
30     build(p,s1,s2,s+1);   //先序遍历左子树
31     build(n-p-1,s1+p+1,s2+p,s+p+1); //先序遍历右子树
32 }
33 int main()
34 {
35     int pre[maxn],in[maxn],post[maxn];
36     while(read_input(in))
37     {
38         read_input(post);
39         build(k,in,post,pre);
40         for(int i=0;i<k;i++)
41             cout<<pre[i]<<" ";
42         cout<<endl;
43     }
44     return 0;
45 }

View Code

uva548

链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=489

不得不说这道题目写了半天，开始我以为可以先通过后序跟中序得出先序，然后向uva112那样写的，后来发现并不能这样，于是开始漫长的建树之路，之后yy出一种可以不用建树的解法，还有不得不说sstream头文件中的stringstream流输入很好用，详见刘汝佳粉书《入门经典第二版》不过最大的缺点就是速度慢

我的AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<algorithm>
 8 #include<sstream>
 9 #include<cstdlib>
10 using namespace std;
11 const int maxn=10000+10;
12 int k,best_sum,best;
13 bool read_input(int* a)  //输入部分
14 {
15     string line;
16     if(!getline(cin,line))  return false;
17     stringstream ss(line);
18     k=0;
19     int x;
20     while(ss>>x) a[k++]=x;
21     return k>0;
22 }
23 void dfs(int n,int sum,int* in,int* post) //深搜即可
24 {
25     if(n<=0) return;
26     int p=find(in,in+n,post[n-1])-in;
27     sum+=post[n-1];
28     if(n==1)
29     {
30         if(sum<best_sum)
31         {
32             best_sum=sum;
33             best=post[n-1];
34         }
35         else if(sum==best_sum)
36             best=min(best,post[n-1]);
37         return;
38     }
39     dfs(p,sum,in,post);  //左子树
40     dfs(n-p-1,sum,in+p+1,post+p); //右子树
41 }
42 int main()
43 {
44     int in[maxn],post[maxn];
45     while(read_input(in))
46     {
47         read_input(post);
48         best_sum=best=0x3ffff;
49         dfs(k,0,in,post);
50         cout<<best<<endl;
51     }
52     return 0;
53 }

View Code

uva297

链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104

四叉树，第一次写，不过这题比较特殊，只需要先序就可以建树，然后照着画，边画边统计

我的代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<cstdlib>
 8 #include<algorithm>
 9 using namespace std;
10 const int maxn=10010;
11 char s1[maxn],s2[maxn];
12 char *p;
13 int sum;
14 typedef struct Tnode
15 {
16     int have_value;
17     struct Tnode* child[4];
18 }node;
19 //建立四叉树
20 node* build_tree()
21 {
22     node* root=(node*)malloc(sizeof(node));
23     root->have_value=0;
24     if(*p=='p')
25     {
26         for(int i=0;i<4;i++)
27         {
28             ++p;
29             root->child[i]=build_tree();
30         }
31     }
32     else
33     {
34         if(*p=='f')
35          root->have_value=1;
36         for(int i=0;i<4;i++)
37             root->child[i]=NULL;
38     }
39     return root;
40 }
41 //dfs遍历一下
42 void dfs(node* root1,node* root2,int cnt)
43 {
44     if(root1==NULL&&root2==NULL) return;
45     if(root1==NULL)
46     {
47         if(root2->have_value)
48         {
49             sum+=1024>>(2*cnt);
50             return;
51         }
52         for(int i=0;i<4;i++)
53             dfs(root1,root2->child[i],cnt+1);
54         return;
55     }
56     if(root2==NULL)
57     {
58         if(root1->have_value)
59         {
60             sum+=1024>>(2*cnt);
61             return;
62         }
63         for(int i=0;i<4;i++)
64             dfs(root1->child[i],root2,cnt+1);
65         return;
66     }
67     if(root1->have_value||root2->have_value)
68     {
69         sum+=1024>>(2*cnt);
70         return;
71     }
72     for(int i=0;i<4;i++)
73         dfs(root1->child[i],root2->child[i],cnt+1);
74 }
75 int main()
76 {
77     int T;
78     cin>>T;
79     while(T--)
80     {
81         cin>>s1>>s2;
82         p=s1;
83         node* root1=build_tree();
84         p=s2;
85         node* root2=build_tree();
86         sum=0;
87         dfs(root1,root2,0);
88         printf("There are %d black pixels.
",sum);
89     }
90 }

View Code

uva712

链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=653

关键是对题目意思的理解，一个大水题，其实就是0表示向左2*n，1表示向右2*n+1，然后给出一堆查询，输出最后的序列

要换行，uva没有pe，只有WA我也是醉了，要不是看题目意思，我还找不出错误在哪儿

我的代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 using namespace std;
 7 const int maxn=300;
 8 string s[maxn],query[maxn];
 9 char p[maxn];
10 int main()
11 {
12     int n,t;
13     int cas=1;
14     while(cin>>n)
15     {
16         if(n==0)
17             break;
18             for(int i=0;i<n;i++)
19                 cin>>s[i];
20            cin>>p;
21          cin>>t;
22          for(int i=0;i<t;i++)
23                 cin>>query[i];
24          int sum;
25          printf("S-Tree #%d:
",cas);
26          for(int i=0;i<t;i++)
27          {
28              sum=1;
29              for(int j=0;j<query[i].length();j++)
30              {
31                  if(query[i][j]=='0')
32                     sum=sum*2;
33                  else
34                     sum=sum*2+1;
35              }
36              int ff=pow(2,n);
37              printf("%c",p[sum-ff]);
38          }
39          printf("

");
40          cas++;
41     }
42     return 0;
43 }

View Code

复习复习，晚上在刷一题

uva699

链接：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19244

题意：就是统计二叉树每一行的和为多少，给出了先序遍历。我们可以把当前位置设为p，左子树p-1，右子树p+1，然后进行递归即可

我的代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=81;
 6 int sum[maxn];
 7 void build(int root,int p)
 8 {
 9     if(root!=-1)
10     {
11         sum[p]+=root;
12         int x,y;
13         cin>>x;
14         build(x,p-1);
15         cin>>y;
16         build(y,p+1);
17     }
18 }
19 int main()
20 {
21     int n,cas=1;
22     while(cin>>n)
23     {
24         if(n==-1)
25             break;
26         memset(sum,0,sizeof(sum));
27         build(n,40);
28         printf("Case %d:
",cas);
29         int k;
30         for(int i=0;i<81;i++)
31             if(sum[i]!=0)
32         {
33             k=i;
34             printf("%d",sum[i]);
35             break;
36         }
37         for(int i=k+1;i<81;i++)
38             if(sum[i]!=0)
39             printf(" %d",sum[i]);
40         printf("

");
41         cas++;
42     }
43 }

View Code

uva327

链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=263

我也不知道这题为什么放在二叉树里面，直接模拟就好了嘛，注意几种情况,a+b,a-b,a++-b,a+++b,--a,++a,然后注意处理一下空格就好了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<cctype>
 7 #include<cstdlib>
 8 using namespace std;
 9 const int maxn=30;
10 int a[maxn],flag[maxn];
11 int main()
12 {
13     string s;
14     while(getline(cin,s))
15     {
16         cout<<"Expression: "<<s<<endl;
17         string ss="";
18         for(int i=0;i<s.length();i++)
19             if(s[i]!=' ')
20             ss+=s[i];
21         for(int i=0;i<26;i++)
22             a[i]=i+1;
23         memset(flag,0,sizeof(flag));
24         int sum=0;
25         for(int i=0;i<ss.length();i++)
26         {
27             if(islower(ss[i]))
28             {
29                 if(i==0)
30                     sum+=(ss[i]-'a'+1);
31                 else
32                 {
33                     if(ss[i-1]!=ss[i-2])
34                     {
35                         if(ss[i-1]=='+')
36                             sum+=ss[i]-'a'+1;
37                         else if(ss[i-1]=='-')
38                             sum-=ss[i]-'a'+1;
39                     }
40                     else
41                     {
42                         if(ss[i-2]=='-')
43                             a[ss[i]-'a']--;
44                         else if(ss[i-2]=='+')
45                             a[ss[i]-'a']++;
46                         if(i>3&&ss[i-3]=='-')
47                             sum-=a[ss[i]-'a'];
48                         else
49                             sum+=a[ss[i]-'a'];
50                     }
51                 }
52                 if(i+2<ss.length()&ss[i+1]==ss[i+2]&&ss[i+2]=='+')
53                         a[ss[i]-'a']++;
54                     else if(i+2<ss.length()&&ss[i+2]==ss[i+1]&&ss[i+2]=='-')
55                         a[ss[i]-'a']--;
56                         flag[ss[i]-'a']=1;
57             }
58         }
59         cout<<"    value = "<<sum<<endl;
60         for(int i=0;i<26;i++)
61             if(flag[i])
62             printf("    %c = %d
",'a'+i,a[i]);
63     }
64     return 0;
65 }

View Code

uva839

链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=780

这题我参照了题解，采取递归的方式定义，因此编写一个递归进行定义就是比较自然的事情

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int ok;
 7 int dfs()
 8 {
 9     int wl,dl,wr,dr;
10     cin>>wl>>dl>>wr>>dr;
11     if(wl&&dl&&wr&&dr)  //叶子结点
12     {
13         if(wl*dl!=wr*dr)　　//只要有一个不平衡全不平衡
14         {
15             ok=0;
16             return 0;
17         }
18         else return wl+wr;　　//返回子树的重量
19     }
20     else
21     {
22         if(!wl) wl=dfs();　　//遍历左子树　　　
23         if(!wr) wr=dfs();　　　　//遍历右子树
24         if(wl*dl!=wr*dr)
25         {
26             ok=0;
27             return 0;
28         }
29         else
30             return wl+wr;
31     }
32 }
33 int main()
34 {
35     int T;
36     cin>>T;
37     int i=0;
38     while(T--)
39     {
40        ok=1;
41        dfs();
42        if(i++)  cout<<endl;
43        if(ok)  cout<<"YES"<<endl;
44        else  cout<<"NO"<<endl;
45     }
46     return 0;
47 }

View Code