构造一棵表达式二叉树

下面这个程序是我看weiss的《数据结构与算法分析》的第四章的树里面的一个算法写的程序，具体可以看该书的第一版的71页这个给出我的实现，希望来者给出更加好的设计思路。

程序里面给出了8种遍历方式，欧拉遍历（其实就是中序加了两个括号而已），前序非递归，中序非递归，后序非递归，前序递归，中序递归，后序递归，

另外程序也添加了按层遍历二叉树，程序如下：

2. #include<ctype.h>
3. #include<malloc.h>
4. #include<stdio.h>
5. #include<queue>
6. usingnamespacestd;
8. typedefstructTreenode*ptrtonode;
9. typedefptrtonodeTree;
11. structTreenode{
12. charx;
13. Treelefttree;
14. Treerighttree;
15. }Treenode;
17. typedefstructList_Stack{
18. structList_Stack*next;
19. Treemytree;
20. }Node,*LS;
22. voidinitstack(LS*a){
23. (*a)=(LS)malloc(sizeof(Node));
24. (*a)->next=NULL;
25. }
27. boolstackempty(constLSa){
28. returna->next==NULL;
29. }
31. /*链栈一般不会满，不测试
32. boolstackfull(constLSa){
33. return!stackempty(a);
34. }
35. */
37. voidpush(LS*lstack,Treea){
38. LSres=(LS)malloc(sizeof(Node));
39. res->mytree=a;
40. res->next=(*lstack)->next;
41. (*lstack)->next=res;
42. }
44. Treepop(LS*lstack){
45. if(stackempty(*lstack)){
46. printf("Poperror,stackisempty!\n");
47. returnNULL;//打印一个笑脸
48. }
49. LSp=(*lstack)->next;
50. Treex=p->mytree;
51. LSpnext=p->next;
52. //free(p);
53. (*lstack)->next=pnext;
54. returnx;
55. }
60. boolisoperator(chara){
61. if(a=='-'||a=='+'||a=='*'||a=='/')
62. return1;
63. else
64. return0;
65. }
67. Treechartotree(chara){
68. Treemytree=(Tree)malloc(sizeof(Treenode));
69. mytree->x=a;
70. mytree->lefttree=mytree->righttree=NULL;
71. returnmytree;
72. }
74. boolexnode(Treex){//外节点，也就是叶子节点
75. if((x->righttree==NULL)&&(x->lefttree==NULL)){
76. return1;
77. }
78. else
79. return0;
80. }
82. boolinnode(Treex){//内节点，也就是中间节点
83. return!exnode(x);
84. }
86. //欧拉遍历方式，跟中序遍历类似
87. voideulervisit(Treex){
88. if(exnode(x)){
89. printf("%c",x->x);
90. }
91. else{
92. printf("(");
93. eulervisit(x->lefttree);
94. printf("%c",x->x);
95. eulervisit(x->righttree);
96. printf(")");
97. }
98. }
100. //中序递归的遍历方式
101. boolmidvisit(Treex){
102. if(x){
103. if(midvisit(x->lefttree))
104. if(printf("%c",x->x))
105. if(midvisit(x->righttree))
106. return1;
107. return0;
108. }
109. else
110. return1;
111. }
113. //前序递归的遍历方式
114. boolprevisit(Treex){
115. if(x){
116. if(printf("%c",x->x))
117. if(previsit(x->lefttree))
118. if(previsit(x->righttree))
119. return1;
120. return0;
121. }
122. else
123. return1;
124. }
126. //后序递归的遍历方式
127. voidpostvisit(Treex){
128. if(x){
129. postvisit(x->lefttree);
130. postvisit(x->righttree);
131. printf("%c",x->x);
132. }
133. }
135. //前序的非递归遍历
136. voidpreordervisit(Treex){
137. LSa;
138. initstack(&a);
139. Treep=x;
140. while(p||!stackempty(a))
141. {
142. if(p)
143. {
144. push(&a,p);
145. printf("%c",p->x);
146. p=p->lefttree;
147. }
148. else{
149. p=pop(&a);
150. p=p->righttree;
151. }
152. }
153. }
155. //中序的非递归遍历
156. voidinordervisit(Treex){
157. LSa;
158. initstack(&a);
159. Treep=x;
160. while(p||!stackempty(a))
161. {
162. if(p)
163. {
164. push(&a,p);
165. p=p->lefttree;
166. }
167. else{
168. p=pop(&a);
169. printf("%c",p->x);
170. p=p->righttree;
171. }
172. }
173. }
175. /***********************************************************************
176. /*后序的非递归遍历，后序遍历有点复杂，
177. /*要给出一个标记表明左边和右边子树都已经遍历，
178. /*这里就不使用开始时候的堆栈了，
179. /*用数组堆栈实现效果更加好，惟一的缺点就是堆栈有最大限制*/
180. /************************************************************************/
182. voidpostordervisit(Treex){
183. Treestack[100],p;
184. inttag[100],top;
185. top=0;
186. p=x;
187. do
188. {
189. while(p!=NULL)//扫描左子树，入栈
190. {
191. top++;
192. stack[top]=p;
193. tag[top]=0;//右边子树还没有访问设置为0
194. p=p->lefttree;
195. }
196. if(top>0)
197. {
198. if(tag[top]==1)
199. {
200. printf("%c",stack[top]->x);
201. top--;
202. }
203. else{
204. p=stack[top];
205. if(top>0)
206. {
207. p=p->righttree;
208. tag[top]=1;
209. }
210. }
211. }
212. }while((p!=NULL)||(top!=0));
213. }
215. Treecreatetree(char*a){//根据数据结构与算法分析的71页的算法设计一个表达式树
216. LSx;
217. initstack(&x);
218. char*p=a;
219. while(*p!='\0'){
220. Treea,b;
221. Treemytree;
222. if(isalpha(*p)){
223. mytree=chartotree(*p);
224. push(&x,mytree);
225. }
226. if(isoperator(*p)){
227. mytree=chartotree(*p);
228. a=pop(&x);
229. b=pop(&x);
230. mytree->righttree=a;
231. mytree->lefttree=b;
232. push(&x,mytree);
233. }
234. p++;
235. }
236. Treeroot=pop(&x);
237. returnroot;
238. }
240. voiddeletenode(Tree*p){//按层遍历
241. queue<Tree>que;
242. que.push(*p);
243. Treetemp;
244. while(!que.empty()){
245. temp=que.front();
246. que.pop();
247. if(temp->lefttree)
248. que.push(temp->lefttree);
249. if(temp->righttree)
250. que.push(temp->righttree);
251. //free(temp);
252. printf("%c",temp->x);
253. temp=NULL;
254. }
255. }
257. intmain(intargc,char*argv[])
258. {
259. LSx;
260. initstack(&x);
262. if(stackempty(x))
263. printf("stackisempty!\n");
264. else
265. printf("stackisfull!\n");
266. printf("%c\n",pop(&x));
268. char*p="abc*+b-";
269. Treeroot=createtree(p);
270. //等待进一步的实现来实现二叉树的遍历
271. //用到exnode和innode函数
274. eulervisit(root);
275. puts("\n中序递归");
276. midvisit(root);
277. puts("\n中序非递归");
278. inordervisit(root);
279. puts("\n前序递归");
280. previsit(root);
281. puts("\n前序非递归");
282. preordervisit(root);
283. puts("\n后序递归");
284. postvisit(root);
285. puts("\n后序非递归");
286. postordervisit(root);
288. deletenode(&root);
289. return0;
290. }