实验二叉树及其应用#严选材料

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

2、、 自动完成求值运算和输出结果。四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境五、实验步骤1、根据二叉树的各种存储结构建立二叉树；2、设计求叶子结点个数算法和树的深度算法；3、根据表达式建立相应的二叉树，生成表达式树的模块；4、根据表达式树，求出表达式值，生成求值模块；5、程序运行效果，测试数据分析算法。六、功能分析存储结构typedef unionint Operator; / 操作符float Operand; / 操作数Int_Float;/表达式树typedef struct BinaryTreeNodeI

3、nt_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

4、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();/创建

5、二叉树bool calculate(lpBiTreeNode Root, float *result);/计算二叉树化表达式的值int getLeafNum(lpBiTreeNode Root);/计算二叉树的叶子结点数int getDepth(lpBiTreeNode Root);/计算二叉树的深度计算叶子节点数的算法分析计算二叉树深度的算法分析递归，核心在于num=numleft+numrightInt num(二叉树 *p)If（空树）return 0；Else if（一个节点的树） return 1；ElseReturn num（num（左子树）+num（右子树）；递归，核心在于dep

6、th=max(leftdepth,righydepth)+1Int depth(二叉树 *p)If（空树）return 0；Else if（一个节点的树） return 1；ElseReturn max（depth（左子树），depth（右子树）+1）；七、程序代码#include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define NUMBER 1#define SIMBLE 2int OP8 = +, -, *, /, (, ), #, 0 ;/运算符数组 /共用体 type

7、def unionint Operator; / 操作符float Operand; / 操作数Int_Float;/表达式树typedef struct BinaryTreeNodeInt_Float Data;/数据域 int IsOperator; /判断是不是操作数的标志位 struct BinaryTreeNode *RChild;/左子树 struct BinaryTreeNode *LChild;/右子树 BiTreeNode, *lpBiTreeNode;/栈的定义 typedef struct lpBiTreeNode *base;lpBiTreeNode *top;int

8、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 );/

9、比较运算符号的优先级 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;/二叉

10、树 float result;/表达式运算结果 if( Root = CreateBiTree() )/若创建二叉树失败则不会执行if操作 printf( 二叉树叶子数= %dn, getLeafNum(Root) );printf( 二叉树的深度= %dn, getDepth(Root) );if( calculate(Root, &result) )/计算结果 printf(表达式的值= %0.2fn, result);elseprintf(ERROR);elseprintf(INPUT ERRORn);printf(*n);return 0;lpBiTreeNode GetTop( Sq

11、Stack s )lpBiTreeNode e;if( s.top = s.base )/栈为空情况 return NULL;e = *(s.top -1);/top指针指向栈顶元素的后一个空间 return e;int IsEmpty( SqStack s )if( s.top = s.base )/栈为空 return 1;else return 0;int InitStack( SqStack &s )s.base = (lpBiTreeNode *)malloc( STACK_INIT_SIZE*sizeof(lpBiTreeNode) );/malloc栈基址空间 if(!s.bas

12、e)/分配空间失败 return 0;s.top = s.base;/栈顶指针 s.stacksize = STACK_INIT_SIZE;/初始化栈大小 return 1;int Pop( SqStack &s, lpBiTreeNode &e )if( s.top = s.base )/空栈 return 0;s.top -;/top指针前移 e = *s.top;/取栈顶元素 return 1;int Push( SqStack &s, lpBiTreeNode e )/入栈函数 if( s.top - s.base = s.stacksize )/空间已满 s.base = (lpBi

13、TreeNode *)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;/元素e入栈 s.top +;/栈顶指针后移 return 1;int In( int c, int* op ) / 判断c 是否在op 中，op为以结尾的数组while( *op != 0 )/比较所有元素，

