表達式樹:
葉子是操作數，其余結點為操作符，是二叉樹的其中一種應用
====================我是分割線======================
一棵表達式樹如下圖：
1 struct TreeNode {
2 object element;
3 TreeNode* leftChild;
4 TreeNode* rightChild;
5 };
用後綴表達式構建一棵表達式樹：
思路：（與後綴表達式計算四則運算結構相似）
1. 一一讀入輸入字符串
2. 若是操作數，則初始化為結點後入棧
3. 若是操作符，則從棧中彈出兩個結點（新結點的左右子樹），與剛讀入的操作符結合起來構建新結點，然後入棧
重復1~3，最後棧內有一棵表達式樹的root結點
code實現：
1 #include<iostream>
2 #include <string>
3 #include<stack>
4
5 using namespace std;
6
7 struct TreeNode{
8 char element;
9 TreeNode* leftChild;
10 TreeNode* rightChild;
11 TreeNode(char ch, TreeNode* l, TreeNode* r) {
12 element = ch;
13 leftChild = l;
14 rightChild = r;
15 }
16 TreeNode() {
17 element = '0';
18 leftChild = 0;
19 rightChild = 0;
20 }
21 };
22
23 //測試函數——輸出樹
24 void drawTree(TreeNode* root, bool infix) {
25 if (infix) {
26 if (root) {
27 //中序遍歷
28 drawTree(root->leftChild, infix);
29 cout << root->element;
30 drawTree(root->rightChild, infix);
31 }
32 else return;
33 }
34 else {
35 if (root) {
36 //後序遍歷
37 drawTree(root->leftChild, infix);
38 drawTree(root->rightChild, infix);
39 cout << root->element;
40 }
41 else return;
42 }
43 }
44
45 int main() {
46 string input;
47 stack<TreeNode> expressionTree;
48 while (cin >> input) {
49 if (input == "0") break;
50 for (int i = 0; i < input.size();) {
51 char ch = input[i++];
52 if (ch >= '0' && ch <= '9') {
53 TreeNode leaves;
54 leaves.element = ch;
55 expressionTree.push(leaves);
56 }
57 else {
58 //出棧，成為新結點右子樹
59 TreeNode* right = new TreeNode(expressionTree.top().element, expressionTree.top().leftChild, expressionTree.top().rightChild);
60 expressionTree.pop();
61
62 ////出棧，成為新結點左子樹
63 TreeNode* left = new TreeNode(expressionTree.top().element, expressionTree.top().leftChild, expressionTree.top().rightChild);
64 expressionTree.pop();
65
66 //新結點入棧
67 TreeNode leave(ch, left, right);
68 expressionTree.push(leave);
69 }
70 }
71 TreeNode* root = &expressionTree.top();
72 expressionTree.pop();
73 drawTree(root, true);
74 }
75 return 0;
76 }
77
78 //NULL 與 0 的概念
局限性：
1. 假設所有輸入合法，無空格等非法符號輸入
2. 測試輸出函數不能還原優先級，12+3* 的表達式樹測試輸出將是 1+2*3，而並非（1+2）*3，如果需要，可以在結構體中再加上一個優先級判斷，若子結點的操作符優先級小於父結點，則輸出時子樹的表達式需要最後要整體放到一個括號內。
一些bugs:
關於NULL、0 和 nullptr的學習：
1. NULL是宏
2. C中對於NULL的定義為 #define NULL ((void *)0)
3. C++中對於NULL的定義為0
#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void *)0)
#endif
4. C++11中對於nullptr的定義
1 const
2 class nullptr_t
3 {
4 public:
5 template<class T>
6 inline operator T*() const
7 { return 0; }
8
9 template<class C, class T>
10 inline operator T C::*() const
11 { return 0; }
12
13 private:
14 void operator&() const;
15 } nullptr = {};
5. 由於C++中的定義，在重載函數時容易出錯
1 //NULL 0 nullptr
2 #include <iostream>
3 #include <stdio.h>
4
5 using namespace std;
6
7 int f(void* ptr) {
8 return 2;
9 }
10
11 int f(int num) {
12 return 3;
13 }
14
15 int main() {
16 int result1 = f(0);
17 //int result2 = f(NULL);
18 int result3 = f(nullptr);
19 cout << "result1 = " << result1 << endl;
20 //cout << "result2 = " << result2 << endl;
21 cout << "result3 = " << result3 << endl;
22 return 0;
23 }
當我把17行的注釋符去掉時：編譯錯誤
最後運行的結果如下：
說明C++11標准中，nullptr的調用在重載時不會又歧義，而0則會在重載時調用int形參的函數
在C++中，可以的話，盡量用nullptr為空指針賦值
文章推薦：
http://www.cppblog.com/airtrack/archive/2012/09/16/190828.html
