poj 3437這道題不難，不過(guò)考察的知識(shí)點(diǎn)比較多。
給出深度優(yōu)先遍歷一棵數(shù)的數(shù)據(jù)，求這棵樹(shù)用左兒子右兄弟的方法變成二叉樹(shù)后，變化前后的深度。
涉及的知識(shí)有：
1. 求樹(shù)的深度；2. 遞歸；3. 左兒子右兄弟表示法。
1 #include <iostream>
2
3 using namespace std;
4
5 const int maxn=20010;
6 char s[maxn];
7
8 int dfs(int b,int e,int &d)
9 {
10 if(b>e) return 0;
11 int i,j,k=b,cnt=1,maxi=0,res,maxd=0,td;
12 int flag;
13 while(k<=e){
14 i=k;
15 flag=(s[k]=='d')?1:-1;
16 while(flag!=0){
17 if(s[++k]=='d') flag++;
18 else flag--;
19 }
20 j=k++;
21 td=0;
22 res=dfs(i+1,j-1,td);
23 if(td>maxd) maxd=td;
24 if(cnt+res>maxi) maxi=cnt+res;
25 cnt++;
26 }
27 d=maxd+1;
28 return maxi;
29 }
30
31 int main()
32 {
33 int cnt=1;
34 while(true){
35 gets(s);
36 if(s[0]=='#') return 1;
37 int depth=0;
38 int len=strlen(s);
39 int res=dfs(0,len-1,depth);
40 printf("Tree %d: %d => %d\n",cnt++,depth,res);
41 }
42 return 1;
43 }