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

原文，转载如下：

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

同时应该学会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被读入，在单个结点树创建后，指向对应的树的指针被压入栈中。

接下来读入"+"号，因此两棵树合并。

继续进行，读入"*"号，因此，弹出两棵树的指针合并形成一棵新的树，"*"号是它的根。

最后，读入一个符号，两棵树合并，而指向最后的树的指针被留在栈中。

[cpp] view plain copy

#include<stdio.h>
#include<stdlib.h>
#defineMAX100
/*树结点的设计*/
typedefstructnode
{
/*数字和运算符*/
union
{
charoperator;
intdata;
};
structnode*lchild;
structnode*rchild;
}TreeNode;
/*树栈*/
typedefstructTree_Stack
{
TreeNode*buf[MAX];
intn;
}TreeStack;
/*创建空栈*/
TreeStack*create_empty_stack()
{
TreeStack*pstack;
pstack=(TreeStack*)malloc(sizeof(TreeStack));
pstack->n=-1;
returnpstack;
}
/*入栈*/
intpush_stack(TreeStack*p,TreeNode*data)
{
p->n++;
p->buf[p->n]=data;
return0;
}
/*出栈*/
TreeNode*pop_stack(TreeStack*p)
{
TreeNode*data;
data=p->buf[p->n];
p->n--;
returndata;
}
/*判断栈空*/
intis_empty_stack(TreeStack*p)
{
if(p->n==-1)
return1;
else
return0;
}
/*创建后缀表达式树*/
TreeNode*create_express_tree(char*str,TreeStack*p)
{
inti=0;
TreeNode*current;
TreeNode*left,*right;
while(str[i])
{
if(str[i]>='0'&&str[i]<='9')
{
current=(TreeNode*)malloc(sizeof(TreeNode));
current->data=str[i]-'0';
current->lchild=NULL;
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++;
}
returnp->buf[p->n];
}
/*打印结点*/
voidprint_node(TreeNode*p)
{
if(p->lchild==NULL&&p->rchild==NULL)
printf("%d",p->data);
else
printf("%c",p->operator);
}
/*访问结点*/
intvisit_node(TreeNode*p)
{
print_node(p);
return0;
}
/*树的后序遍历*/
voidPostOrder(TreeNode*p)
{
if(p!=NULL)
{
PostOrder(p->lchild);
PostOrder(p->rchild);
visit_node(p);
}
}
/*树的中序遍历*/
voidInOrder(TreeNode*p)
{
if(p!=NULL)
{
InOrder(p->lchild);
visit_node(p);
InOrder(p->rchild);
}
}
/*树的前序遍历*/
voidPreOrder(TreeNode*p)
{
if(p!=NULL)
{
visit_node(p);
PreOrder(p->lchild);
PreOrder(p->rchild);
}
}
intmain()
{
TreeNode*thead;
TreeStack*pstack;
inti=0;
charbuf[100];
scanf("%s",buf);
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");
return0;
}

测试结果如下：

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

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