14、最后一个为0 if( c = *op )/相等 ，存在 return 1 return 1;op +;/op指针后移 return 0;int Precede( int theta1, int theta2 )/比较优先级 int i, j;int op_look77 = , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , = 0 & c Operator = result.Operator;return SIMBLE; / 符号/ 去前导空格c = getchar();while ( c

15、= & 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;elseresult.Operand = result.Operand*10 + c;IsFloat +;else if(c = .)if(IsFloat != 0)/ 两个小数点Result-Operand = 0;return ERROR;elseIsFloat = 1

16、;else if (In(c, OP) if(IsNumber) / 数字后接符号if(IsFloat = 1)Result-Operand = 0;return ERROR;elsebuffer = 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;

17、elsefor(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 th

18、eta,a,b;Int_Float c;printf(*n);printf(QAQ请输入一个算式并以#号结尾：n);int r = GetInput(&c);InitStack(Operand);/初始化操作数栈 InitStack(Operator);/初始化操作符栈 pNode = (lpBiTreeNode)malloc(sizeof(BiTreeNode);pNode-Data.Operator = #;pNode-IsOperator = 1;pNode-LChild = NULL;pNode-RChild = NULL;Push( Operator, pNode );while(

19、!( r = SIMBLE & c.Operator = #) | GetTop(Operator)-Data.Operator != # )/处理到# if(r = ERROR)return NULL;if( r = NUMBER ) / 是数字pNode = (lpBiTreeNode)malloc(sizeof(BiTreeNode);pNode-Data.Operand = c.Operand;pNode-IsOperator = 0;pNode-LChild = NULL;pNode-RChild = NULL;Push(Operand,pNode);r = GetInput(&c)

20、;else if( r = SIMBLE ) / 是符号switch( Precede(GetTop(Operator)-Data.Operator, c.Operator) )case Data.Operator = c.Operator;pNode-IsOperator = 1;pNode-LChild = NULL;pNode-RChild = NULL;Push( Operator, pNode );r = GetInput(&c);break;case =: / (, )相遇，脱括号Pop( Operator, pNode );r = GetInput(&c);break;case

21、: / 栈顶元素优先权高, 退栈并将运算结果入栈Pop( Operator, theta );Pop( Operand, b);Pop( Operand, a);theta-LChild = a;theta-RChild = b;Push(Operand, theta);break;return GetTop(Operand);bool calculate(lpBiTreeNode Root, float *result)/计算二叉树的值 float resultLchild;float resultRchild;if( Root != NULL )/非空 if(Root-LChild = N

22、ULL & Root-RChild = NULL)/叶子节点 *result = Root-Data.Operand;return true;else if(Root-LChild = NULL | Root-RChild = NULL)/不可能出现单子树情况 return false;else/左右子树都存在的情况 ，递归计算 switch (Root-Data.Operator)/取操作符 case +:if( calculate(Root-LChild, &resultLchild)=false ) return false;if( calculate(Root-RChild, &res

23、ultRchild)=false )return false;*result = resultLchild + resultRchild;/该二叉树的值等于左子树的值加上右子树的值break;case -:if( calculate(Root-LChild, &resultLchild)=false )return false;if( calculate(Root-RChild, &resultRchild)=false ) return false;*result = resultLchild - resultRchild;/该二叉树的值等于左子树的值减去右子树的值break;case *:

24、if( calculate(Root-LChild, &resultLchild)=false )return false;if( calculate(Root-RChild, &resultRchild)=false ) return false;*result = resultLchild * resultRchild;/该二叉树的值等于左子树的值乘上右子树的值break;case /:if( calculate(Root-LChild, &resultLchild)=false )return false;if( calculate(Root-RChild, &resultRchild)

25、=false )return false;*result = resultLchild / resultRchild;/该二叉树的值等于左子树除以加上右子树的值break;return true;int getLeafNum(lpBiTreeNode Root)/计算叶子节点数 int LeafnumLchild;/左子树的叶子结点数 int LeafnumRchild;/右左子树的叶子结点数 if( Root != NULL )/非空 if(Root-LChild = NULL & Root-RChild = NULL)/该结点是叶子节点return 1;elseLeafnumLchild = getLeafNum(Root-LChild);/递归计算左子树的num LeafnumRchild = getLeafNum(Root-RChild);/递归计算右子树的num return LeafnumLchild + LeafnumRchild;/总的叶子节