数据结构上机报告.doc

《数据结构上机报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构上机题3表达式二叉树：表达式可以用表达式二叉树来表示。对于简单的四则运算，实现以下功能：1、对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）、后缀表达式（不带括号），能够在计算机内部构造出一颗表达式二叉树，并且以图示显示出来（字符图货图形的形式）2、对于构造好的内部表达式二叉树，按照用户的要求，输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括号）货后缀表达式（不带括号）。2015、5、21一、需求分析1、输入形式、输入值的范围：输入为正确的前缀、后缀、中缀表达式；2、输出形式：输出为除了输入的表达式以外的其它两种形式的表达式以及所输入表达

2、式所构建的二叉树；3、程序功能：将所输入的任意前缀、中缀、后缀表达式转换成其它两种形式的表达式，并将输入的表达式构建成二叉树的形式输出；二、概要设计1、ADT定义：1）二叉树结点ADT：classBinaryTreeNode//二叉树结点类{private:Tvalue;//结点数据域BinaryTreeNode*leftChild;//左孩子结点BinaryTreeNode*rightChild;//右孩子结点public:BinaryTreeNode(){leftChild=NULL,rightChild=NULL;};//构造函数（左右孩子初始化为空）BinaryT

3、reeNode(constT&);//构造函数（结点值初始化）BinaryTreeNode(constT&,BinaryTreeNode*,BinaryTreeNode*);//构造函数（结点值及左右孩子均初始化）voidsetValue(constT&);//设置结点值TgetValue()const;//返回结点值BinaryTreeNode*getLeftChild()const;//返回左孩子结点BinaryTreeNode*getRightChild()const;//返回右孩子结点voidsetLeftChild(BinaryTreeNode

4、*leftChild);//设置左孩子结点voidsetRightChild(BinaryTreeNode*rightChild);//设置右孩子结点boolisLeaf()const;//判断是否为树叶};2）表达式二叉树ADTclassExpressionBinaryTree//表达式二叉树类{private:BinaryTreeNode*root;//字符串型的二叉树结点voidrecursionDeleteAll(BinaryTreeNode*root);//递归函数清空二叉树，释放空间voidclear(){//清空函数if(root=

5、=NULL)return;recursionDeleteAll(root);};intgetHeight(BinaryTreeNode*root);//求树的高度boolaIsGreaterOrEqualThanB(chara,charb);//比较a,b优先级voidprintBlank(intn);//打印n个空格voidprintInRightFormat(stringvalue);//按照格式打印，以便对齐voidrecursionPrintPreffixE(BinaryTreeNode*root);//递归调用打印前缀表达式voidrecur

6、sionPrintSuffixE(BinaryTreeNode*root);//递归调用打印后缀表达式boolshouldPrintLeftBracket(conststack*>&nodeStack,BinaryTreeNode*pointer,intleftOrRight);//用于输出中缀表达式时判断是否需要输出左括号public:ExpressionBinaryTree();//构造函数~ExpressionBinaryTree(){clear();};//析构函数voidbuildBTreeByP

7、reffixE();//以前缀表达式构建二叉树voidbuildBTreeByInfixE();//以中缀表达式构建二叉树voidbuildBTreeBySuffixE();//以后缀表达式构建二叉树voidprintEBTree();//打印二叉树字符图voidprintPreffixE(){recursionPrintPreffixE(root);cout<