一、定义
二叉树(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被读入,在单个结点树创建后,指向对应的树的指针被压入栈中。
接下来读入"+"号,因此两棵树合并。
继续进行,读入"*"号,因此,弹出两棵树的指针合并形成一棵新的树,"*"号是它的根。
最后,读入一个符号,两棵树合并,而指向最后的树的指针被留在栈中。
下面我们来实现以下它吧
- #include <stdio.h>
- #include <stdlib.h>
- #define MAX 100
- //树结点的设计
- typedef struct node
- {
- //数字和运算符
- union
- {
- char operator;
- int data;
- };
- struct node *lchild;
- struct node *rchild;
-
- }TreeNode;
- //树栈的设计
- typedef struct
- {
- TreeNode *buf[MAX];
- int n;
-
- }TreeStack;
- //创建空栈
- TreeStack *create_empty_stack()
- {
- TreeStack *pstack;
- pstack = (TreeStack *)malloc(sizeof(TreeStack));
- pstack->n = -1;
- return pstack;
- }
- //入栈
- int push_stack(TreeStack *p,TreeNode *data)
- {
- p->n ++;
- p->buf[p->n] = data;
- return 0;
- }
- //出栈
- TreeNode *pop_stack(TreeStack *p)
- {
- TreeNode *data;
- data = p->buf[p->n];
- p->n --;
- return data;
- }
- //判断空栈
- int is_empty_stack(TreeStack *p)
- {
- if(p->n == -1)
- {
- return 1;
-
- }else{
- return 0;
- }
- }
- //后缀表达式树的创建
- TreeNode *create_express_tree(char *str,TreeStack *p)
- {
- int i = 0;
- TreeNode *current;
- TreeNode *left,*right;
-
- while(str[i])
- {
- if(str[i] == ' ')
- {
- i ++;
- continue;
- }
-
- if(str[i] >= '0' && str[i] <= '9')
- {
- current = (TreeNode *)malloc(sizeof(TreeNode));
- current->data = str[i] - '0';
- current->lchild = current->rchild = NULL;
- push_stack(p,current);
-
- }else{
- current = (TreeNode *)malloc(sizeof(TreeNode));
- current->operator = str[i];
- right = pop_stack(p);
- left = pop_stack(p);
- current->lchild = left;
- current->rchild = right;
- push_stack(p,current);
- }
- i ++;
- }
- return p->buf[p->n];
- }
- //打印结点
- void print_node(TreeNode *p)
- {
- if(p->lchild == NULL && p->rchild == NULL)
- {
- printf("%d ",p->data);
-
- }else{
- printf("%c ",p->operator);
- }
- return;
- }
- //访问结点
- int vist_node(TreeNode *p)
- {
- print_node(p);
- return 0;
- }
- //树的后序遍历
- int PostOrder(TreeNode *p)
- {
- if(p != NULL)
- {
- PostOrder(p->lchild);//左
- PostOrder(p->rchild);//右
- vist_node(p);//根
- }
- return 0;
- }
- //树的中序遍历
- int InOrder(TreeNode *p)
- {
- if(p != NULL)
- {
- InOrder(p->lchild);//左
- vist_node(p);//根
- InOrder(p->rchild);//右
- }
- return 0;
- }
- //树的前序遍历
- int PreOrder(TreeNode *p)
- {
- if(p != NULL)
- {
- vist_node(p);//根
- PreOrder(p->lchild);//左
- PreOrder(p->rchild);//右
- }
- return 0;
- }
- /队列的设计
- struct _node_
- {
- TreeNode *data;
- struct _node_ *next;
- };
- typedef struct
- {
- struct _node_ *front;
- struct _node_ *rear;
-
- }Queue;
- //创建空队列
- Queue *create_empty_queue()
- {
- struct _node_ *pnode;
- Queue *qhead;
- qhead = (Queue *)malloc(sizeof(Queue));
- pnode = (struct _node_ *)malloc(sizeof(struct _node_));
- pnode->next = NULL;
- qhead->front = qhead->rear = pnode;
- return qhead;
- }
- //入队
- int EnterQueue(Queue *qhead,TreeNode *data)
- {
- struct _node_ *temp;
- temp = (struct _node_ *)malloc(sizeof(struct _node_ *));
- temp->data = data;
- temp->next = NULL;
- qhead->rear->next = temp;
- qhead->rear = temp;
- return 0;
- }
- //出队
- TreeNode *DeleteQueue(Queue *qhead)
- {
- struct _node_ *temp;
- temp = qhead->front;
- qhead->front = temp->next;
- free(temp);
- temp = NULL;
- return qhead->front->data;
- }
- //队列为空
- int is_empty_queue(Queue *qhead)
- {
- if(qhead->front == qhead->rear)
- return 1;
- else
- return 0;
- }
- //树的层次遍历
- int NoOrder(TreeNode *p)
- {
- Queue *qhead;
- TreeNode *pdata;
- qhead = create_empty_queue();
- EnterQueue(qhead, p);
- while(!is_empty_queue(qhead))
- {
- pdata = DeleteQueue(qhead);
- vist_node(pdata);
- if(pdata->lchild)EnterQueue(qhead,pdata->lchild);
- if(pdata->rchild)EnterQueue(qhead,pdata->rchild);
- }
-
- return 0;
- }
- int main()
- {
- TreeNode *thead;
- TreeStack *pstack;
- int i = 0;
- char buf[100];
- while((buf[i++] = getchar()) != '\n' && i < 100);
- buf[i-1] = 0;
-
- pstack = create_empty_stack();
- thead = create_express_tree(buf,pstack);
- printf("PostOrder:: ");
- PostOrder(thead);
- printf("\n");
- printf("InOrder:: ");
- InOrder(thead);
- printf("\n");
- printf("PreOrder:: ");
- PreOrder(thead);
- printf("\n");
- printf("NoOrder::");
- NoOrder(thead);
- printf("\n");
- return 0;
- }
运行结果:
阅读(265) | 评论(0) | 转发(0) |