表达式二叉树.pdfVIP

数据结构与算法实习报告 第 4 次上机实习报告 2 数据结构与算法实习报告 诚信保证：我保证没有抄袭他人作业！ 问题部分 1.1 问题描述 【1】对于任意给出的前缀表达式（不带括号） 、中缀表达式（可以带括号）或后 缀表达式（不带括号） ，能够在计算机内部构造出一棵表达式二叉树，并且图示出 来（图形的形式） 。 【2 】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达 式（不带括号） 、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不 带括号）。 （2）输入输出要求： 请输入表达式类型； 请输入表达式类型， 前缀表达式输入 -1 ，中缀表达式输入 0， 后缀表达式输入 1. 请输入字符串表达式： 树形二叉树（图形显示） 中缀表达式为： 前缀表达式为： 后缀表达式为： 1.2 问题分析 一、前缀、中缀、后缀表达式 - 二叉树表达式 2 数据结构实习报告 前缀表达式 - 二叉树表达式：从后往前扫描 （a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈； （b）碰到操作符则把其值赋给相应的新申请的二叉树，若栈非空，从 栈中弹出一个地址， 则栈顶指针所指结点设置成当前结点左孩子， 若栈非空， 再从栈中弹出一个地址，则栈顶指针所指结点设置成当前结点右孩子，操作 完毕后把当前节点压栈，最后一个地址即为二叉树的根结点地址。 中缀表达式 - 二叉树表达式：把中缀表达式转换成后缀表达式，然后再 建立二叉树。 后缀表达式 - 二叉树表达式：从前往后扫描 （a ）碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空 则地址压栈， （b）碰到操作符则把其值赋给相应的新申请的二叉树结点，若当前元 素的左孩子为空则设为其左孩子，左孩子为满则设为其右孩子 , 开始那个元 素地址为根结点地址，开始时用变量 root 保存。 二、二叉树表达式 - 前缀、中缀、后缀表达式 二叉树表达式 - 前缀表达式：对二叉树表达式进行前序遍历。 二叉树表达式 - 中缀表达式：对二叉树表达式进行中序遍历，如果当前 节点的左子树是运算符，且运算符优先级低于当前运算符，那么左边的表达 式要先计算，需要加括号，否则直接输出左子树；如果当前节点的右子树是 运算符，且运算符优先级不高于当前运算符，那么右边的表达式要先计算， 需要加括号，狗则直接输出右子树。 3 4 数据结构与算法实习报告 二叉树表达式 - 后缀表达式：对二叉树表达式进行后序遍历。 2 实现部分 2.1 实现方法分析 节点类 TNode：包含操作符 oper 、左孩子 left 、右孩子 right ，isOper （）判 断是否为操作符， getOperOrder （）返回运算符 op 所对应的优先级， freeTree