数据结构上机报告

数据结构上机题3表达式二叉树：表达式可以用表达式二叉树来表示。对于简单的四则运算，实现以下功能：1、对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）、后缀表达式（不带括号），能够在计算机内部构造出一颗表达式二叉树，并且以图示显示出来（字符图货图形的形式）2、对于构造好的内部表达式二叉树，按照用户的要求，输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括号）货后缀表达式（不带括号）。2015、5、21一、需求分析1、输入形式、输入值的范围：输入为正确的前缀、后缀、中缀表达式；2、输出形式：输出为除了输入的表达式以外的其它两种形式的表达式以及所输入表达式所构建的二叉树；3、程序功能：将所输入的任意前缀、中缀、后缀表达式转换成其它两种形式的表达式，并将输入的表达式构建成二叉树的形式输出；二、概要设计1、ADT定义：1）二叉树结点ADT：classBinaryTreeNode//二叉树结点类{private:Tvalue;//结点数据域BinaryTreeNodeT*leftChild;//左孩子结点BinaryTreeNodeT*rightChild;//右孩子结点public:BinaryTreeNode(){leftChild=NULL,rightChild=NULL;};//构造函数（左右孩子初始化为空）BinaryTreeNode(constT&);//构造函数（结点值初始化）BinaryTreeNode(constT&,BinaryTreeNodeT*,BinaryTreeNodeT*);//构造函数（结点值及左右孩子均初始化）voidsetValue(constT&);//设置结点值TgetValue()const;//返回结点值BinaryTreeNodeT*getLeftChild()const;//返回左孩子结点BinaryTreeNodeT*getRightChild()const;//返回右孩子结点voidsetLeftChild(BinaryTreeNodeT*leftChild);//设置左孩子结点voidsetRightChild(BinaryTreeNodeT*rightChild);//设置右孩子结点boolisLeaf()const;//判断是否为树叶};2）表达式二叉树ADTclassExpressionBinaryTree//表达式二叉树类{private:BinaryTreeNodestring*root;//字符串型的二叉树结点voidrecursionDeleteAll(BinaryTreeNodestring*root);//递归函数清空二叉树，释放空间voidclear(){//清空函数if(root==NULL)return;recursionDeleteAll(root);};intgetHeight(BinaryTreeNodestring*root);//求树的高度boolaIsGreaterOrEqualThanB(chara,charb);//比较a,b优先级voidprintBlank(intn);//打印n个空格voidprintInRightFormat(stringvalue);//按照格式打印，以便对齐voidrecursionPrintPreffixE(BinaryTreeNodestring*root);//递归调用打印前缀表达式voidrecursionPrintSuffixE(BinaryTreeNodestring*root);//递归调用打印后缀表达式boolshouldPrintLeftBracket(conststackBinaryTreeNodestring*&nodeStack,BinaryTreeNodestring*pointer,intleftOrRight);//用于输出中缀表达式时判断是否需要输出左括号public:ExpressionBinaryTree();//构造函数~ExpressionBinaryTree(){clear();};//析构函数voidbuildBTreeByPreffixE();//以前缀表达式构建二叉树voidbuildBTreeByInfixE();//以中缀表达式构建二叉树voidbuildBTreeBySuffixE();//以后缀表达式构建二叉树voidprintEBTree();//打印二叉树字符图voidprintPreffixE(){recursionPrintPreffixE(root);coutendl;}//打印前缀表达式voidprintSuffixE(){recursionPrintSuffixE(root);coutendl;}//打印后缀表达式voidprintInfixE();//打印中缀表达式};2、主程序流程：是否（q）三、详细设计实现ADT定义的数据类型：stackBinaryTreeNodestring*二叉树节点字符串类型的栈；queueBinaryTreeNodestring*二叉树节点类型的字符串类型队列。开始（main）ExpressionBinaryTreeebt//创建表达式二叉树的对象选择需要输入的表达式类型根据输入的表达式进行其它形式表达式的转换并构建二叉树输出是否继续输入结束四、用户使用说明根据提示输入正确的表达式（前缀表达式，中缀表达式，后缀表达式任选一）五、测试结果运行程序：根据提示输入相应的正确表达式选择2，输入中缀表达式（12+13）*2-（15*6）/10选择1，输入前缀表达式选择3，输入后缀表达式六、源程序#includetchar.h//为了兼容字符集,使用字符串宏，主要用来定义ascii码和unicode的标准化，使代码移植后，不需要修改相应的代码，重新编译即可使用。#includestack//STL堆栈容器#includesstream//基于字符串的流,字符串流的输入输出操作#includequeue//STL队列容器#includelist//STL线性列表容器(将元素按顺序储存在链表中)#includecmath//包含了许多数学函数的库文件#includeiostreamusingnamespacestd;templateclassTclassBinaryTreeNode//二叉树结点类{private:Tvalue;//结点数据域BinaryTreeNodeT*leftChild;//左孩子结点BinaryTreeNodeT*rightChild;//右孩子结点public:BinaryTreeNode(){leftChild=NULL,rightChild=NULL;};//构造函数（左右孩子初始化为空）BinaryTreeNode(constT&);//构造函数（结点值初始化）BinaryTreeNode(constT&,BinaryTreeNodeT*,BinaryTreeNodeT*);//构造函数（结点值及左右孩子均初始化）voidsetValue(constT&);//设置结点值TgetValue()const;//返回结点值BinaryTreeNodeT*getLeftChild()const;//返回左孩子结点BinaryTreeNodeT*getRightChild()const;//返回右孩子结点voidsetLeftChild(BinaryTreeNodeT*leftChild);//设置左孩子结点voidsetRightChild(BinaryTreeNodeT*rightChild);//设置右孩子结点boolisLeaf()const;//判断是否为树叶};templateclassTBinaryTreeNodeT::BinaryTreeNode(constT&V)//构造函数（结点值初始化）{value=V;leftChild=rightChild=NULL;}templateclassTBinaryTreeNodeT::BinaryTreeNode(constT&V,BinaryTreeNodeT*L,BinaryTreeNode*R)//构造函数（结点值及左右孩子均初始化）{value=V;leftChild=L;rightChild=R;}templateclassTvoidBinaryTreeNodeT::setValue(constT&V)//设置结点的值{value=V;}templateclassTTBinaryTreeNodeT::getValue()const//返回结点值{returnvalue;}templateclassTBinaryTreeNodeT*BinaryTreeNodeT::getLeftChild()const//返回左孩子结点{returnleftChild;}templateclassTBinaryTreeNodeT*BinaryTreeNodeT::getRightChild()const//返回右孩子结点{returnrightChild;}templateclassTvoidBinaryTreeNodeT::setLeftChild(BinaryTreeNodeT*leftChild)//设置左孩子结点{this-leftChild=leftChild;}templateclassTvoidBinaryTreeNodeT::setRightChild(BinaryTreeNodeT*rightChild)//设置右孩子结点{this-rightChild=rightChild;}templateclassTboolBinaryTreeNodeT::isLeaf()const//判断是否为树叶{if(leftChild==NULL&&rightChild==NULL)returntrue;returnfalse;}classExpressionBinaryTree//表达式二叉树类{private:BinaryTreeNodestring*root;//字符串型的二叉树结点voidrecursionDeleteAll(BinaryTreeNodestring*root);//递归函数清空二叉树，释放空间voidclear(){//清空函数if(root==NULL)return;recursionDeleteAll(root);};intgetHeight(BinaryTreeNodestring*root);//求树的高度boolaIsGreaterOrEqualThanB(chara,charb);//比较a,b优先级voidprintBlank(intn);//打印n个空格voidprintInRightFormat(stringvalue);//按照格式打印，以便对齐voidrecursionPrintPreffixE(BinaryTreeNodestring*root);//递归调用打印前缀表达式voidrecursionPrintSuffixE(BinaryTreeNodestring*root);//递归调用打印后缀表达式boolshouldPrintLeftBracket(conststackBinaryTreeNodestring*&nodeStack,BinaryTreeNodestring*pointer,intleftOrRight);//用于输出中缀表达式时判断是否需要输出左括号public:ExpressionBinaryTree();//构造函数~ExpressionBinaryTree()