表达式树:
叶子是操作数，其余结点为操作符，是二叉树的其中一种应用
====================我是分割线======================
一棵表达式树如下图：
若是对它做中序遍历，则可以得到中缀表达式
做后序遍历，则可以得到后缀表达式
已知树的结点可以表示成：
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
原文：http://www.cnblogs.com/cheermyang/p/5288832.html