实验6：二叉树及其应用

《实验6：二叉树及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验6：二叉树及其应用一、实验目的树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。二、问题描述首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。-+/ab-efCd如算术表达式：a+b(c-d)-e/f三、实验要求1、如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算a)统计叶子结点的个数。b)求二叉树的深度。2、十进制的四则运算的计算器可以接收用户来自键盘的输入。3、由输入的表达式字符串动态生成算术表达式所对应的二叉树。4、自动完

2、成求值运算和输出结果。 四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境 五、实验步骤1、根据二叉树的各种存储结构建立二叉树；2、设计求叶子结点个数算法和树的深度算法；3、根据表达式建立相应的二叉树，生成表达式树的模块；164、根据表达式树，求出表达式值，生成求值模块；5、程序运行效果，测试数据分析算法。六、功能分析存储结构typedefunion{intOperator;//操作符floatOperand;//操作数}Int_Float;//表达式树typedefstructBinaryTreeNode{Int_Floa

3、tData;//数据域intIsOperator;//判断是不是操作数的标志位structBinaryTreeNodeRChild;//左子树structBinaryTreeNodeLChild;//右子树}BiTreeNode,lpBiTreeNode;//栈的定义typedefstruct{lpBiTreeNodebase;lpBiTreeNodetop;intstacksize;}SqStack;函数一览表lpBiTreeNodeGetTop(SqStacks);//取栈顶结点函数intIsEmpty(SqStacks);//判空函数intInitStack(SqStack&s);

4、//初始化栈函数intPop(SqStack&s,lpBiTreeNode&e);//出栈函数intPush(SqStack&s,lpBiTreeNodee);//入栈函数intIn(intc,intop);//判断c是否在op中intPrecede(inttheta1,inttheta2);//比较运算符号的优先级intisNum(intc);//判断是不是数intGetInput(Int_FloatResult);//读入输入的数lpBiTreeNodeCreateBiTree();//创建二叉树boolcalculate(lpBiTreeNodeRoot,floatresult);

5、//计算二叉树化表达式的值intgetLeafNum(lpBiTreeNodeRoot);//计算二叉树的叶子结点数intgetDepth(lpBiTreeNodeRoot);//计算二叉树的深度16计算叶子节点数的算法分析计算二叉树深度的算法分析递归，核心在于num=numleft+numrightIntnum(二叉树p){If（空树）return0；Elseif（一个节点的树）return1；Else{Returnnum（num（左子树）+num（右子树））；}}递归，核心在于depth=max(leftdepth,righydepth)+1Intdepth(二叉树p){If（空树）

6、return0；Elseif（一个节点的树）return1；Else{Returnmax（depth（左子树），depth（右子树）+1）；}}七、程序代码#include#include#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineERROR0#defineNUMBER1#defineSIMBLE2intOP[8]={'+','-','','/','(',')','#',0};//运算符数组//共用体typedefunion{intOperator;//操作符floatOperand;

7、//操作数}Int_Float;//表达式树typedefstructBinaryTreeNode16{Int_FloatData;//数据域intIsOperator;//判断是不是操作数的标志位structBinaryTreeNodeRChild;//左子树structBinaryTreeNodeLChild;//右子树}BiTreeNode,lpBiTreeNode;//栈的定义typedefstruct{lpBiTreeNo