先看中缀表达式的二叉树表示：
/*
* 中缀表达式 构建 二叉树
*
* 方法： 每次找到“最后计算”的运算符，作为当前树的根，然后递归处理
* 详见 刘汝佳《算法竞赛入门经典》 P198
*
*/
#include <iostream>
using namespace std;
const int maxn = 1000;
//每个节点的左右儿子编号
int lch[maxn], rch[maxn];
//节点的字符
char op[maxn];
//节点数
int cnt = 0;
//s的[x, y)作为范围
int buildTree(char *s, int x, int y){
//c1, c2分别记录出现在括号外的最右边的加减号和乘除号
int c1 = -1, c2 = -1, p = 0, u;
//当前表达式长度为1，则直接以此为一棵树
if(y - x == 1){
u = cnt++; //第u个节点
lch[u] = rch[u] = -1;
op[u] = s[x];
return u;
}
//p==0表示在括号外
for(int i=x; i<y; i++){
switch(s[i]){
case '(': p++; break;
case ')': p--; break;
case '+': case '-':
if(p == 0) c1 = i; //p==0说明s[i]不在括号内
break;
case '*': case '/':
if(p == 0) c2 = i;
break;
}
}
if(c1 < 0) c1 = c2; //括号外没有 + 或 - ，则选括号外的 * 或 /
if(c1 < 0) return buildTree(s, x+1, y-1); //括号外也没有* 或 /， 说明表达式被一个括号括住，去括号
u = cnt++;
lch[u] = buildTree(s, x, c1);
rch[u] = buildTree(s, c1+1, y);
op[u] = s[c1];
return u;
}
int main(){
return 0;
}
下面是转的：
包括中缀、后缀、前缀用二叉树表示：
2.
需求分析：
（1）功能：表达式可以用二叉树表示，对于简单的四则运算，请实现以下功能
【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。
【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。
提示：所谓中缀表达式中的冗余括号，就是去掉括号后不影响表达式的计算顺序。例如：“（c+b）+a”中的括号是冗余的，可以表示成不冗余的“c+b+a”。
（2）输入输出要求：请输入字符串表达式：
树形二叉树（图形显示）
中缀表达式为：
前缀表达式为：
后缀表达式为：
3.
概要设计：（算法）
分成两部分完成：
【1】前缀、中缀、后缀表达式->二叉树表达式
前缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为其右指针和左指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。
中缀表达式->二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二叉树。
后缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树结点，取栈顶元素，取栈顶元素分别作为右、左节点。开始时用变量root保存。
【1】二叉树表达式->前缀、中缀、后缀表达式
二叉树表达式->前缀表达式：对二叉树表达式进行前序遍历。
二叉树表达式->中缀表达式：对二叉树表达式进行中序遍历，若结点操作符的优先级高于其左或右子树，在打印相应的子树之前先打印开括号，在打印相应的子树最后在打印一个闭括号。
二叉树表达式->后缀表达式：对二叉树表达式进行后序遍历。
建立表达式树就是建立树中的每一个结点，将每一个结点链接起来就是整棵树。而在建立深度低的结点时要将其左右指针指向之前建立的深度比它高一级的结点(如’*’要指向’2’和’3’，而’+’又要指向’*’)。这样我们可以用栈来存放每次建立的结点，按照优先级(表达式为中缀型)或顺序扫描表达式(表达式为波兰式与逆波兰式)建立每一个结点。建立结点的顺序即为表达式求值的顺序。如果扫描到操作数则直接新建一个左右指针为空的结点，并压入结点栈中(存放结点指针)。遇到运算符时首先新建一个结点，然后从栈中依次弹出两个结点，并让新建立的结点的左右指针域指向它们。当所有结点建立完毕时，如果表达式没有错误(这里假设输入表达式正确)，这时栈中应该只剩下一个结点，它就是所建立的表达式的根结点。
