[ 資料結構 小學堂 ] 樹狀結構導論 : 二元運算樹進階研究 - 二元搜尋樹

前言 :
如果一個二元樹符合 "每一個節點的資料大於左子節點且小於右子節點", 這棵樹便稱為二分樹. 因為二分數方便用來排序及搜尋, 包括二元排序樹或是二元搜尋樹都是二分樹的一種. 當建立一棵二元排序樹後, 接著也要清楚知道如何在一排序樹中搜尋某一筆資料, 事實上二元搜尋或二元排序樹可以說是一體兩面. 其中二元搜尋樹T 具有以下特點 :

- 可以是空集合, 但若不是空集合則節點上一定要有一個鍵值.
- 每一個樹根的值須大於左子樹的值.
- 每一個樹根的植須小於右子樹的值.
- 左右子樹也是二元搜尋樹.
- 樹的每個節點值都不同.

二元搜尋樹 :
基本上只要懂二元樹的排序就可以理解二元樹的搜尋. 只需在二元樹中比較樹根與欲搜尋的值, 在依 左子樹 > 樹根 > 右子樹的原則走訪二元樹就可以找到我們打算搜尋的值.

範例代碼 :
* BinarySearchTree.h 代碼 :

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4.   
5. class BinarySearchTreeNode{  
6. public:  
7.     int data;  
8.     class BinarySearchTreeNode *left;  
9.     class BinarySearchTreeNode *right;  
10.     BinarySearchTreeNode(){  
11.         data = -1;  
12.         left = NULL;  
13.         right = NULL;  
14.     }  
15. };  
16.   
17. typedef class BinarySearchTreeNode bstNode;  
18. typedef bstNode *bstNodePoint;  
19.   
20. class BinarySearchTree{  
21.     bstNodePoint root;  
22. public:  
23.     BinarySearchTree(){root=NULL;}  
24.     virtual void add_Node_To_Tree(int value);  
25.     virtual void createTree(int *m, int len);  
26.     virtual bool search(int *v);  
27. };  

* BinarySearchTree.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "BinarySearchTree.h"  
2.   
3. bool BinarySearchTree::search(int *v) {  
4.     bstNodePoint currentNode = root;  
5.     if(root == NULL) {  
6.         return false;  
7.     } else {  
8.         int loopCount = 0;  
9.         bool isDone = false;  
10.         bool isFound = false;  
11.         while(!isDone) {  
12.             loopCount++;  
13.             if(currentNode->data > *v) { // 往左子樹移動  
14.                 if(currentNode->left == NULL) {  
15.                     isFound = false;  
16.                     isDone = true;  
17.                 } else {  
18.                     currentNode = currentNode->left;  
19.                 }  
20.             } else if(currentNode->data < *v) { // 往右子樹移動  
21.                 if(currentNode->right == NULL) {  
22.                     isFound = false;  
23.                     isDone = true;  
24.                 } else {  
25.                     currentNode = currentNode->right;  
26.                 }  
27.             } else {                  
28.                 isFound = true;  
29.                 isDone = true;  
30.             }  
31.         }  
32.         cout << "共搜尋 " << loopCount << "次!" << endl;  
33.         return isFound;  
34.     }  
35. }  
36.   
37. void BinarySearchTree::createTree(int *matrix, int len) {  
38.     for(int i=0; i
39.         this->add_Node_To_Tree(matrix[i]);  
40.     }  
41. }  
42.   
43. void BinarySearchTree::add_Node_To_Tree(int value) {  
44.     bstNodePoint currentNode;  
45.     bstNodePoint newnode;  
46.     newnode = new bstNode();  
47.     newnode->left = NULL;  
48.     newnode->right = NULL;  
49.     newnode->data = value;  
50.     if(root == NULL) {  
51.         root = newnode;  
52.     } else {  
53.         currentNode = root;  
54.         int flag=0; // 用來紀錄是否插入新的節點  
55.         while(!flag) {  
56.             if(currentNode->data > value) { // 往左子樹移動  
57.                 if(currentNode->left == NULL) {  
58.                     currentNode->left = newnode;  
59.                     flag = 1;  
60.                 } else {  
61.                     currentNode  = currentNode->left;  
62.                 }  
63.             } else if(currentNode->data < value){ //往右子樹移動  
64.                 if(currentNode->right == NULL) {  
65.                     currentNode->right = newnode;  
66.                     flag = 1;  
67.                 } else {  
68.                     currentNode = currentNode->right;  
69.                 }  
70.             }  else { // 二元搜尋樹沒有相同值的節點  
71.                 flag = 1;  
72.             }  
73.         }  
74.     }  
75. }  

* 呼叫演算法代碼 :

view plaincopy to clipboardprint?

1. void ch06_06(bool b) {  
2.     if(b) {  
3.         int data[] = {7, 4, 1, 5, 13, 8, 11, 12, 15, 9, 2};  
4.         BinarySearchTree bsTree;  
5.         bsTree.createTree(data, 11);  
6.         int sv = 0;  
7.         while(sv != -1) {  
8.             cout << "請輸入搜尋值 (輸入-1離開) : ";  
9.             cin >> sv;  
10.             if(bsTree.search(&sv)) {  
11.                 cout << "你要找的值 [" << sv << "] 有找到 !" << endl;  
12.             } else {  
13.                 cout << "你要找的值 [" << sv << "] 沒有找到 ==\"" << endl;  
14.             }  
15.         }  
16.     }  
17. }  

執行結果 :

請輸入搜尋值 (輸入-1離開) : 11
共搜尋 4次!
你要找的值 [11] 有找到 !
請輸入搜尋值 (輸入-1離開) : 8
共搜尋 3次!
你要找的值 [8] 有找到 !
請輸入搜尋值 (輸入-1離開) : 6
共搜尋 3次!
你要找的值 [6] 沒有找到 =="
請輸入搜尋值 (輸入-1離開) : -1 <離開>
共搜尋 3次!
你要找的值 [-1] 沒有找到 =="

補充說明 :
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元運算樹進階研究 - 二元排序樹
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的走訪
* Wiki - 二元搜尋樹

二叉排序樹的查找過程和次優二元樹類似，通常採取二叉鏈表作為二叉排序樹的存儲結構。中序遍歷二叉排序樹可得到一個關鍵字的有序序列，一個無序序列可以通過構造一棵二叉排序樹變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。每次插入的新的結點都是二叉排序樹上新的葉子結點，在進行插入操作時，不必移動其它結點，只需改動某個結點的指針，由空變為非空即可。搜索,插入,刪除的複雜度等於樹高，期望O(logn),最壞O(n)(數列有序,樹退化成線性表).

This message was edited 5 times. Last update was at 25/04/2010 15:18:12