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

標籤

2010年10月14日 星期四

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

前言 : 
在二元樹的應用中, 常見的有二元排序樹, 二元搜尋樹, 引線二元樹等, 這裡將會針對二元排序樹進行介紹. 

二元排序樹 : 
事實上, 二元樹是一種很好的排序應用模式, 因為在建立二元樹的同時, 資料已經經過初步的比較判斷, 並依照二元樹的建立規則來存放資料. 規則如下 : 

- 第一個輸入資料當作此二元樹的樹根.
- 之後的資料以遞迴的方式與樹根進行比較, 小於樹根置於左子樹, 大於樹根置於右子樹.

從上面的規則我們知道, 左子樹的值一定小於樹根, 而右子樹的值一定大於樹根. 因此只要利用 “中序走訪” 方式就可以得到由小到大排序好的資料, 如果是想求由大到小排列, 可將最後結果至於堆疊再使用堆疊pop 出來. 以下是簡單的示範 : 
 
根據上面範例建立完的二元樹後, 經由中序走訪可得 16, 25, 27, 32, 35 並按照由小到大排列. 因為在輸入資料的同時就開始建立二元樹, 所以在完成資料輸入並建立完二元樹後, 經由中序走訪便可以很輕鬆的完成排序. 

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

  1. #include   
  2.   
  3. using namespace std;  
  4.   
  5. class LSBinaryTreeNode{  
  6. public:  
  7.     int data;  
  8.     class LSBinaryTreeNode *left;  
  9.     class LSBinaryTreeNode *right;  
  10.     LSBinaryTreeNode(){  
  11.         data = -1;  
  12.         left = NULL;  
  13.         right = NULL;  
  14.     }  
  15. };  
  16.   
  17. typedef class LSBinaryTreeNode lsbtNode;  
  18. typedef lsbtNode *lsbtNodePoint;  
  19.   
  20. class LSBinaryTree{  
  21.     lsbtNodePoint rootNode;  
  22. public:  
  23.     LSBinaryTree(){  
  24.         rootNode = NULL;  
  25.     }  
  26.     virtual void add_Node_To_Tree(int value);  
  27.     virtual int getLevel(); /*獲取此二元樹的Level/階度*/  
  28.     virtual int getNodeCount();  /*獲取此二元樹的設定節點個數*/  
  29.     virtual void inorder();  /*中序走訪二元樹*/  
  30.     virtual void preorder();  /*前序走訪二元樹*/  
  31.     virtual void postorder();  /*後序走訪二元樹*/  
  32.       
  33. protected:  
  34.     virtual void _inorder(lsbtNodePoint p);  
  35.     virtual void _preorder(lsbtNodePoint p);  
  36.     virtual void _postorder(lsbtNodePoint p);  
  37.     virtual int _getNodeCount(lsbtNodePoint p);  
  38.     virtual int _getDepth(lsbtNodePoint p);   
  39. };  
