[ 資料結構 小學堂 ] 樹狀結構導論 : 二元運算樹

前言 : 
一般的算數式也可以轉換成二元運算樹 (Binary Expression Tree) 的方式, 建立的方法可以根據以下兩種規則 : 

1. 考慮算術式中運算子的結合性與優先權, 再適當的加上括號.
2. 再由最內層的括號逐步向外, 利用運算子當樹根, 左邊運算元當左子樹, 右邊運算元當右子樹, 其中優先權最低的運算子作為此二元運算樹的樹根.

現在考慮運算式 : A-B*(-C+-3) : 

> A-B*(-C+-3)
> (A-(B*((-C)+(-3)))) <根據運算子的結合性與優先權, 加上適當括號>
> 二元運算樹如下所示 : <將優先權最低的運算子作為二元運算樹的樹根>

接著便可以藉由二元運算樹進行前序與後序走訪得到此運算式的前序法與後序法. 

範例代碼 : 
這裡以鏈結串列來實現二元運算樹, 詳細代碼如下 : 
* OperBTreeInLS.h 代碼 : 

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4.   
5. class OperBTreeNode{  
6. public:  
7.     int data;  
8.     class OperBTreeNode *left;  
9.     class OperBTreeNode *right;  
10.     OperBTreeNode(){  
11.         data = -1;  
12.         left = NULL;  
13.         right = NULL;  
14.     }  
15. };  
16.   
17. typedef class OperBTreeNode obtNode;  
18. typedef obtNode *obtNodePoint;  
19.   
20. class OperBTreeInLS{  
21.     obtNodePoint root;  
22. public:   
23.     OperBTreeInLS(){  
24.         root = NULL;  
25.     }  
26.     virtual void inOrder(); /*中序走法*/  
27.     virtual int answer();  /*計算運算式二元樹的結果*/  
28.     virtual void add_Node_To_Tree(int value);  
29.     virtual obtNodePoint create(char seq[100], int index, int arraySize);  
30.     virtual void cleanAll(); /*清除二元樹設定*/  
31.   
32. protected:  
33.     virtual void _cleanAll(obtNodePoint ptr);     
34.     virtual void _inOrder(obtNodePoint ptr);  
35.     /*判斷運算式如何運算的方法宣告*/  
36.     virtual int _condition(char opr, int num1, int num2);     
37.     virtual int _answer(obtNodePoint ptr);  
38. };  

* OperBTreeInLS.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "OperBTreeInLS.h"  
2.   
3. int OperBTreeInLS::answer(){  
4.     return _answer(root);  
5. }  
6.   
7. int OperBTreeInLS::_answer(obtNodePoint ptr){  
8.     if(ptr != NULL) {  
9.         int firstNumber = 0;  
10.         int secondNumber = 0;  
11.         if(ptr->left == NULL && ptr->right ==NULL) {  
12.             return ptr->data - 48;  //ASCII char '0' = 48  
13.         } else {  
14.             firstNumber = _answer(ptr->left);  
15.             secondNumber = _answer(ptr->right);  
16.             return _condition((char)ptr->data, firstNumber, secondNumber);  
17.         }  
18.     }  
19.     return -1;  
20. }  
21.   
22. void OperBTreeInLS::add_Node_To_Tree(int value) {  
23.     /*Not implement here*/  
24. }  
25.   
26. obtNodePoint OperBTreeInLS::create(char seq[], int index, int arraySize) {  
27.     obtNodePoint tmpPoint;  
28.     if(seq[index]=='0' || index >= arraySize) {  
29.         return NULL;  
30.     } else {  
31.         tmpPoint = new obtNode;  
32.         if(root == NULL)   
33.             root = tmpPoint;  
34.         tmpPoint->data = seq[index];  
35.         tmpPoint->left = NULL;  
36.         tmpPoint->right = NULL;  
37.         // 建立左子樹  
38.         tmpPoint->left = create(seq, index*2, arraySize);  
39.         // 建立右子樹  
40.         tmpPoint->right = create(seq, index*2+1, arraySize);  
41.         return tmpPoint;  
42.     }  
43. }  
44.   
45. int OperBTreeInLS::_condition(char opr, int num1, int num2) {  
46.     switch(opr) {  
47.         case '*': return (num1 * num2);  
48.         case '/': return (num1 / num2);  
49.         case '+': return (num1 + num2);  
50.         case '-': return (num1 - num2);  
51.         case '%': return (num1 % num2);  
52.     }  
53.     return -1;  
54. }  
55.   
56. void OperBTreeInLS::inOrder() {  
57.     this->_inOrder(this->root);  
58. }  
59.   
60. void OperBTreeInLS::_inOrder(obtNodePoint ptr) {  
61.     if(ptr != NULL) {  
62.         this->_inOrder(ptr->left);  
63.         cout << "[" << (char)ptr->data << "] ";  
64.         this->_inOrder(ptr->right);  
65.     }  
66. }  
67.   
68. void OperBTreeInLS::cleanAll() {  
69.     cout << "Clean " ;  
70.     this->_cleanAll(this->root);  
71.     cout << endl;  
72.     this->root = NULL;  
73. }  
74.   
75. void OperBTreeInLS::_cleanAll(obtNodePoint ptr){  
76.     if(ptr!=NULL) {  
77.         /*後序走法*/  
78.         _cleanAll(ptr->left);  
79.         _cleanAll(ptr->right);  
80.         cout  << (char)ptr->data << " " ;  
81.         delete ptr;  
82.     }  
83. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void ch06_04(bool b) {  
2.     if(b) {  
3.         // 第一筆運算式  
4.         char information1[] = {' ', '+', '*', '%', '6', '3', '9', '5'};  
5.         char information2[] = {' ', '+', '+', '+', '*', '%', '/', '*', '1', '2', '3', '2', '6', '3', '2', '2'};  
6.         OperBTreeInLS operBTree;  
7.         operBTree.create(information1, 1, 8);  
8.         cout << "===二元運算樹範例(一)===" << endl;  
9.         cout << "轉成中序運算式: ";  
10.         operBTree.inOrder();  
11.         cout << endl;  
12.         cout << "此二元運算樹結果為:" << operBTree.answer() << endl;  
13.         operBTree.cleanAll();  
14.         operBTree.create(information2, 1, 16);  
15.         cout << "===二元運算樹範例(二)===" << endl;  
16.         cout << "轉成中序運算式: ";  
17.         operBTree.inOrder();  
18.         cout << endl;  
19.         cout << "此二元運算樹結果為:" << operBTree.answer() << endl;  
20.         operBTree.cleanAll();  
21.     }  
22. }  

執行結果 : 

===二元運算樹範例(一)===
轉成中序運算式: [6] [*] [3] [+] [9] [%] [5]
此二元運算樹結果為:22
Clean 6 3 * 9 5 % +
===二元運算樹範例(二)===
轉成中序運算式: [1] [*] [2] [+] [3] [%] [2] [+] [6] [/] [3] [+] [2] [*] [2]
此二元運算樹結果為:9
Clean 1 2 * 3 2 % + 6 3 / 2 2 * + +

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

ASCII（American Standard Code for Information Interchange，美國資訊互換標準代碼）是基於拉丁字母的一套電腦編碼系統。它主要用於顯示現代英語和其他西歐語言。它是現今最通用的單位元組編碼系統，並等同於國際標準ISO/IEC 646。