標題: b346: 二元搜尋樹快速建造 [打印本頁]

---

作者: 劉得恩    時間: 2014-11-1 11:42     標題: b346: 二元搜尋樹快速建造

內容 ：
二元搜尋樹（Binary Search Tree），也稱二叉搜索樹、有序二元樹（ordered binary tree），排序二元樹（sorted binary tree），是指一棵空樹或者具有下列性質的二元樹：

    若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
    任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
    任意節點的左、右子樹也分別為二元搜尋樹。
    沒有鍵值相等的節點（no duplicate nodes）。

1. void insert(Node*& root, int data) {   
   
2. 
   
3. if (!root)      root = new Node(data);   
   
4. 
   
5. else if (data < root->data)     
   
6. 
   
7. insert(root->left, data);   
   
8. 
   
9. else if (data > root->data)     
   
10. 
    
11. insert(root->right, data);
    
12. 
    
13. }

複製代碼

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

輸入說明 ：

輸入有多組測資，

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

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



輸出說明 ：
對於每一組測資，輸出一行的前序走訪。
範例輸入 ： help

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

範例輸出 ：

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

提示 ：

出處 ：
妮可
(管理：morris1028)

---

作者: 劉得恩    時間: 2014-11-1 11:43

此帖僅作者可見

---

歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)

Powered by Discuz! 7.2