原文，转载如下：
用到了栈，并且递归实现了中序遍历，后序遍历，前序遍历。
同时应该学会union的使用方法。
基础知识：
一、表达式树
表达式树的树叶是操作数(operand)，加常数或变量名字，而其他的结点为操作数(operator)。由于这里所有的操作都是二元的，因此这棵特定的树正好是二叉树，虽然这是最简单的情况，但是结点还是有可能含有多于两个的儿子，这里我们不讨论。
二、构造一棵表达式树
之前我们实现过一个中缀表达式求值的具体程序，在求值过程中需要用两个栈，并且代码并不简单。而这里你会看到，对于表达式树的求值操作却非常简单，甚至只需要两条语句。因为这里大部分操作都是递归定义，二递归函数本身都是很简洁的，甚至比你想象的还要简单，甚至只需要两条语句。因为这里大部分操作都是递归定义，二递归函数本身都是很简洁的，甚至比你想象的还要简单！就像树的遍历操作。三种遍历分别是先序遍历、中序遍历与后序遍历，正好对应表达式的三种形式：前缀型、中缀型与后缀型。其中为大家熟知的是中缀形式，如2+3*(5-4)。前缀型表达式又叫波兰式(Polish Notation)，后缀性表达式又叫逆波兰式(Reverse Polish Notation)。他们最早于1920年波兰数学家Jan Lukasiewicz发明，这两种表示方式的最大特点是不需要括号来表明优先级，他们经常用于计算机科学，特别是编译器设计方面。
下面给出一种算法来把后缀表达式转变成表达式树。我们一次一个符号地读入表达式。如果符号是操作数，那么就建立一个单结点树并将它推入栈中。如果符号是操作符，那么就从栈中弹出两棵树T1和T2(T1先弹出)并形成一棵新的树，该树的根就是操作符，它的左、右儿子分别是T2和T1。然后将指向这颗树的指针压入栈中。
下面来看一个例子。设输入为ab+cde+**
前两个符号是操作数，因此创建两棵单结点树并将指向它们的指针压入栈中。
接着,"+"被读入，因此指向两棵树的指针被弹出，形成一棵新的树，并将指向它的指针压入栈中。
然后,c,d和e被读入，在单个结点树创建后，指向对应的树的指针被压入栈中。
接下来读入"+"号，因此两棵树合并。
继续进行，读入"*"号，因此，弹出两棵树的指针合并形成一棵新的树，"*"号是它的根。
最后，读入一个符号，两棵树合并，而指向最后的树的指针被留在栈中。
- #include<stdio.h>
- #include<stdlib.h>
- #defineMAX100
- /*树结点的设计*/
- typedefstructnode
- {
- /*数字和运算符*/
- union
- {
- charoperator;
- intdata;
- };
- structnode*lchild;
- structnode*rchild;
- }TreeNode;
- /*树栈*/
- typedefstructTree_Stack
- {
- TreeNode*buf[MAX];
- intn;
- }TreeStack;
- /*创建空栈*/
- TreeStack*create_empty_stack()
- {
- TreeStack*pstack;
- pstack=(TreeStack*)malloc(sizeof(TreeStack));
- pstack->n=-1;
- returnpstack;
- }
- /*入栈*/
- intpush_stack(TreeStack*p,TreeNode*data)
- {
- p->n++;
- p->buf[p->n]=data;
- return0;
- }
- /*出栈*/
- TreeNode*pop_stack(TreeStack*p)
- {
- TreeNode*data;
- data=p->buf[p->n];
- p->n--;
- returndata;
- }
- /*判断栈空*/
- intis_empty_stack(TreeStack*p)
- {
- if(p->n==-1)
- return1;
- else
- return0;
- }
- /*创建后缀表达式树*/
- TreeNode*create_express_tree(char*str,TreeStack*p)
- {
- inti=0;
- TreeNode*current;
- TreeNode*left,*right;
- while(str[i])
- {
- if(str[i]>='0'&&str[i]<='9')
- {
- current=(TreeNode*)malloc(sizeof(TreeNode));
- current->data=str[i]-'0';
- current->lchild=NULL;
- current->rchild=NULL;
- push_stack(p,current);
- }
- else
- {
- current=(TreeNode*)malloc(sizeof(TreeNode));
- current->operator=str[i];
- right=pop_stack(p);
- left=pop_stack(p);
- current->lchild=left;
- current->rchild=right;
- push_stack(p,current);
- }
- i++;
- }
- returnp->buf[p->n];
- }
- /*打印结点*/
- voidprint_node(TreeNode*p)
- {
- if(p->lchild==NULL&&p->rchild==NULL)
- printf("%d",p->data);
- else
- printf("%c",p->operator);
- }
- /*访问结点*/
- intvisit_node(TreeNode*p)
- {
- print_node(p);
- return0;
- }
- /*树的后序遍历*/
- voidpostorder(TreeNode*p)
- {
- if(p!=NULL)
- {
- postorder(p->lchild);
- postorder(p->rchild);
- visit_node(p);
- }
- }
- /*树的中序遍历*/
- voidInorder(TreeNode*p)
- {
- if(p!=NULL)
- {
- Inorder(p->lchild);
- visit_node(p);
- Inorder(p->rchild);
- }
- }
- /*树的前序遍历*/
- voidPreOrder(TreeNode*p)
- {
- if(p!=NULL)
- {
- visit_node(p);
- PreOrder(p->lchild);
- PreOrder(p->rchild);
- }
- }
- intmain()
- {
- TreeNode*thead;
- TreeStack*pstack;
- inti=0;
- charbuf[100];
- scanf("%s",buf);
- pstack=create_empty_stack();
- thead=create_express_tree(buf,pstack);
- printf("postorder:");
- postorder(thead);
- printf("\n");
- printf("Inorder:");
- Inorder(thead);
- printf("\n");
- printf("PreOrder:");
- PreOrder(thead);
- printf("\n");
- return0;
- }
测试结果如下：