二叉树的前中后序遍历以及表达式树论述.pdf

二叉树的前中后序遍历以及表达式树 昨天数据结构课布置了上机实验，要求递归方式建立表达式二叉树，输出树的前中后序遍历的结 果，并计算表达式的值。网上其他人的做法无非就是先求出后缀表达式，然后后序遍历的方式+栈建 立二叉树，可是本题的要求是递归方式，所以我的方法就是求出前缀表达式，用前序遍历的方法可以 递归建立二叉树，最后用后序遍历的方式求解表达式树。 举个栗子：表达式：1 + 2 * (3 - 4) - 5 / 6，那么它的前缀表达式就是：- + 1 * 2 - 3 4 / 5 6， 那么可以建立二叉树，如图： 最后，附上代码 /************************************************ * Author :你们亲爱的室友 * Created Time :2015/10/29 星期四 16:12:53 * File Name :BT.cpp ************************************************/ #include cstdio #include algorithm #include iostream #include sstream #include cstring #include cmath #include string #include vector #include queue #include deque #include stack #include list #include map #include set #include bitset #include cstdlib #include ctime #include iomanip using namespace std; #define lson l, mid, rt 1 #define rson mid + 1, r, rt 1 | 1 typedef long long ll; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = acos (-1.0); /* 表达式求值，逆波兰式(后缀表达式)算法 输入(可以有空格，支持小数，实现+-/*%)： ((1+2)*5+1)/4= 注意：取模一定是要整型，实现版本数字全是 double，强制类型转换可能倒置错误 转换为后缀表达式： 得到：1 2 + 5 * 1 + 4 / = 计算后缀表达式：得到：4.00 */ bool is_digit(char ch) { return 0 = ch ch = 9; } struct Exp { stackchar op; stackdouble num; bool error; int prior(char ch) { //运算符的优先级 switch (ch) { case +: case -: return 1; case *: case %: case /: return 2; default: return 0; } } string get_prefix(string s) { //中缀表达式转变前缀表达式 while (!op.empty ()) op.pop (); op.push (#); string ret = ; int len = s.length (), i = len - 1; while (i = 0) { if (s[i] == || s[i] == =) { i--; continue; } else if (s[i] == )) { op.push (s[i--]); } else if (s[i] == () { while (op.top () != # op.top () != )) { ret += op.top (); ret += ; op.pop (); } op.pop (); i--; } else if (s[i] == + || s[i] == - || s[i] == * || s[i] == / || s[i] == %) { while (prior (op.top ()) prior (s[i])) { ret += op.top ();ret += ; op.pop (); } op.push (s[i--]); } else { while (is_digit (s[i]) || s[i] == .) { ret += s[i--]; } ret += ; } } while (op.top () != #)