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

標籤

2010年10月10日 星期日

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

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

  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 代碼 : 
  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 代碼 : 
  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. }  
* 呼叫演算法代碼 : 
  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>

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

沒有留言:

張貼留言

網誌存檔