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

標籤

2010年10月19日 星期二

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

前言 : 
雖然我們把樹化成二元樹可以減少空間浪費由 2/3 降低到 1/2, 但是如果仔細觀察我們使用鏈結串列建立 n 節點二元樹, 實際上用來指向左右兩節點的指標只有n-1 個鏈結, 另外的 n+1 個指標都是空鏈結. 
所謂的 "引線二元樹" (Thread Binary Tree) 就是把這些空的鏈結加以利用, 再指到樹的其它節點, 而這些鏈結就稱為 "引線" (Thread), 而這棵樹就稱為引線二元樹. 至於將二元樹轉換成引線二元樹的步驟如下 : 

1. 先將二元樹經由中序走訪方式依序排出, 並將所有空鏈結改成引線.
2. 如果引線鏈結是指向該節點的左鏈結, 則將該鏈結指到中序走訪順序下的前一個節點.
3. 如果引線鏈結是指向該節點的右鏈結, 則將該鏈結指到中序走訪順序下的後一個節點.
4. 指像一個空節點, 並將此空節點的右鏈結指向自己, 而空節點的左子樹是此引線二元樹.


引線二元樹的基本結構如下 : 
 

和鏈結串列所建立的二元樹不同在於, 為了區分正常指標或引線而加入的兩個欄位 LBIT 及 RBIT. 其中: 

* 如果 LCHILD 為正常指標, 則 LBIT=1
* 如果 LCHILD 為引線, 則 LBIT=0
* 如果 RCHILD 為正常指標, 則 RBIT=1
* 如果 RCHILD 為引線, 則 RBIT=0


二元樹轉引線二元樹 : 
接著我們練習如何將下圖二元樹轉為引線二元樹 : 
 
步驟 : 
1. 以中序追蹤二元樹 : HDIBEAFCG 
2. 找出相對應的引線二元樹, 並按照中序走訪求得下圖 : 
 

以下整理出來使用引線二元樹的優缺點 : 
優點 : 

1. 在二元樹中作中序走訪, 不需要使用堆疊處理, 但一般二元樹需要.
2. 由於充分使用空鏈結, 所以避免了鏈結閒置浪費的情形. 另外中序走訪時速度也較快.
3. 任一節點都容易找出它中序後繼者與中序前行者, 在中序走訪可以不使用堆疊或遞迴.

缺點 : 

1. 在加入或刪除節點時的速度較一般二元樹慢.
2. 引線子樹間不能共享.


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

  1. #include   
  2.   
  3. using namespace std;  
  4.   
  5. class ThreadBTreeNode{  
  6. public:  
  7.     int data;  
  8.     int left_Thread;  
  9.     int right_Thread;  
  10.     class ThreadBTreeNode *leftNode;  
  11.     class ThreadBTreeNode *rightNode;  
  12. };  
  13.   
  14. typedef class ThreadBTreeNode tbtNode;  
  15. typedef tbtNode *tbtNodePoint;  
  16.   
  17. class ThreadBTree{  
  18.     tbtNodePoint root;  
  19. public:  
  20.     ThreadBTree(){root = NULL;}  
  21.     virtual void Add_Node_To_Tree(int value);  
  22.     virtual void CreateTree(int *m, int len);  
  23.     virtual void Inorder(); /*中序走訪二元樹*/  
  24. };  
