`
pleasetojava
  • 浏览: 732982 次
  • 性别: Icon_minigender_2
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

构造一棵表达式二叉树

阅读更多

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

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

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

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

相关推荐

    将已知数组元素构造一棵二叉树

    例如,如果我们有数组 `[1, 2, 3, 4, 5]`,我们可能想要构造一个完全二叉树,使得数组中的每个元素成为二叉树的一个节点,而数组的索引决定节点的位置。在这种情况下,数组的索引0是根节点,索引1和2是其左子节点和...

    算术表达式和二叉树-数据结构课设

    (1) ReadExpre(E)- _以字符序列的形式输入语法正确的前缀表达式并构造表达式E。(2) WriteExpre(E)- 用带括弧的中缀表达式输出表达式E。 (3) Assign(V,c)-实现对变量 V的赋值(V=c), 变量的初值为0。 (4) Value(E)-对...

    C++版数据结构的算术表达式与二叉树

    1. 构建:从后缀表示或前缀表示构造二叉树,可以使用栈来辅助实现。 2. 遍历:主要有前序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根),每种遍历方式对应不同的算术表达式表示。 3. 计算:通过...

    构造二叉树与遍历二叉树

    1. 创建一个空节点(默认构造函数)。 2. 创建一个只包含元素的节点。 3. 创建一个包含元素和左右子节点的节点。 #### 三、二叉树类的定义 接下来是`BinaryTree`类的定义,它使用了模板来支持不同类型的元素。`...

    链表存储结构的表达式二叉树相关代码

    表达式二叉树是一种特殊的二叉树,用于表示数学表达式,其中叶子节点代表操作数,非叶子节点代表运算符。二叉树的遍历方法有三种主要类型:前序遍历、中序遍历和后序遍历。此外,还有层序遍历(广度优先搜索)和两种...

    根据后序二叉树序列构造二叉树_扩展二叉树

    在众多的二叉树操作中,根据后序遍历序列(也称为后序序列)来构造二叉树是一项常见的任务。后序遍历的特点是:左子树 -&gt; 右子树 -&gt; 根节点,这种遍历方式对于解决特定问题非常有用,如表达式树的构建。 在这个话题...

    前缀和后缀表达式建二叉树

    非递归方法则可能利用栈来模拟运算过程,从左到右遍历表达式,逐步构造二叉树。 在提供的压缩包文件 "建树" 中,可能包含了实现这一功能的代码示例,或者是用于测试该功能的数据集。通过分析和理解这些内容,我们...

    Java实现表达式二叉树

    【Java实现表达式二叉树】是编程领域中一种数据结构的应用,主要用于处理数学表达式。在计算机科学中,二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,通常分为左子节点和右子节点。表达式二叉树,又...

    二叉树建立还有后序计算表达式

    1、设计一个程序,根据二叉树的先根序列和中根序列创建一棵用左右指针表示的二叉树 例如:先根序列为 ABDGCEF#, 中根序列为 DGBAECF# (#表示结束)。然后用程序构造一棵二叉树。注意程序的通用性(也就是说上述只是...

    java版数据结构的 算术表达式与二叉树源码

    2. **二叉树的构造函数**:根据算术表达式构建二叉树。 3. **遍历方法**:实现前序、中序、后序遍历。 4. **计算方法**:遍历二叉树并执行相应的操作,如加、减、乘、除等。 5. **打印方法**:以中缀、前缀或后缀...

    数据结构课程设计(完整版)

    表达式二叉树是一种特殊类型的树,其非叶节点表示运算符,叶节点表示操作数。生成表达式二叉树的过程是将算术表达式从左到右扫描,遇到运算符时创建新节点,遇到操作数时连接到新节点。这个过程可以用来帮助理解...

    java前序中序构造二叉树

    给定前序和中序遍历的结果,可以唯一确定一棵二叉树。前序遍历的第一个元素是树的根节点,而在中序遍历中,这个根节点将树分为了左子树和右子树两部分。根据这两个遍历结果,可以递归地构造整个二叉树。 4. **Java...

    c语言 实现二叉树操作 用栈实现算术表达式求值

    在本课程设计中,主要涉及了两个核心主题...通过以上步骤,可以完成课程设计的要求,实现二叉树的构造与操作,以及算术表达式的中缀到后缀转换和求值。这些技能对于理解和应用数据结构,特别是C语言编程来说至关重要。

    数据课设报告书-表达式类型的实现(完整的课设报告+源代码)

    1. ReadExpr(E)——以字符序列的形式输入语法正确的前缀表示式并构造表达式E。 2. WriteExpr(E)——用带括号的中缀表示式输出表达式E。 3. Assign(V,c)——实现对变量V的赋值(V=c),变量的初值为0。 4. Value...

    表达式求值(二叉树存储)

    在表达式求值的场景下,我们可以构建一种特殊的二叉树——操作符优先二叉树(也称为后缀表达式或逆波兰表示法)或者中缀表达式二叉树。这里我们讨论中缀表达式二叉树,它能直观地反映出表达式的结构。 在构建中缀...

    数据结构(c语言)单链表 表达式求值 二叉树 二叉排序树 Huffman编码

    在这个项目中,我们关注的是五种重要的数据结构及其应用:单链表、表达式求值、二叉树、二叉排序树和Huffman编码。这些概念在算法设计、编译器构建、文件压缩等领域都有广泛应用。 首先,单链表是一种线性数据结构...

    这是数据结构课程设计,二叉树表示的算术表达式

    在这个特定的课程设计中,“二叉树表示的算术表达式”是关键主题,它将二叉树这一数据结构应用于解析和操作数学表达式。下面我们将详细探讨这个主题涉及的知识点。 首先,我们要理解什么是二叉树。二叉树是一种特殊...

Global site tag (gtag.js) - Google Analytics