实验六_二叉树及其应用实验6:二叉树及其应用
一、实验目的
树是数据结构中应用极为广泛的非线性结构,本单元的实验达到熟悉二叉树的存储结构的特性,以及如何应用树结构解决具体问题。
二、问题描述
首先,掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次,以二叉树表示算术表达式的基础上,设计一个十进制的四则运算的计算器。
如算术表达式:a+b*(c-d)-e/f
三、实验要求
1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树,分别计算
a) 统计叶子结点的个数。
b) 求二叉树的深度。
2、 十进制的四则运算的计算器可以接收用户来自键盘...
实验6:二叉树及其应用
一、实验目的
树是数据结构中应用极为广泛的非线性结构,本单元的实验达到熟悉二叉树的存储结构的特性,以及如何应用树结构解决具体问
。
二、问题描述
首先,掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次,以二叉树表示算术表达式的基础上,设计一个十进制的四则运算的计算器。
如算术表达式:a+b*(c-d)-e/f
三、实验要求
1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树,分别计算
a) 统计叶子结点的个数。
b) 求二叉树的深度。
2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。
3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。
4、 自动完成求值运算和输出结果。
四、实验环境
PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五、实验步骤
1、根据二叉树的各种存储结构建立二叉树;
2、设计求叶子结点个数算法和树的深度算法;
3、根据表达式建立相应的二叉树,生成表达式树的模块;
4、根据表达式树,求出表达式值,生成求值模块;
5、程序运行效果,测试数据
算法。
设计程序代码如下:
#include
#include
#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;
int InitStack( SqStack &s )
{
s.base = (lpBiTreeNode *)malloc( STACK_INIT_SIZE*sizeof(lpBiTreeNode) );
if(!s.base)
return 0;
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
return 1;
}
int Push( SqStack &s, lpBiTreeNode e )
{
if( s.top - s.base >= s.stacksize )
{
s.base = (lpBiTreeNode *)realloc( s.base, (s.stacksize + STACKINCREMENT)*sizeof(lpBiTreeNode) );
if(!s.base)
return 0;
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
*s.top = e;
s.top ++;
return 1;
}
int Pop( SqStack &s, lpBiTreeNode &e )
{
if( s.top == s.base )
return 0;
s.top --;
e = *s.top;
return 1;
}
lpBiTreeNode GetTop( SqStack s )
{
lpBiTreeNode e;
if( s.top == s.base )
return NULL;
e = *(s.top -1);
return e;
}
int IsEmpty( SqStack s )
{
if( s.top == s.base )
return 1;
else
return 0;
}
int In( int c, int* op ) // 判断c 是否在op 中,op为以结尾的数组
{
while( *op != 0 )
{
if( c == *op )
return 1;
op ++;
}
return 0;
}
int Precede( int theta1, int theta2 )
{
int i, j;
int op_look[7][7] =
{ { '>', '>', '<', '<', '<', '>', '>' },
{ '>', '>', '<', '<', '<', '>', '>' },
{ '>', '>', '>', '>', '<', '>', '>' },
{ '>', '>', '>', '>', '<', '>', '>' },
{ '<', '<', '<', '<', '<', '=', ' ' },
{ '>', '>', '>', '>', ' ', '>', '>' },
{ '<', '<', '<', '<', '<', ' ', '=' }
};
switch( theta1 )
{
case '+':
i = 0;
break;
case '-':
i = 1;
break;
case '*':
i = 2;
break;
case '/':
i = 3;
break;
case '(':
i = 4;
break;
case ')':
i = 5;
break;
case '#':
i = 6;
break;
default:
return 0;
}
switch( theta2 )
{
case '+':
j = 0;
break;
case '-':
j = 1;
break;
case '*':
j = 2;
break;
case '/':
j = 3;
break;
case '(':
j = 4;
break;
case ')':
j = 5;
break;
case '#':
j = 6;
break;
default:
return 0;
}
return op_look[i][j];
}
int isNum( int c )
{
if( c >= '0' && c <= '9' )
return 1;
else return 0;
}
int GetInput(Int_Float *Result) // 返回值:无,1数字,2符号
{
static int buffer = 0; // 缓存存储数字后的符号
int c;
Int_Float result;
int IsNumber = 0; // 是否为数字
int IsFloat = 0; // 是否为小数
int i,t=1;
result.Operand = 0;
if(In(buffer, OP)) // 缓存中有符号,返回
{
result.Operator = buffer;
buffer = 0;
Result->Operator = result.Operator;
return SIMBLE; // 符号
}// 去前导空格
c = getchar();
while ( c == ' ' && c != 10 )
{
c = getchar();
}
while( c != ' ' && c != 10 ) // 不是空格和回车
{
if(isNum(c)) // 是数字
{
IsNumber = 1;
c = c - 48; // 字符到整型
if(IsFloat == 0)
result.Operand = result.Operand*10 + c;
else
{
result.Operand = result.Operand*10 + c;
IsFloat ++;
}
}
else if(c == '.')
{
if(IsFloat != 0) // 两个小数点
{
Result->Operand = 0;
return ERROR;
}
else
IsFloat = 1;
}
else if (In(c, OP))
{
if(IsNumber) // 数字后接符号
{
if(IsFloat == 1)
{
Result->Operand = 0;
return ERROR;
}
else
{
buffer = c;
for(i=0; iOperand = result.Operand/(float)t;
return NUMBER; // 数字
}
}
else
{
Result->Operator = c;
return SIMBLE; // 符号
}
}
c = getchar();
}
buffer = 0;
if(IsNumber)
{
if(IsFloat == 1)
{
Result->Operand = 0;
return ERROR;
}
else
{
for(i=0; iOperand = result.Operand/(float)t;
return NUMBER;
}
}
else if(result.Operand == 0)
{
Result->Operand = 0;
return ERROR;
}
else
{
Result->Operator = result.Operator;
return SIMBLE;
}
}
lpBiTreeNode CreateBiTree()
{
SqStack Operand; // 操作数
SqStack Operator; // 操作符
lpBiTreeNode pNode;
lpBiTreeNode theta,a,b;
Int_Float c;
printf("输入算式,以'#'结尾\n");
本文档为【实验六_二叉树及其应用】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。