[ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式

前言 : 
樹狀結構在程式中的建立與應用大多使用鏈結串列來處理, 因為鏈結串列的指標可以用來處理樹的子節點而且相當方便, 當變更子節點時只需改變指標即可. 此外當然也可以使用陣列這樣的連續記憶體來表示二元樹. 至於使用陣列或鏈結串列都各有利弊, 首先下面我們會使用陣列來建立與實作一個二元樹. 

二元樹的陣列表示法 : 
如果要使用一維陣列來儲存二元樹, 首先將二元樹想像成一個完滿二元樹, 而且第 K 階具有 2^(k-1) 個節點, 並且依序存放在此一維陣列. 首先先來看看使用一維陣列建立二元樹的表式方式即索引值的配置 : 
 

另外在建立二元樹的實例時必須遵守 “小於父節點的值放在左子節點, 大於父節點的值則放在右子節點” 的規則, 則我們可以保證左子樹的值一定完全小於樹根, 而右子樹的值一定大於樹根. 實現請參考下面範例代碼. 

範例代碼 : 
範例程式分別使用陣列與鏈結串列來將原始陣列的值依序放入二元樹 : 
* BTreeInLS.h 代碼 : 

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4.   
5. class BTreeInLSNode  {  
6. public:  
7.     int data; // 節點資料  
8.     class BTreeInLSNode *left, *right; // 節點左指標及右指標  
9.     BTreeInLSNode(){  
10.         data = -1;  
11.         left = NULL;  
12.         right = NULL;  
13.     }  
14. };  
15.   
16. typedef class BTreeInLSNode btmNode;  
17. typedef btmNode *btmNodePoint;  
18.   
19. class BTreeInLS{  
20.     btmNodePoint rootNode;  
21.     int level;  
22. public:  
23.     BTreeInLS(){  
24.         rootNode = NULL;  
25.         level = 0;  
26.     }  
27.     virtual void addNode(int v);  
28.     virtual void showData();  
29.     virtual int getLevel();  
30. protected:  
31.     virtual void _showNode(int level, int curLeve,  btmNodePoint np);  
32. };  

* BTreeInLS.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "BTreeInLS.h"  
2.   
3. void BTreeInLS::addNode(int v) {  
4.     /*Add node*/  
5.     if(rootNode == NULL) {  
6.         rootNode = new BTreeInLSNode;  
7.         rootNode->data = v;  
8.         rootNode->left = NULL;  
9.         rootNode->right = NULL;    
10.         level = 1;  
11.     } else {  
12.         btmNodePoint tmpPoint = rootNode;  
13.         btmNodePoint prevPoint;  
14.         int tmpLevel = 1;  
15.         int direction = -1; //0 is left, 1 is right  
16.         while(true) {  
17.             if(tmpPoint == NULL) {  
18.                 tmpPoint = new BTreeInLSNode;  
19.                 tmpPoint->data = v;  
20.                 tmpPoint->left = NULL;  
21.                 tmpPoint->right = NULL;  
22.                 if(tmpLevel>level)  
23.                     level = tmpLevel; //紀錄目前最高Level  
24.                 if(direction==0) {  
25.                     prevPoint->left = tmpPoint;  
26.                 } else {  
27.                     prevPoint->right = tmpPoint;  
28.                 }  
29.                 break;  
30.             } else if(tmpPoint->data < v) { // 往右子樹移動  
31.                 prevPoint = tmpPoint;  
32.                 tmpPoint = tmpPoint->right;  
33.                 tmpLevel++;  
34.                 direction = 1;  
35.             } else {  // 往左子樹移動  
36.                 prevPoint = tmpPoint;  
37.                 tmpPoint = tmpPoint->left;  
38.                 tmpLevel++;  
39.                 direction = 0;  
40.             }  
41.         }  
42.     }  
43. }  
44.   
45.   
46. void BTreeInLS::showData(){  
47.     for(int i=1; i<=level; i++) {  
48.         this->_showNode(i, 1, rootNode);  
49.         cout << endl;  
50.     }  
51. }  
52.   
53. void BTreeInLS::_showNode(int level, int curLevel, btmNodePoint np) {  
54.     if(level == curLevel) {  
55.         if(np!=NULL) {  
56.             cout << "[" << np->data << "] ";  
57.         } else {  
58.             cout << "[0] " ;  
59.         }  
60.     } else if(level> curLevel && np!= NULL) {  
61.         this->_showNode(level, curLevel+1, np->left);  
62.         this->_showNode(level, curLevel+1, np->right);  
63.     }  
64. }  
65.   
66. int BTreeInLS::getLevel(){  
67.     return level;  
68. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void ch06_01(bool b) {  
2.     if(b) {  
3.         int data[] = {0,6,3,5,9,7,8,4,2}; // 原始陣列  
4.         int bdata[16] = {0}; //存放二元樹陣列   
5.         BTreeInLS bTree;  
6.         cout << "原始陣列內容:" << endl;  
7.         for(int i=1; i<9; i++)  
8.             cout << "[" << data[i] << "] ";  
9.         cout << endl;  
10.         // 把原始陣列放進二元樹陣列  
11.         for(int i=1; i<9; i++) {           
12.             bTree.addNode(data[i]);  
13.             int level = 1;  
14.             for(;bdata[level]>0;) {  
15.                 if(data[i] > bdata[level]) //如果陣列的值大於樹根, 往右子樹比較  
16.                     level = level*2 + 1;  
17.                 else // 如果陣列的值小於等於樹根, 往左子樹比較  
18.                     level = level*2;  
19.             }  
20.             bdata[level] = data[i];  
21.         }  
22.         cout << "二元樹內容(陣列) :" << endl;  
23.         for(int i=1; i<16; i++)   
24.             cout << "[" << bdata[i] << "] " ;  
25.         cout << endl;  
26.         cout << "二元樹內容(鏈結串列):" << endl;  
27.         bTree.showData();  
28.     }  
29. }  

執行結果 : 

原始陣列內容:
[6] [3] [5] [9] [7] [8] [4] [2]
二元樹內容(陣列) :
[6] [3] [9] [2] [5] [7] [0] [0] [0] [4] [0] [0] [8] [0] [0]
二元樹內容(鏈結串列):
[6]
[3] [9]
[2] [5] [7] [0]
[0] [0] [4] [0] [0] [8]

補充說明 : 
* [ 資料結構 小學堂 ] 樹狀結構導論 : 樹
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式 - Java version