算术表达式与二叉树1.doc

目录

TOC\o1-2\h\z\u一、 算法描述 1

二、 系统分析与设计 1

三、 系统的设计与实现 3

四、系统测试 6

五、总结 8

六、 附件〔代码〕 8

算术表达式与二叉树

算法描述

一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的操作。

系统分析与设计

系统功能要求

算术表达式求值

假设算术表达式Expression内可以含有变量〔a～z〕、常量〔0～9〕和二元运算符〔+，-，*，/〕。实现以下操作：

ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。

WriteExpre(E)—用带括弧的中缀表达式输出表达式E。

Assign(V,c)—实现对变量V的赋值〔V=c〕，变量的初值为0。

Value(E)—对算术表达式E求值。

CompoundExpr〔P，E1，E2〕--构造一个新的复合表达式〔E1〕P〔E2〕

二叉树

构建一棵二叉树CreateBiTree，要求实现二叉树的遍历InOrderOut，即先序遍历、中序遍历、后序遍历，以及这课二叉树中的叶子结点的数目CountLeaf和这棵二叉树的深度Depth。

系统模块结构设计

通过对系统功能的分析，算数表达式与二叉树系统功能结构如下列图所示。

算数表达式

算数表达式

申请两个栈指针

定义运算符栈

定义数字栈

利用栈计算表达式值

主函数的建立

图2-1.算术表达式

二叉树

二叉树

二叉树结构定义

二叉树的初始化

二叉树的创立

二叉树的先中后序遍历

二叉树中叶子节点的数目

二叉树的深度

图2-2.二叉树

对算术表达式系统，可划分为两个模块：

中缀表达式局部，该模块主要实现：将算术表达式以中缀表达式方式输出，借助函数TranslateExpress来实现；

后缀表达式局部，该模块主要实现，将算术表达式以后缀方式输出，借助函数ComputeExpress来实现；

对二叉树系统，可分为以四个下模块：

二叉树的建立，应用函数CreateBiTree来实现调用。

二叉树的遍历算法，应用函数InOrderOut来实现调用，来完成二叉树的先序，中序，后序遍历。

二叉树叶子节点数目的统计，用函数CountLeaf来实现调用。

二叉树深度，应用函数Depth来实现调用。

系统的设计与实现

算术表达式与二叉树

算术表达式

算术表达式

栈的初始化

栈的创立

算术表达式的输入

逐个扫描算术表达式

算术表达式的求值过程

主函数执行局部

图3-1.算术表达式

二

二叉树

二叉树的定义

二叉树的初始化

二叉树的建立

二叉树的遍历〔前、中、后序遍历〕

二叉树中叶子节点的数目统计

二叉树的深度

图3-2.二叉树

该系统局部模块的解说：

定义栈的局部程序：

voidInitStack(SeqStack*S);//初始化栈

intStackEmpty(SeqStackS);//判断栈是否为空

intPushStack(SeqStack*S,chare);//进栈

intPopStack(SeqStack*S,char*e);//删除栈顶元素

intGetTop(SeqStackS,char*e);//取栈顶元素

voidTranslateExpress(chars1[],chars2[]);//将中缀表达式转为后缀表达式

floatComputeExpress(chars[]);//计算后缀表达式

2、二叉树的创立：

voidCreateBiTree(BiTree*T)

{

charch;

scanf(%c,ch);

if(ch==0)

(*T)=NULL;

else

{

(*T)=newBiTNode;

(*T)-data=ch;

CreateBiTree((*T)-lchild);

CreateBiTree((*T)-rchild);

}

}

3、运算符栈的执行局部：

case+:

x1=S.data[S.top];

S.top--;

x2=S.data[S.top];

S.top--;

result=x1+x2;

S.top++;

S.data[S.top]=result;

break;

case-:

x1=S.data[S.top];

S.top--;

x2=S.data[S.top];

S.top--;

result=x2-x1;

S.top