[ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式 - 以鏈結串列表式

前言 : 
所謂二元樹的串列表示法就是利用鏈結串列來儲存二元樹, 也就是利用動態記憶體及指標的方式來建立二元樹. 其節點宣告如下 : 

view plaincopy to clipboardprint?

1. class LSBinaryTreeNode{  
2. public:  
3.     int data;  
4.     class LSBinaryTreeNode *left;  
5.     class LSBinaryTreeNode *right;  
6.     LSBinaryTreeNode(){  
7.         data = -1;  
8.         left = NULL;  
9.         right = NULL;  
10.     }  
11. };  

範例代碼 : 
* 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. protected:  
30.     virtual int _getNodeCount(lsbtNodePoint p);  
31.     virtual int _getDepth(lsbtNodePoint p);  
32. };  

* 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. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void ch06_02(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 << ">>>你總共輸入 " << btree.getNodeCount() << " 個節點." << endl;  
14.         cout << ">>>該二元樹階度為 " << btree.getLevel() << endl;  
15.     }  
16. }  

執行結果 : 

請輸入節點值(輸入-1離開): 8
請輸入節點值(輸入-1離開): 1
請輸入節點值(輸入-1離開): 9
請輸入節點值(輸入-1離開): 3
請輸入節點值(輸入-1離開): 6
請輸入節點值(輸入-1離開): 2
請輸入節點值(輸入-1離開): -1 <離開輸入>
>>>你總共輸入 6 個節點. <上面共輸入6個節點>
>>>該二元樹階度為 4 <上面節點組成的二元樹, 階度為4>

根據輸入, 二元樹如下所示 :