【数据结构】后缀表达式-->表达式树

前端之家收集整理的这篇文章主要介绍了【数据结构】后缀表达式-->表达式树前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

原文,转载如下:

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

同时应该学会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被读入,在单个结点树创建后,指向对应的树的指针被压入栈中。
接下来读入"+"号,因此两棵树合并。
继续进行,读入"*"号,因此,弹出两棵树的指针合并形成一棵新的树,"*"号是它的根。
最后,读入一个符号,两棵树合并,而指向最后的树的指针被留在栈中。


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

测试结果如下:

原文链接:https://www.f2er.com/datastructure/382295.html

猜你在找的数据结构相关文章