现在的位置: 首页 > 综合 > 正文

构造一棵表达式二叉树

2013年10月22日 ⁄ 综合 ⁄ 共 5907字 ⁄ 字号 小 中 大 ⁄ 评论关闭

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

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

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

  2. #include <ctype.h>  
  3. #include <malloc.h>  
  4. #include <stdio.h>
  5. #include <queue>
  6. using namespace std;
  8. typedef struct Treenode *ptrtonode; 
  9. typedef ptrtonode Tree; 
  11. struct Treenode { 
  12.     char x; 
  13.     Tree lefttree; 
  14.     Tree righttree; 
  15. } Treenode; 
  17. typedef  struct List_Stack { 
  18.     struct List_Stack *next;     
  19.     Tree mytree; 
  20. } Node, *LS; 
  22. void initstack(LS *a) { 
  23.     (*a) = (LS)malloc(sizeof(Node)); 
  24.     (*a)->next = NULL; 
  25. } 
  27. bool stackempty(const LS a) { 
  28.     return a->next == NULL; 
  29. } 
  31. /* 链栈一般不会满，不测试 
  32. bool stackfull(const LS a) { 
  33.     return !stackempty(a); 
  34. } 
  35. */ 
  37. void push(LS *lstack, Tree a) { 
  38.     LS res = (LS)malloc(sizeof(Node)); 
  39.     res->mytree = a; 
  40.     res->next = (*lstack)->next; 
  41.     (*lstack)->next = res; 
  42. } 
  44. Tree pop(LS *lstack) { 
  45.     if (stackempty(*lstack)) { 
  46.         printf("Pop error,stack is empty!/n"); 
  47.         return NULL;//打印一个笑脸 
  48.     } 
  49.     LS p = (*lstack)->next; 
  50.     Tree x = p->mytree; 
  51.     LS pnext = p->next; 
  52.     //free(p); 
  53.     (*lstack)->next = pnext; 
  54.     return x; 
  55. } 
  60. bool isoperator(char a) {  
  61.     if(a == '-' || a == '+' || a == '*' || a == '/')  
  62.         return 1;  
  63.     else   
  64.         return 0;  
  65. }  
  67. Tree chartotree(char a) {  
  68.     Tree mytree = (Tree)malloc(sizeof(Treenode));  
  69.     mytree->x = a;  
  70.     mytree->lefttree = mytree->righttree = NULL;  
  71.     return mytree;  
  72. }  
  74. bool exnode(Tree x) { //外节点，也就是叶子节点  
  75.     if( (x->righttree == NULL) && (x->lefttree == NULL) ) {  
  76.         return 1;  
  77.     }  
  78.     else  
  79.         return 0;  
  80. }  
  82. bool innode(Tree x) { //内节点，也就是中间节点  
  83.     return !exnode(x);  
  84. }  
  86. //欧拉遍历方式，跟中序遍历类似  
  87. void eulervisit(Tree x) {  
  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. bool midvisit(Tree x) {  
  102.     if(x) {  
  103.         if(midvisit(x->lefttree)) 
  104.             if(printf(" %c ", x->x)) 
  105.                 if(midvisit(x->righttree)) 
  106.                     return 1; 
  107.         return 0; 
  108.     }  
  109.     else 
  110.         return 1; 
  111. }  
  113. //前序递归的遍历方式  
  114. bool previsit(Tree x) {  
  115.     if(x) {  
  116.         if(printf(" %c ", x->x)) 
  117.             if(previsit(x->lefttree)) 
  118.                 if(previsit(x->righttree)) 
  119.                     return 1; 
  120.         return 0; 
  121.     }  
  122.     else 
  123.         return 1; 
  124. }  
  126. //后序递归的遍历方式  
  127. void postvisit(Tree x) {  
  128.     if(x) {          
  129.         postvisit(x->lefttree);          
  130.         postvisit(x->righttree);  
  131.         printf(" %c ", x->x);  
  132.     }  
  133. }  
  135. //前序的非递归遍历 
  136. void preordervisit(Tree x) { 
  137.     LS a;  
  138.     initstack(&a); 
  139.     Tree p = 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. void inordervisit(Tree x) { 
  157.     LS a;  
  158.     initstack(&a); 
  159.     Tree p = 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. void postordervisit(Tree x) { 
  183.     Tree stack[100], p; 
  184.     int tag[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. Tree createtree(char *a) { //根据数据结构与算法分析的71页的算法设计一个表达式树  
  216.     LS x;  
  217.     initstack(&x);  
  218.     char *p = a;  
  219.     while( *p != '/0') {  
  220.         Tree a, b;  
  221.         Tree mytree;  
  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.     Tree root = pop(&x);  
  237.     return root;  
  238. }  
  240. void deletenode(Tree *p) { //按层遍历
  241.     queue<Tree> que;
  242.     que.push(*p);
  243.     Tree temp;
  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. int main(int argc, char* argv[])  
  258. {  
  259.     LS x;  
  260.     initstack(&x);  
  262.     if (stackempty(x))  
  263.         printf("stack is empty!/n");   
  264.     else   
  265.         printf("stack is full!/n");  
  266.     printf("%c/n", pop(&x));  
  268.     char *p = "abc*+b-";  
  269.     Tree root = createtree(p);  
  270.     //等待进一步的实现来实现二叉树的遍历  
  271.     //用到exnode和innode函数  
  273.     
  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); 
  287.     
  288.     deletenode(&root);
  289.     return 0;  
  290. }  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