alan23273850 的刷題筆記
d526: Binary Search Tree (BST)
Tags: b.s.t, linked-list
出處：https://zerojudge.tw/ShowProblem?problemid=d526
提交：https://zerojudge.tw/Submissions?problemid=d526&account=allllllan123456
問題：給定 $N\in[1,1000]$ 個 int 範圍內的正整數，試問按照此順序建出來的二元搜尋樹之前序遍歷的結果。
解法：這題就蠻經典的資料結構題目，之所以特別記錄是因為 linked list (在總體積上限已知的情況下) 可以用陣列模擬，而前序遍歷法也可以用 stack 實作。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int num, arr[1001];
6 int N, count, left[1001], right[1001];
7 while (cin >> N) {
8 stack<int> s; count = left[0] = right[0] = 0;
9 cin >> arr[count++]; N--; // build the root node first
10 while (N--) {
11 cin >> num; int i = 0;
12 while (true) {
13 if (arr[i] < num) {
14 if (right[i]) i = right[i];
15 else {
16 right[i] = count++; i = right[i];
17 arr[i] = num; left[i] = right[i] = 0;
18 break;
19 }
20 } else if (num < arr[i]) {
21 if (left[i]) i = left[i];
22 else {
23 left[i] = count++; i = left[i];
24 arr[i] = num; left[i] = right[i] = 0;
25 break;
26 }
27 } else assert(false);
28 }
29 }
30 s.push(0);
31 while (!s.empty()) {
32 int i = s.top(); s.pop();
33 if (right[i]) s.push(right[i]);
34 if (left[i]) s.push(left[i]);
35 cout << arr[i] << ' ';
36 }
37 cout << '\n';
38 }
39 return 0;
40}