[ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的走訪

前言 : 
二元樹的走訪 (Binary Tree Travel), 最簡單的說法就是 “拜訪樹中所有的節點各一次”, 並且在走訪後, 將樹中的資料轉化成線性關係. 其實二元樹的走訪, 並不像之前所提到的線性資料結構般單純, 就一個簡單按二元樹節點而言, 每個節點都可以區分成左右兩個分支, 請參考下面圖形, 所以共可以有 ABC, ACB, BAC etc 等6種走訪方式. 如果是依照二元樹特性, 一律由左向右, 那只會剩下三種走訪方式, 分別是 BAC, ABC, BCA 三種 : 
 

我們通常把這三種方式的命名與規則如下 : 

- 中序走訪 (BAC, Inorder) : 左子樹 > 樹根 > 右子樹
- 前序走訪 (ABC, Preorder) : 樹根 > 左子樹 > 右子樹
- 後序走訪 (BCA, Postorder) : 左子樹 > 右子樹 > 樹根

對於這三種走訪方式, 只需要記得樹根的位置就不會前中後序搞混. 例如中序法即樹根在中間, 前序法則是樹根在前面以此類推. 接著以底下的二元樹為範例針對這三種走訪方式作介紹. 
 

中序走訪 : 
中序走訪的順序為 : 左子樹 > 樹根 > 右子樹 
就是延著二元樹的左子樹一直往下, 直到無法前進後退回父節點, 再往右節點一直往下, 如果右子樹也走完就退回上層的左節點, 再重複左> 中 > 右的順序走訪. 以上面二元樹為例的中序走訪為 : D > B > E > A > C > F. 中序走訪的遞迴演算法如下 : 

view plaincopy to clipboardprint?

1. void Inorder (btree ptr) {  
2.     if(ptr!= NULL) {  
3.         Inorder(ptr->left);    /*走訪左子樹*/  
4.         cout << ptr->data;  /*走訪列印樹根*/  
5.         Inorder(ptr->right);  /*走訪右子樹*/  
6.     }  
7. }  

前序走訪 : 
前序走訪的順序為 : 樹根 > 左子樹 > 右子樹 
前序走訪就是從根節點開始處理, 根節點處理完後往左子樹走, 直到無法前進再處理右子樹. 以上面二元樹為例的前序走訪為 : A > B > D > E > C >F. 前序走訪的遞迴演算法如下 : 

view plaincopy to clipboardprint?

1. void Inorder (btree ptr) {  
2.     if(ptr!= NULL) {  
3.         cout << ptr->data;  /*走訪列印樹根*/  
4.         Inorder(ptr->left);    /*走訪左子樹*/          
5.         Inorder(ptr->right);  /*走訪右子樹*/  
6.     }  
7. }  

後序走訪 : 
後序走訪的順序為 : 左子樹 > 右子樹 > 樹根 
後序走訪和前序走訪的方法相反, 它是先把左子樹和右子樹的節點處理完後才處理樹根. 以上面二元樹為例的後序走訪為 : D > E > B > F > C >A. 後序走訪的遞迴演算法如下 : 

view plaincopy to clipboardprint?

1. void Inorder (btree ptr) {  
2.     if(ptr!= NULL) {  
3.         Inorder(ptr->left);    /*走訪左子樹*/          
4.         Inorder(ptr->right);  /*走訪右子樹*/  
5.         cout << ptr->data;  /*走訪列印樹根*/  
6.     }  
7. }  

決定為一二元樹 : 
在二元樹的三種走法中, 如果有中序與前序的走訪結果或中序與後序的走訪結果, 就可以藉由這些結果求得唯一的二元樹. 不過如果只具備前序與後序的走訪結果並無法決定唯一的二元樹. 請參考下面範例 : 
範例一 : 
考慮我們有一二元樹, 中序走訪為 : BAEDGF, 前序走訪為ABDEFG, 請畫出此唯一二元樹 : 
 

範例代碼 : 
* 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 void inorder();  /*中序走訪二元樹*/  
28.     virtual void preorder();  /*前序走訪二元樹*/  
29.     virtual void postorder();  /*後序走訪二元樹*/  
30.       
31. protected:  
32.     virtual void _inorder(lsbtNodePoint p);  
33.     virtual void _preorder(lsbtNodePoint p);  
34.     virtual void _postorder(lsbtNodePoint p);     
35. };  

* 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. void LSBinaryTree::inorder() {  
36.     this->_inorder(this->rootNode);  
37. }  
38.   
39. void LSBinaryTree::_inorder(lsbtNodePoint p){  
40.     if(p != NULL) {  
41.         if(p->left != NULL)   
42.             this->_inorder(p->left);  
43.         cout << "[" << p->data << "] ";  
44.         if(p->right != NULL)   
45.             this->_inorder(p->right);   
46.     }   
47. }  
48.   
49. void LSBinaryTree::preorder() {  
50.     this->_preorder(this->rootNode);  
51. }  
52.   
53. void LSBinaryTree::_preorder(lsbtNodePoint p) {  
54.     if(p!=NULL) {  
55.         cout << "[" << p->data << "] ";  
56.         if(p->left!=NULL)  
57.             _preorder(p->left);  
58.         if(p->right!=NULL)  
59.             _preorder(p->right);  
60.     }  
61. }  
62.   
63. void LSBinaryTree::postorder() {  
64.     this->_postorder(this->rootNode);  
65. }  
66.   
67. void LSBinaryTree::_postorder(lsbtNodePoint p){  
68.     if(p!=NULL){  
69.         if(p->left!=NULL)  
70.             _postorder(p->left);  
71.         if(p->right!=NULL)  
72.             _postorder(p->right);  
73.         cout << "[" << p->data << "] ";  
74.     }  
75. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void ch06_03(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 << "中序走訪: ";  
14.         btree.inorder();  
15.         cout <<  endl;  
16.         cout << "前序走訪: ";  
17.         btree.preorder();  
18.         cout << endl;  
19.         cout << "後序走訪: ";  
20.         btree.postorder();  
21.         cout << endl;  
22.     }  
23. }  

執行結果 : 

請輸入節點值(輸入-1離開): 7
請輸入節點值(輸入-1離開): 4
請輸入節點值(輸入-1離開): 1
請輸入節點值(輸入-1離開): 5
請輸入節點值(輸入-1離開): 16
請輸入節點值(輸入-1離開): 8
請輸入節點值(輸入-1離開): 11
請輸入節點值(輸入-1離開): 12
請輸入節點值(輸入-1離開): 15
請輸入節點值(輸入-1離開): 9
請輸入節點值(輸入-1離開): 2
請輸入節點值(輸入-1離開): -1 <離開輸入>
中序走訪: [1] [2] [4] [5] [7] [8] [9] [11] [12] [15] [16]
前序走訪: [7] [4] [1] [2] [5] [16] [8] [11] [9] [12] [15]
後序走訪: [2] [1] [5] [4] [9] [15] [12] [11] [8] [16] [7]

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