表达式树

用到了栈，并且递归实现了中序遍历，后序遍历，前序遍历。

同时应该学会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被读入，在单个结点树创建后，指向对应的树的指针被压入栈中。

 

 

接下来读入"+"号，因此两棵树合并。

 

 

继续进行，读入"*"号，因此，弹出两棵树的指针合并形成一棵新的树，"*"号是它的根。

最后，读入一个符号，两棵树合并，而指向最后的树的指针被留在栈中。

 

[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4. #define MAX 100  
5.   
6. /* 树结点的设计 */  
7. typedef struct node  
8. {  
9.     /* 数字和运算符 */  
10.     union  
11.     {  
12.         char operator;  
13.         int data;  
14.     };  
15.   
16.     struct node *lchild;  
17.     struct node *rchild;  
18. }TreeNode;  
19.   
20. /* 树栈 */  
21. typedef struct Tree_Stack  
22. {  
23.     TreeNode *buf[MAX];  
24.     int n;  
25. }TreeStack;  
26.   
27. /* 创建空栈 */  
28. TreeStack *create_empty_stack()  
29. {  
30.     TreeStack *pstack;  
31.   
32.     pstack = (TreeStack *)malloc(sizeof(TreeStack));  
33.     pstack->n = -1;  
34.   
35.     return pstack;  
36. }  
37.   
38. /* 入栈 */  
39. int push_stack(TreeStack *p, TreeNode *data)  
40. {  
41.     p->n++;  
42.     p->buf[p->n] = data;  
43.   
44.     return 0;  
45. }  
46.   
47. /* 出栈 */  
48. TreeNode *pop_stack(TreeStack *p)  
49. {  
50.     TreeNode *data;  
51.   
52.     data = p->buf[p->n];  
53.     p->n --;  
54.   
55.     return data;  
56. }  
57.   
58. /* 判断栈空 */  
59. int is_empty_stack(TreeStack *p)  
60. {  
61.     if(p->n == -1)  
62.         return 1;  
63.     else  
64.         return 0;  
65. }  
66.   
67. /* 创建后缀表达式树 */  
68. TreeNode *create_express_tree(char *str, TreeStack *p)  
69. {  
70.     int i = 0;  
71.     TreeNode *current;  
72.     TreeNode *left, *right;  
73.   
74.     while(str[i])  
75.     {  
76.         if(str[i] >= '0' && str[i] <= '9')  
77.         {  
78.             current = (TreeNode *)malloc(sizeof(TreeNode));  
79.             current->data = str[i] - '0';  
80.             current->lchild = NULL;  
81.             current->rchild = NULL;  
82.             push_stack(p, current);  
83.         }  
84.         else  
85.         {  
86.             current = (TreeNode *)malloc(sizeof(TreeNode));  
87.             current->operator = str[i];  
88.             right = pop_stack(p);  
89.             left = pop_stack(p);  
90.             current->lchild = left;  
91.             current->rchild = right;  
92.             push_stack(p, current);  
93.         }  
94.         i++;  
95.     }  
96.     return p->buf[p->n];  
97. }  
98.   
99. /* 打印结点 */  
100. void print_node(TreeNode *p)  
101. {  
102.     if(p->lchild == NULL && p->rchild == NULL)  
103.         printf("%d ", p->data);  
104.     else  
105.         printf("%c ", p->operator);  
106. }  
107.   
108. /* 访问结点 */  
109. int visit_node(TreeNode *p)  
110. {  
111.     print_node(p);  
112.   
113.     return 0;  
114. }  
115.   
116. /* 树的后序遍历 */  
117. void PostOrder(TreeNode *p)  
118. {  
119.     if(p != NULL)  
120.     {  
121.         PostOrder(p->lchild);  
122.         PostOrder(p->rchild);  
123.         visit_node(p);  
124.     }  
125. }  
126.   
127. /* 树的中序遍历 */  
128. void InOrder(TreeNode *p)  
129. {  
130.     if(p != NULL)  
131.     {  
132.         InOrder(p->lchild);  
133.         visit_node(p);  
134.         InOrder(p->rchild);  
135.     }  
136. }  
137.   
138. /* 树的前序遍历 */  
139. void PreOrder(TreeNode *p)  
140. {  
141.     if(p != NULL)  
142.     {  
143.         visit_node(p);  
144.         PreOrder(p->lchild);  
145.         PreOrder(p->rchild);  
146.     }  
147. }  
148.   
149. int main()  
150. {  
151.     TreeNode *thead;  
152.     TreeStack *pstack;  
153.     int i = 0;  
154.     char buf[100];  
155.   
156.     scanf("%s", buf);  
157.   
158.     pstack = create_empty_stack();  
159.     thead = create_express_tree(buf, pstack);  
160.   
161.     printf("PostOrder:  ");  
162.     PostOrder(thead);  
163.     printf("\n");  
164.   
165.     printf("InOrder:  ");  
166.     InOrder(thead);  
167.     printf("\n");  
168.   
169.     printf("PreOrder:  ");  
170.     PreOrder(thead);  
171.     printf("\n");  
172.   
173.     return 0;  
174. }  

测试结果如下：