实验六_二叉树及其应用

实验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");