Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2272002
  • 博文数量: 102
  • 博客积分: 1444
  • 博客等级: 中尉
  • 技术积分: 13853
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-29 10:58
文章分类

全部博文(102)

文章存档

2014年(29)

2013年(14)

2012年(59)

分类: C/C++

2012-04-10 21:37:15

转载请注明涞源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>

  3. #define MAX 100

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

  13.     struct node *lchild;
  14.     struct node *rchild;    
  15.     
  16. }TreeNode;

  17. //树栈的设计
  18. typedef struct
  19. {
  20.     TreeNode *buf[MAX];
  21.     int n;
  22.     
  23. }TreeStack;

  24. //创建空栈
  25. TreeStack *create_empty_stack()
  26. {
  27.     TreeStack *pstack;

  28.     pstack = (TreeStack *)malloc(sizeof(TreeStack));
  29.     pstack->n = -1;

  30.     return pstack;
  31. }

  32. //入栈
  33. int push_stack(TreeStack *p,TreeNode *data)
  34. {
  35.     p->n ++;
  36.     p->buf[p->n] = data;

  37.     return 0;
  38. }

  39. //出栈
  40. TreeNode *pop_stack(TreeStack *p)
  41. {
  42.     TreeNode *data;

  43.     data = p->buf[p->n];
  44.     p->n --;

  45.     return data;
  46. }

  47. //判断空栈
  48. int is_empty_stack(TreeStack *p)
  49. {
  50.     if(p->n == -1)
  51.     {
  52.         return 1;
  53.         
  54.     }else{
  55.         return 0;
  56.     }
  57. }

  58. //后缀表达式树的创建
  59. TreeNode *create_express_tree(char *str,TreeStack *p)
  60. {
  61.     int i = 0;
  62.     TreeNode *current;
  63.     TreeNode *left,*right;
  64.     
  65.     while(str[i])
  66.     {
  67.         if(str[i] == ' ')
  68.         {
  69.             i ++;
  70.             continue;
  71.         }
  72.         
  73.         if(str[i] >= '0' && str[i] <= '9')
  74.         {
  75.             current = (TreeNode *)malloc(sizeof(TreeNode));
  76.             current->data = str[i] - '0';
  77.             current->lchild = current->rchild = NULL;
  78.             push_stack(p,current);
  79.             
  80.         }else{
  81.             current = (TreeNode *)malloc(sizeof(TreeNode));
  82.             current->operator = str[i];
  83.             right = pop_stack(p);
  84.             left = pop_stack(p);
  85.             current->lchild = left;
  86.             current->rchild = right;
  87.             push_stack(p,current);
  88.         }

  89.         i ++;
  90.     }

  91.     return p->buf[p->n];
  92. }

  93. //打印结点
  94. void print_node(TreeNode *p)
  95. {
  96.     if(p->lchild == NULL && p->rchild == NULL)
  97.     {
  98.         printf("%d ",p->data);
  99.         
  100.     }else{

  101.         printf("%c ",p->operator);
  102.     }

  103.     return;
  104. }

  105. //访问结点
  106. int vist_node(TreeNode *p)
  107. {
  108.     print_node(p);

  109.     return 0;
  110. }

  111. //树的后序遍历
  112. int PostOrder(TreeNode *p)
  113. {
  114.     if(p != NULL)
  115.     {
  116.         PostOrder(p->lchild);//
  117.         PostOrder(p->rchild);//
  118.         vist_node(p);//
  119.     }

  120.     return 0;
  121. }

  122. //树的中序遍历
  123. int InOrder(TreeNode *p)
  124. {
  125.     if(p != NULL)
  126.     {
  127.         InOrder(p->lchild);//
  128.         vist_node(p);//
  129.         InOrder(p->rchild);//
  130.     }

  131.     return 0;
  132. }

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

  142.     return 0;
  143. }

  144. /队列的设计
  145. struct _node_
  146. {
  147.     TreeNode *data;
  148.     struct _node_ *next;
  149. };

  150. typedef struct
  151. {
  152.     struct _node_ *front;
  153.     struct _node_ *rear;
  154.     
  155. }Queue;

  156. //创建空队列
  157. Queue *create_empty_queue()
  158. {
  159.     struct _node_ *pnode;
  160.     Queue *qhead;

  161.     qhead = (Queue *)malloc(sizeof(Queue));
  162.     pnode = (struct _node_ *)malloc(sizeof(struct _node_));
  163.     pnode->next = NULL;

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

  165.     return qhead;    
  166. }

  167. //入队
  168. int EnterQueue(Queue *qhead,TreeNode *data)
  169. {
  170.     struct _node_ *temp;

  171.     temp = (struct _node_ *)malloc(sizeof(struct _node_ *));
  172.     temp->data = data;
  173.     temp->next = NULL;

  174.     qhead->rear->next = temp;
  175.     qhead->rear = temp;

  176.     return 0;    
  177. }

  178. //出队
  179. TreeNode *DeleteQueue(Queue *qhead)
  180. {
  181.     struct _node_ *temp;

  182.     temp = qhead->front;
  183.     qhead->front = temp->next;
  184.     free(temp);
  185.     temp = NULL;

  186.     return qhead->front->data;
  187. }

  188. //队列为空
  189. int is_empty_queue(Queue *qhead)
  190. {
  191.     if(qhead->front == qhead->rear)
  192.         return 1;
  193.     else
  194.         return 0;
  195. }

  196. //树的层次遍历
  197. int NoOrder(TreeNode *p)
  198. {
  199.     Queue *qhead;
  200.     TreeNode *pdata;

  201.     qhead = create_empty_queue();
  202.     EnterQueue(qhead, p);

  203.     while(!is_empty_queue(qhead))
  204.     {
  205.         pdata = DeleteQueue(qhead);
  206.         vist_node(pdata);

  207.         if(pdata->lchild)EnterQueue(qhead,pdata->lchild);
  208.         if(pdata->rchild)EnterQueue(qhead,pdata->rchild);
  209.     }
  210.     
  211.     return 0;
  212. }

  213. int main()
  214. {
  215.     TreeNode *thead;
  216.     TreeStack *pstack;
  217.     int i = 0;
  218.     char buf[100];

  219.     while((buf[i++] = getchar()) != '\n' && i < 100);
  220.     buf[i-1] = 0;
  221.     
  222.     pstack = create_empty_stack();
  223.     thead = create_express_tree(buf,pstack);

  224.     printf("PostOrder:: ");
  225.     PostOrder(thead);
  226.     printf("\n");

  227.     printf("InOrder:: ");
  228.     InOrder(thead);
  229.     printf("\n");

  230.     printf("PreOrder:: ");
  231.     PreOrder(thead);
  232.     printf("\n");

  233.     printf("NoOrder::");
  234.     NoOrder(thead);
  235.     printf("\n");

  236.     return 0;
  237. }
 
运行结果:
阅读(12382) | 评论(0) | 转发(13) |
1

上一篇:图的存储

下一篇:图的遍历

给主人留下些什么吧!~~