Board logo

標題: 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. if (!root)      root = new Node(data);   

  3. else if (data < root->data)     

  4. insert(root->left, data);   

  5. else if (data > root->data)     

  6. insert(root->right, data);

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

輸入說明 :

輸入有多組測資,

每一組,第一行有一個數字 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