* LSBinaryTree.cpp 代碼 : 

  1. #include "LSBinaryTree.h"  
  2.   
  3. void LSBinaryTree::add_Node_To_Tree(int value) {  
  4.     lsbtNodePoint currentNode;  
  5.     lsbtNodePoint newnode;  
  6.     int flag=0// 用來紀錄是否插入新的節點  
  7.     newnode = (lsbtNodePoint)malloc(sizeof(lsbtNode));  
  8.     newnode->data = value;  
  9.     newnode->left = NULL;  
  10.     newnode->right = NULL;  
  11.     if(this->rootNode == NULL){  
  12.         rootNode = newnode;  
  13.     } else {  
  14.         currentNode = this->rootNode;  
  15.         while(!flag) {  
  16.             if(value<=currentNode->data) { // 往左子樹  
  17.                 if(currentNode->left == NULL) {  
  18.                     currentNode->left = newnode;  
  19.                     flag = 1;  
  20.                 } else {  
  21.                     currentNode = currentNode->left;  
  22.                 }  
  23.             } else { // 往右子樹  
  24.                 if(currentNode->right == NULL){  
  25.                     currentNode->right = newnode;  
  26.                     flag = 1;  
  27.                 } else {  
  28.                     currentNode = currentNode->right;  
  29.                 }  
  30.             }  
  31.         }  
  32.     }  
  33. }  
  34.   
  35. int LSBinaryTree::getLevel() {  
  36.     return _getDepth(this->rootNode);  
  37. }  
  38.   
  39. int LSBinaryTree::getNodeCount() {  
  40.     return _getNodeCount(this->rootNode);  
  41. }  
  42.   
  43. int LSBinaryTree::_getNodeCount(lsbtNodePoint p){  
  44.     if(p!=NULL) {  
  45.         return this->_getNodeCount(p->left) + this->_getNodeCount(p->right) + 1;  
  46.     } else {  
  47.         return 0;  
  48.     }  
  49. }  
  50.   
  51. int LSBinaryTree::_getDepth(lsbtNodePoint p){  
  52.     if(p!=NULL) {  
  53.         int ld = 1this->_getDepth(p->left);  
  54.         int rd = 1this->_getDepth(p->right);  
  55.         if(ld>rd) {  
  56.             return ld;  
  57.         } else {  
  58.             return rd;  
  59.         }  
  60.     } else {  
  61.         return 0;  
  62.     }  
  63. }  
  64.   
  65. void LSBinaryTree::inorder() {  
  66.     this->_inorder(this->rootNode);  
  67. }  
  68.   
  69. void LSBinaryTree::_inorder(lsbtNodePoint p){  
  70.     if(p != NULL) {  
  71.         if(p->left != NULL)   
  72.             this->_inorder(p->left);  
  73.         cout << "[" << p->data << "] ";  
  74.         if(p->right != NULL)   
  75.             this->_inorder(p->right);   
  76.     }   
  77. }  
  78.   
  79. void LSBinaryTree::preorder() {  
  80.     this->_preorder(this->rootNode);  
  81. }  
  82.   
  83. void LSBinaryTree::_preorder(lsbtNodePoint p) {  
  84.     if(p!=NULL) {  
  85.         cout << "[" << p->data << "] ";  
  86.         if(p->left!=NULL)  
  87.             _preorder(p->left);  
  88.         if(p->right!=NULL)  
  89.             _preorder(p->right);  
  90.     }  
  91. }  
  92.   
  93. void LSBinaryTree::postorder() {  
  94.     this->_postorder(this->rootNode);  
  95. }  
  96.   
  97. void LSBinaryTree::_postorder(lsbtNodePoint p){  
  98.     if(p!=NULL){  
  99.         if(p->left!=NULL)  
  100.             _postorder(p->left);  
  101.         if(p->right!=NULL)  
  102.             _postorder(p->right);  
  103.         cout << "[" << p->data << "] ";  
  104.     }  
  105. }  
* 呼叫演算法代碼 : 

  1. void ch06_05(bool b) {  
  2.     if(b) {  
  3.         int value=0;  
  4.         LSBinaryTree btree;  
  5.         while(true) {  
  6.             cout << "請輸入節點值(輸入-1離開): ";  
  7.             cin >> value;  
  8.             if(value == -1)   
  9.                 break;  
  10.             else  
  11.                 btree.add_Node_To_Tree(value);  
  12.         }  
  13.         cout << "中序走訪: ";  
  14.         btree.inorder();  
  15.         cout <<  endl;  
  16.     }  
  17. }  

執行結果 : 

請輸入節點值(輸入-1離開): 32
請輸入節點值(輸入-1離開): 25
請輸入節點值(輸入-1離開): 16
請輸入節點值(輸入-1離開): 35
請輸入節點值(輸入-1離開): 27
請輸入節點值(輸入-1離開): -1 <離開輸入>
中序走訪: [16] [25] [27] [32] [35]


補充說明 : 
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的走訪

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!