b346: 二元搜尋樹快速建造
Tags : 平衡樹 笛卡爾樹
Accepted rate : 32人/84人 ( 38% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-06-15 06:29

Content
二元搜尋樹(Binary Search Tree),也稱二叉搜索樹、有序二元樹(ordered binary tree),排序二元樹(sorted binary tree),是指一棵空樹或者具有下列性質的二元樹:

  1. 若任意節點的左子樹不空,則左子樹上所有結點的值均小於它的根結點的值;
  2. 任意節點的右子樹不空,則右子樹上所有結點的值均大於它的根結點的值;
  3. 任意節點的左、右子樹也分別為二元搜尋樹。
  4. 沒有鍵值相等的節點(no duplicate nodes)。
void insert(Node*& root, int data) {   
if (!root)      root = new Node(data);   
else if (data < root->data)     
insert(root->left, data);   
else if (data > root->data)     
insert(root->right, data); 
}

通常一開始學到二元搜尋樹,會先教插入算法,現在的這個問題很簡單,只是稍微要求效率。

Input

輸入有多組測資,

每一組,第一行有一個數字 N (0 < N < 131072)

接下來會建入 N 個數字 M (signed 32-bit) ,沒有數字會重複。

 

Output
對於每一組測資,輸出一行的前序走訪。
Sample Input #1
5
0 1 2 4 3
5
0 2 4 1 3
5
3 1 4 2 0
5
1 4 2 0 3
5
0 4 3 2 1
Sample Output #1
0 1 2 4 3 
0 2 1 4 3 
3 1 0 2 4 
1 0 4 2 3 
0 4 3 2 1 
測資資訊:
記憶體限制: 32 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
平衡樹 笛卡爾樹
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」