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

2010年10月15日 星期五

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


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


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

範例代碼 :
* BinarySearchTree.h 代碼 :
  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 代碼 :
  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. }  
* 呼叫演算法代碼 :
  1. void ch06_06(bool b) {  
  2.     if(b) {  
  3.         int data[] = {741513811121592};  
  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

沒有留言:

張貼留言

網誌存檔