计算机系数据结构实验报告（5）
实验目的：
树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。
问题描述：
首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。
如算术表达式：a+b*(c-d)-e/f
-
+
a
b
C *
-
d / e
f
实验要求：文法是一个四元
1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算
a) 统计叶子结点的个数。 b) 求二叉树的深度。 2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。 3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。 4、 自动完成求值运算和输出结果。
算法分析：
用二叉树表示表达式，可以按先序次序输入表达式，为了实现四则运算，输入后按书面格式输出原式，再进行运算，最后输出结果。另外，构造两个函数Leaf()和Height()来完成叶子节点和深度的计算。这是流程。
先序输入构造二叉树采用最常用的递归调用，Leaf()和Height()的原理很简单，构造起来不难，主要的问题是字符输入与节点数据会有小数的矛盾和二叉树表示的表达式的运算的规则。
其中注意到，四则运算的数据可能是小数，所以为了与之匹配，节点数据采用浮点型，先把字符输入的数据进行相应的处理，存入一个数组中，再在构造二叉树的时候，从数组中获得数据。运算时则通过判断叶子节点与非叶子节点，进行浮点型与字符型的转换，再按四则运算法则求解，同样需要利用递归调用。
实验内容和过程：
源程序:
#include
//-----二叉树的二叉链表存储表示-----
- 1 -
typedef float TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
int dataprocess() { char ch; int j=1; float m; int flag=0; ch=getchar(); while(ch!='$') { if(!((ch>='0'&&ch<='9')||ch=='.')) { node[j]=(int)ch; flag=0; j++; ch=getchar(); continue; }
if(ch>='0'&&ch<='9'&&flag==1) node[j]=node[j]*10+((int)ch-48); } if(ch=='.') { m=1; --j; ch=getchar(); while(ch>='0'&&ch<='9') { m=0.1*m; node[j]=node[j]+m*((int)ch-48); ch=getchar(); } ++j; continue; } if(ch>='0'&&ch<='9'&&flag==0) { node[j]=(int)ch-48; flag=1; } ++j;
ch=getchar(); } }
int PreCreateBiTree(BiTree &T) { ++i; if(node[i]==35) { T=NULL; return 0; } if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) T->data=node[i]; PreCreateBiTree(T->lchild); PreCreateBiTree(T->rchild);
- 2 -
exit(-1); --j;
{ return 1; }
int output(BiTree T) { char ch; if(!T->lchild&&!T->rchild) cout< int reread(BiTree T) { if(!T) return 0; if((T->data==42||T->data==47)&&(T->lchild->data==43||T->lchild->data==45)) { printf(\ reread(T->lchild); printf(\ } else { reread(T->lchild); } output(T); if((T->data==42||T->data==47)&&(T->rchild->data==43||T->rchild->data==45)) { printf(\ reread(T->rchild); printf(\ } else { reread(T->rchild); } return 1; } int Leaf(BiTree T) { int p,q; if(!T) return 0; if(!T->lchild&&!T->rchild) return 1; p=Leaf(T->lchild); q=Leaf(T->rchild); return p+q; } int Height(BiTree T) { int r,s; if(!T) return 0; r=Height(T->lchild); s=Height(T->rchild); - 3 - return 1+(r>s?r:s); } float result(BiTree T) { float u,v; char c; if(!T->lchild&&!T->rchild) return T->data; u=result(T->lchild); v=result(T->rchild); c=(char)T->data; switch(c) { case '+': return u+v; case '-': return u-v; case '*': return u*v; case '/': return u/(v+0.0); } return 0; } int main() { BiTree T; cout<<\按先序次序输入二叉树(必须以'$'结束)：\ dataprocess(); PreCreateBiTree(T); cout<<\输入的表达式为：\ reread(T); cout< 实验结果： 输入数据：(1+2)*3+(5+6*7); 正确输出：56 - 4 - 输入数据：2.2*（3.1+1.20）-7.5/3 正确结果：6.96 总结和感想： 实验的难点在于对二叉树各种操作的应用，只有充分借鉴书中所学再结合递归算法的巧妙，同时还要有以往程序设计的经验，程序才能完成。 - 5 -