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

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

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

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

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

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

view plaincopy to clipboardprint?

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 代碼 : 

view plaincopy to clipboardprint?

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 = 1+ this->_getDepth(p->left);  
54.         int rd = 1+ this->_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. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

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]

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