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

標籤

2010年10月11日 星期一

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

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

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

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

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

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

  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. 前序走訪的遞迴演算法如下 : 

  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. 後序走訪的遞迴演算法如下 : 

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

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

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

  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]


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

沒有留言:

張貼留言

網誌存檔

關於我自己

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