1719 測資加強 已 rejudge
1609 . Problem C 二元搜尋樹 (TRVBST)
Description
二元搜尋樹是最基礎的一種動態資料結構，支持動態的新增、刪除、查找元素等操作，
我們也可以視二元搜尋樹為一個可動態維護的集合。
此外，二元搜尋樹的效率大致取決於樹的高度，而樹的高度則由元素插入的順序決定。
最壞情況下，對二元搜尋樹做n次插入操作可能需要O(n2) 的時間。
假設現在我們已經知道所有元素插入一棵二元搜尋樹的順序，
請問所有元素皆插入後，二元搜尋樹的中序遍歷結果為 ?
Input Format
第一行有一個正整數n，代表我們總共插入了n個不同的元素(1≦n≦1,000,000)。
接下來的n行，每一行有一個整數，第i+1行代表第i個插入的元素vi
(-230≦vi≦230)。
Output Format
請輸出一行，總共有n個整數，代表二元搜尋樹的中序遍歷結果。整數間請以一個空白
隔開。
Sample Input 1
6
-10
10
100
1000
10000
1000000
-10
10
100
1000
10000
1000000
Sample Output 1
-10 10 100 1000 10000 1000000
Hints
Problem Source
原TIOJ1609 / Problem Setter: suhorng
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |