表达式二叉树

570阅读　0评论2014-11-26　张泽伟
分类：C/C++

转载请注明涞源chengyaogen.blog.chinaunix.net
 
一、定义
 
       二叉树(binary tree)是一棵每个结点都不能有多于两个儿子的树。

二、数据结构设计
    
        因为一个二叉树结点最多是有两个儿子，所以可以直接链接到他们。树结点的声明在结构上类似双向链表的声明。在声明中，一个结点就是由element(元素)的信息加上两个 到其他结点的引用(left和right)组成的结构

        struct BinaryNode
        {
              Object    element;                    //The data in the node  
              struct BinaryNode   *left;        //Left   child
              struct BinaryNode   *right;     //Right  child
        };    
  
三、表达式树
    
    表达式树的树叶是操作数(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>

  4. #define MAX 100

  6. //树结点的设计
  7. typedef struct node
  8. {
  9.     //数字和运算符
  10.     union
  11.     {
  12.         char operator;
  13.         int data;
  14.     };

  16.     struct node *lchild;
  17.     struct node *rchild;    
  18.     
  19. }TreeNode;

  21. //树栈的设计
  22. typedef struct
  23. {
  24.     TreeNode *buf[MAX];
  25.     int n;
  26.     
  27. }TreeStack;

  29. //创建空栈
  30. TreeStack *create_empty_stack()
  31. {
  32.     TreeStack *pstack;

  34.     pstack = (TreeStack *)malloc(sizeof(TreeStack));
  35.     pstack->n = -1;

  37.     return pstack;
  38. }

  40. //入栈
  41. int push_stack(TreeStack *p,TreeNode *data)
  42. {
  43.     p->n ++;
  44.     p->buf[p->n] = data;

  46.     return 0;
  47. }

  49. //出栈
  50. TreeNode *pop_stack(TreeStack *p)
  51. {
  52.     TreeNode *data;

  54.     data = p->buf[p->n];
  55.     p->n --;

  57.     return data;
  58. }

  60. //判断空栈
  61. int is_empty_stack(TreeStack *p)
  62. {
  63.     if(p->n == -1)
  64.     {
  65.         return 1;
  66.         
  67.     }else{
  68.         return 0;
  69.     }
  70. }

  72. //后缀表达式树的创建
  73. TreeNode *create_express_tree(char *str,TreeStack *p)
  74. {
  75.     int i = 0;
  76.     TreeNode *current;
  77.     TreeNode *left,*right;
  78.     
  79.     while(str[i])
  80.     {
  81.         if(str[i] == ' ')
  82.         {
  83.             i ++;
  84.             continue;
  85.         }
  86.         
  87.         if(str[i] >= '0' && str[i] <= '9')
  88.         {
  89.             current = (TreeNode *)malloc(sizeof(TreeNode));
  90.             current->data = str[i] - '0';
  91.             current->lchild = current->rchild = NULL;
  92.             push_stack(p,current);
  93.             
  94.         }else{
  95.             current = (TreeNode *)malloc(sizeof(TreeNode));
  96.             current->operator = str[i];
  97.             right = pop_stack(p);
  98.             left = pop_stack(p);
  99.             current->lchild = left;
  100.             current->rchild = right;
  101.             push_stack(p,current);
  102.         }

  104.         i ++;
  105.     }

  107.     return p->buf[p->n];
  108. }

  110. //打印结点
  111. void print_node(TreeNode *p)
  112. {
  113.     if(p->lchild == NULL && p->rchild == NULL)
  114.     {
  115.         printf("%d ",p->data);
  116.         
  117.     }else{

  119.         printf("%c ",p->operator);
  120.     }

  122.     return;
  123. }

  125. //访问结点
  126. int vist_node(TreeNode *p)
  127. {
  128.     print_node(p);

  130.     return 0;
  131. }

  133. //树的后序遍历
  134. int PostOrder(TreeNode *p)
  135. {
  136.     if(p != NULL)
  137.     {
  138.         PostOrder(p->lchild);//左
  139.         PostOrder(p->rchild);//右
  140.         vist_node(p);//根
  141.     }

  143.     return 0;
  144. }

  146. //树的中序遍历
  147. int InOrder(TreeNode *p)
  148. {
  149.     if(p != NULL)
  150.     {
  151.         InOrder(p->lchild);//左
  152.         vist_node(p);//根
  153.         InOrder(p->rchild);//右
  154.     }

  156.     return 0;
  157. }

  159. //树的前序遍历
  160. int PreOrder(TreeNode *p)
  161. {
  162.     if(p != NULL)
  163.     {
  164.         vist_node(p);//根
  165.         PreOrder(p->lchild);//左
  166.         PreOrder(p->rchild);//右
  167.     }

  169.     return 0;
  170. }

  172. /队列的设计
  173. struct _node_
  174. {
  175.     TreeNode *data;
  176.     struct _node_ *next;
  177. };

  179. typedef struct
  180. {
  181.     struct _node_ *front;
  182.     struct _node_ *rear;
  183.     
  184. }Queue;

  186. //创建空队列
  187. Queue *create_empty_queue()
  188. {
  189.     struct _node_ *pnode;
  190.     Queue *qhead;

  192.     qhead = (Queue *)malloc(sizeof(Queue));
  193.     pnode = (struct _node_ *)malloc(sizeof(struct _node_));
  194.     pnode->next = NULL;

  196.     qhead->front = qhead->rear = pnode;

  198.     return qhead;    
  199. }

  201. //入队
  202. int EnterQueue(Queue *qhead,TreeNode *data)
  203. {
  204.     struct _node_ *temp;

  206.     temp = (struct _node_ *)malloc(sizeof(struct _node_ *));
  207.     temp->data = data;
  208.     temp->next = NULL;

  210.     qhead->rear->next = temp;
  211.     qhead->rear = temp;

  213.     return 0;    
  214. }

  216. //出队
  217. TreeNode *DeleteQueue(Queue *qhead)
  218. {
  219.     struct _node_ *temp;

  221.     temp = qhead->front;
  222.     qhead->front = temp->next;
  223.     free(temp);
  224.     temp = NULL;

  226.     return qhead->front->data;
  227. }

  229. //队列为空
  230. int is_empty_queue(Queue *qhead)
  231. {
  232.     if(qhead->front == qhead->rear)
  233.         return 1;
  234.     else
  235.         return 0;
  236. }

  238. //树的层次遍历
  239. int NoOrder(TreeNode *p)
  240. {
  241.     Queue *qhead;
  242.     TreeNode *pdata;

  244.     qhead = create_empty_queue();
  245.     EnterQueue(qhead, p);

  247.     while(!is_empty_queue(qhead))
  248.     {
  249.         pdata = DeleteQueue(qhead);
  250.         vist_node(pdata);

  252.         if(pdata->lchild)EnterQueue(qhead,pdata->lchild);
  253.         if(pdata->rchild)EnterQueue(qhead,pdata->rchild);
  254.     }
  255.     
  256.     return 0;
  257. }

  259. int main()
  260. {
  261.     TreeNode *thead;
  262.     TreeStack *pstack;
  263.     int i = 0;
  264.     char buf[100];

  266.     while((buf[i++] = getchar()) != '\n' && i < 100);
  267.     buf[i-1] = 0;
  268.     
  269.     pstack = create_empty_stack();
  270.     thead = create_express_tree(buf,pstack);

  272.     printf("PostOrder:: ");
  273.     PostOrder(thead);
  274.     printf("\n");

  276.     printf("InOrder:: ");
  277.     InOrder(thead);
  278.     printf("\n");

  280.     printf("PreOrder:: ");
  281.     PreOrder(thead);
  282.     printf("\n");

  284.     printf("NoOrder::");
  285.     NoOrder(thead);
  286.     printf("\n");

  288.     return 0;
  289. }
 
运行结果:
上一篇：进程间通信--管道
下一篇：Linux 设备驱动之字符设备(一)