1064. Complete Binary Search Tree
15878 단어 Binary search
http://www.patest.cn/contests/pat-a-practise/1064
1 #include <stdio.h>
2
3 #include <math.h>
4
5 #include <algorithm>
6
7 using namespace std;
8
9 struct Node
10
11 {
12
13 Node* lchild;
14
15 Node* rchild;
16
17 int val;
18
19 }Tree[1001];
20
21
22
23 int loc;
24
25 Node * create()
26
27 {
28
29 Tree[loc].lchild=NULL;
30
31 Tree[loc].rchild=NULL;
32
33 return &Tree[loc++];
34
35 }
36
37 bool cmp(int a,int b)
38
39 {
40
41 return a<b;
42
43 }
44
45 Node* fun(int ans[],int len,Node* T)
46
47 {
48
49 int com;//
50
51 int left;// T
52
53 int right;// ———— ———————
54
55 int LastLevel;//
56
57 int LeftLastLevel;//
58
59 int level;//
60
61 // level
62
63 level=0;
64
65 while(pow(2.0,level)-1<len)// 2^(level)-1
66
67 ++level;
68
69 LastLevel=len-pow(2.0,level-1)+1;
70
71 if(LastLevel<pow(2.0,level-1)/2)// n 2^(n-1)
72
73 LeftLastLevel=LastLevel; //
74
75 else LeftLastLevel=pow(2.0,level-1)/2;
76
77 left=(pow(2.0,level-1)-1-1)/2+LeftLastLevel;
78
79 right=len-left-1;
80
81 T=create();
82
83 T->val=ans[left+1];
84
85 if(left>0)
86
87 T->lchild=fun(ans,left,T->lchild);
88
89 if(right>0)
90
91 T->rchild=fun(ans+left+1,right,T->rchild);
92
93 return T;
94
95 }
96
97 int main()
98
99 {
100
101 int n,i;
102
103 while(scanf("%d",&n)!=EOF)
104
105 {
106
107 getchar();
108
109 int ans[1001];
110
111 for(i=1;i<=n;i++)
112
113 scanf("%d",&ans[i]);
114
115 getchar();
116
117 sort(ans+1,ans+1+n,cmp);
118
119 Node* T=NULL;
120
121 loc=0;
122
123 T=fun(ans,n,T);
124
125 //
126
127 Node* que[1001];
128
129 int rear=0,front=0;
130
131 que[rear++]=T;
132
133 printf("%d",T->val);
134
135 while(rear!=front)
136
137 {
138
139 Node* temp=que[front++];
140
141
142
143 if(temp->rchild!=NULL)
144
145 {
146
147 que[rear++]=temp->lchild;
148
149 que[rear++]=temp->rchild;
150
151 printf(" %d %d",temp->lchild->val,temp->rchild->val);
152
153 }
154
155 else if(temp->lchild!=NULL)
156
157 {
158
159 que[rear++]=temp->lchild;
160
161 printf(" %d",temp->lchild->val);
162
163 }
164
165 }
166
167 printf("
");
168
169 }
170
171 return 0;
172
173 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[leetode]Binary Search Tree Iterator텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.