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

前言 : 
雖然我們把樹化成二元樹可以減少空間浪費由 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 代碼 : 

view plaincopy to clipboardprint?

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

view plaincopy to clipboardprint?

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

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

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] <按中序走訪, 所以數字會依小到大排列>

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