* ThreadBTree.cpp 代碼 : 

  1. #include "ThreadBTree.h"  
  2.   
  3. void ThreadBTree::Inorder(){  
  4.     tbtNodePoint tempNode = root;  
  5.     do{  
  6.         if(tempNode->right_Thread == 0)  
  7.             tempNode = tempNode->rightNode;  
  8.         else {  
  9.             tempNode = tempNode->rightNode;  
  10.             while(tempNode->left_Thread !=0)  
  11.                 tempNode = tempNode->leftNode;  
  12.         }  
  13.         if(tempNode != root)  
  14.             cout << "[" << tempNode->data << "] ";  
  15.     }while(tempNode != root);  
  16.     cout << endl;  
  17. }  
  18.   
  19. void ThreadBTree::CreateTree(int *m, int len) {  
  20.     for(int i=0; i
  21.         this->Add_Node_To_Tree(m[i]);  
  22. }  
  23.   
  24. void ThreadBTree::Add_Node_To_Tree(int value){  
  25.     tbtNodePoint newnode;  
  26.     tbtNodePoint previous;  
  27.     newnode = new  tbtNode;  
  28.     newnode->data = value;  
  29.     newnode->left_Thread = 0;  
  30.     newnode->right_Thread = 0;  
  31.     newnode->leftNode = NULL;  
  32.     newnode->rightNode = NULL;  
  33.     tbtNodePoint current;  
  34.     tbtNodePoint parent;  
  35.     int pos;  
  36.     // 設定引線二元樹的開頭節點  
  37.     if(root == NULL) {  
  38.         root = newnode;  
  39.         root->leftNode = root;  
  40.         root->rightNode = NULL;  
  41.         root->left_Thread = 0;  
  42.         root->right_Thread = 1;  
  43.         return;  
  44.     }  
  45.     // 設定開頭節點所指節點  
  46.     current = root->rightNode;  
  47.     if(current == NULL) {  
  48.         root->rightNode = newnode;  
  49.         newnode->leftNode = root;  
  50.         newnode->rightNode = root;  
  51.         return;  
  52.     }  
  53.     parent = root; // 父節點是開頭節點  
  54.     pos = 0// 設定二元樹中的行進方向  
  55.     while(current != NULL) {  
  56.         if(current->data > value) { // 往左節點  
  57.             if(pos != -1){  
  58.                 pos = -1;  
  59.                 previous = parent;  
  60.             }  
  61.             parent = current;  
  62.             if(current->left_Thread == 1)   
  63.                 current = current->leftNode;  
  64.             else   
  65.                 current = NULL;  
  66.         } else {  // 往右節點  
  67.             if(pos != 1) {  
  68.                 pos = 1;  
  69.                 previous = parent;  
  70.             }  
  71.             parent = current;  
  72.             if(current->right_Thread == 1)  
  73.                 current = current->rightNode;  
  74.             else  
  75.                 current = NULL;  
  76.         }  
  77.     }  
  78.     if(parent->data > value) {  
  79.         parent->leftNode = newnode;  
  80.         parent->left_Thread = 1;  
  81.         newnode->leftNode = previous;  
  82.         newnode->rightNode = parent;  
  83.     } else {  
  84.         parent->rightNode = newnode;  
  85.         parent->right_Thread = 1;  
  86.         newnode->leftNode = parent;  
  87.         newnode->rightNode = previous;  
  88.     }  
  89. }  
* 呼叫演算法代碼 : 

  1. void ch06_07(bool b) {  
  2.     if(b) {  
  3.         ThreadBTree tBTree;  
  4.         tBTree.Add_Node_To_Tree(0); // 建立Null Node  
  5.         int sv = 0;  
  6.         while(sv != -1) {  
  7.             cout << "請輸入值 (輸入-1離開):" ;  
  8.             cin >> sv;  
  9.             if(sv!=-1) {  
  10.                 tBTree.Add_Node_To_Tree(sv);  
  11.             }  
  12.         }  
  13.         /*中序走法列印二元樹內容*/  
  14.         tBTree.Inorder();  
  15.     }  
  16. }  

執行結果 : 

請輸入值 (輸入-1離開):4
請輸入值 (輸入-1離開):2
請輸入值 (輸入-1離開):9
請輸入值 (輸入-1離開):3
請輸入值 (輸入-1離開):7
請輸入值 (輸入-1離開):1
請輸入值 (輸入-1離開):-1 <離開輸入>
[1] [2] [3] [4] [7] [9] <按中序走訪, 所以數字會依小到大排列>

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

沒有留言:

張貼留言

網誌存檔

關於我自己

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