实验6：二叉树及其应用
一、实验目的
树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。
二、问题描述
首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。
其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。
如算术表达式：a+b*(c-d)-e/f
三、实验要求
1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算
a) 统计叶子结点的个数。
b) 求二叉树的深度。
2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。
3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。
4、 自动完成求值运算和输出结果。
四、实验环境
PC 微机
DOS 操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五、实验步骤
1、根据二叉树的各种存储结构建立二叉树；
2、设计求叶子结点个数算法和树的深度算法；
3、根据表达式建立相应的二叉树，生成表达式树的模块；
-
+
/
a
*
b
-
e
f
C
d
4、根据表达式树，求出表达式值，生成求值模块；
5、程序运行效果，测试数据分析算法。
六、功能分析
存储结构
typedef union{
int Operator; // 操作符
float Operand; // 操作数
}Int_Float;
//表达式树
typedef struct BinaryTreeNode{
Int_Float Data; //数据域
int IsOperator; //判断是不是操作数的标志位
struct BinaryTreeNode *RChild;//左子树
struct BinaryTreeNode *LChild;//右子树
}BiTreeNode, *lpBiTreeNode;
//栈的定义
typedef struct {
lpBiTreeNode *base;
lpBiTreeNode *top;
int stacksize;
}SqStack;
函数一览表
lpBiTreeNode GetTop( SqStack s );//取栈顶结点函数
int IsEmpty( SqStack s );//判空函数
int InitStack( SqStack &s );//初始化栈函数
int Pop( SqStack &s, lpBiTreeNode &e );//出栈函数
int Push( SqStack &s, lpBiTreeNode e );//入栈函数
int In( int c, int* op );// 判断c是否在op中
int Precede( int theta1, int theta2 );//比较运算符号的优先级
int isNum( int c );//判断是不是数
int GetInput(Int_Float *Result);//读入输入的数
lpBiTreeNode CreateBiTree();//创建二叉树
bool calculate(lpBiTreeNode Root, float *result);//计算二叉树化表达式的值int getLeafNum(lpBiTreeNode Root);//计算二叉树的叶子结点数
int getDepth(lpBiTreeNode Root);//计算二叉树的深度
计算叶子节点数的算法分析计算二叉树深度的算法分析
递归，核心在于
num=numleft+numright
Int num(二叉树 *p){
If（空树）return 0；
Else if（一个节点的树） return 1；
Else{
Return num（num（左子树）+num（右子树））；}
}
递归，核心在于
depth=max(leftdepth,righydepth)+1
Int depth(二叉树 *p){
If（空树）return 0；
Else if（一个节点的树） return 1；
Else{
Return
max（depth（左子树），depth（右子树）+1）；
}
}
七、程序代码
#include <stdio.h>
#include <malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define ERROR 0
#define NUMBER 1
#define SIMBLE 2
int OP[8] = { '+', '-', '*', '/', '(', ')', '#', 0 };//运算符数组
//共用体
typedef union
{
int Operator; // 操作符
float Operand; // 操作数
}Int_Float;
//表达式树
typedef struct BinaryTreeNode
{
Int_Float Data; //数据域
int IsOperator; //判断是不是操作数的标志位
struct BinaryTreeNode *RChild;//左子树
struct BinaryTreeNode *LChild;//右子树
}BiTreeNode, *lpBiTreeNode;
//栈的定义
typedef struct {
lpBiTreeNode *base;
lpBiTreeNode *top;
int stacksize;
}SqStack;
//函数声明区
lpBiTreeNode GetTop( SqStack s );//取栈顶结点函数
int IsEmpty( SqStack s );//判空函数
int InitStack( SqStack &s );//初始化栈函数
int Pop( SqStack &s, lpBiTreeNode &e );//出栈函数
int Push( SqStack &s, lpBiTreeNode e );//入栈函数
int In( int c, int* op );// 判断c是否在op中
int Precede( int theta1, int theta2 );//比较运算符号的优先级
int isNum( int c );//判断是不是数
int GetInput(Int_Float *Result);//读入输入的数
lpBiTreeNode CreateBiTree();//创建二叉树
bool calculate(lpBiTreeNode Root, float *result);//计算二叉树化表达式的值int getLeafNum(lpBiTreeNode Root);//计算二叉树的叶子结点数
int getDepth(lpBiTreeNode Root);//计算二叉树的深度
int main()//主函数
{
lpBiTreeNode Root;//二叉树
float result; //表达式运算结果
if( Root = CreateBiTree() )//若创建二叉树失败则不会执行if操作
{
printf( "二叉树叶子数= %d\n", getLeafNum(Root) );。