Posted on 2009-07-09 16:20
Hero 閱讀(306)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //HLOJ 1042 Accepted 15 276 1180 C++
2
3 //二叉樹的中序遍歷
4 //沒有考慮到虛節點
5
6 #include <iostream>
7 using namespace std ;
8
9 const int size = 20000 ;
10 int data[size] ;
11
12 int tnum ;
13 int inn ;
14 char *blank = "" ;
15 bool istree = false ;
16
17 int deep ;
18
19 void DFS( int root )
20 {
21 if( root > inn ) return ;
22
23 if( data[root] != 0 ) DFS( root * 2 ) ;
24
25 if( data[root] != 0 )
26 {
27 printf( "%s%d", blank, data[root] ) ;
28 blank = " " ;
29 istree = true ;
30 deep = deep > root ? deep : root ;
31 }
32
33 if( data[root] != 0 ) DFS( root * 2 + 1 ) ;
34 }
35
36 int fpow( int a, int b )
37 {
38 int reval = 1 ;
39
40 for( int i=1; i<=b; i++ )
41 {
42 reval = reval * a ;
43 }
44
45 return reval ;
46 }
47
48 int main()
49 {
50 while( cin >> tnum )
51 {
52 while( tnum -- )
53 {
54 cin >> inn ;
55
56 memset( data, 0, sizeof(data) ) ;
57 blank = "" ;
58 istree = false ;
59 deep = 0 ;
60
61 for( int i=1; i<=inn; i++ )
62 {
63 cin >> data[i] ;
64 }
65
66 DFS( 1 ) ; cout << endl ;
67
68 int cnt = 0 ; int num = 0 ;
69 while( num < deep && istree )
70 {
71 num = num + fpow( 2, cnt ) ;
72 cnt = cnt + 1 ;
73 }
74
75 cout << cnt << endl ;
76 }
77 }
78
79 return 0 ;
80 }