浙江大学城市学院实验报告
课程名称                     python高级程序设计                         
实验项目名称     实验五  二叉树的应用----表达式求值                 
实验成绩         指导老师（签名 ）          日期               
一. 实验目的和要求
1、掌握二叉树的链式存储结构；
2、掌握在二叉链表上的二叉树的基本操作；
3、掌握二叉树的简单应用----表达式树的操作。
二. 实验内容
1、在实验四中，已经实现了对一个中缀表达式可以用栈转换成后缀表达式，并可对后缀表达式进行求值计算的方法。另一种思路是可以利用二叉树建立表达式树，通过对该表达式树进行
求值计算，本实验实现：输入一个中缀表达式，建立该表达式的二叉树，然后对该二叉树进行表达式值的计算。
    如一个中缀达式 (6+2)*5 的二叉树表示为如下所示时，该二叉树的后序遍历62+5*正好就是后缀表达式。
设一般数学表达式的运算符包括 +、-、*、/ 四种，当然允许（），且（）优先级高。为方便实现，设定输入的表达式只允许个位整数。要求设计一个完整的程序，对输入的一个日常的中缀表达式，实现以下功能：
⏹ 建立对应的二叉树
⏹ 输出该二叉树的前序序列、中序序列、后序序列
⏹ 求该二叉树的高度
⏹ 求该二叉树的结点总数
⏹ 求该二叉树的叶子结点数
⏹ 计算该二叉树的表达式值
分析：
（1）表达式树的构建方法：
● 构建表达式树的方法之一：直接根据输入的中缀表达式构建
对于任意一个算术中缀表达式，都可用二叉树来表示。表达式对应的二叉树创建后，利用二叉树的遍历等操作，很容易实现二叉树的求值运算。因此问题的关键就是如何创建表达式树。
对于一个中缀表达式来说，其表达式对应的表达式树中叶子结点均为操作数，分支结点均为
运算符。由于创建的表达式树需要准确的表达运算次序，因此，在扫描表达式创建表达式树的过程中，当遇到运算符时不能直接创建结点，而应将其与前面的运算符进行优先级比较，根据比较结果进行处理。这种处理方式在实验四中以采用过，可以借助一个运算符栈，来暂存已经扫描到的还未处理的运算符。
根据表达式树与表达式对应关系的递归定义，每两个操作数和一个运算符就可以建立一棵表达式二叉树，而该二叉树又可以作为另一个运算符结点的一棵子树。可以另外借助一个表达式树栈，来暂存已建立好的表达式树的根结点，以便其作为另一个运算符结点的子树而被引用。
为实现表达式树的创建算法，可以使用两个工作栈，一个称为OPTR，用以暂存运算符；另一个称为EXPT，用以暂存已建立好的表达式树子树的根结点。为了便于实现，假设每个表达式均以“#”开始，以“#”结束，如输入“(6+2)*5#”。
表达式树的创建算法过程如下：
1 初始化OPTR和EXPT，将表达式起始符“#”压入OPTR栈
2 扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR栈顶不为“#”时，则循环执行以下操作：
● 若ch不是运算符，则以ch为根创建一棵只有根结点的二叉树，且将该树根结点压入EXPT栈，读入下一个ch；
● 若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同处理：
小于，则ch压入OPTR栈，读入下一个ch；
大于，则弹出OPTR栈顶运算符，从EXPT栈弹出两个表达式子树的根结点，以该运算符为根结点，以弹出的第二个子树作为左子树，弹出的第一个子树为右子树，创建一棵新二叉树，并将该树根结点压入EXPT栈；
相等，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“（”，相当于括号匹配成功，然后读入下一个ch。
● 构建表达式树的方法之二：直接根据转换后的后缀表达式构建
实验四中已经实现把一个中缀表达式转换成为后缀表达式，则可以在此转换后的后缀表达式基础上构建表达式树，可以省略了前面方法中关于运算符优先级的比较过程，可以直接构建，方法类似于前面方法。
（2）表达式树的求值：
对于构建完成的表达式树，通过中序遍历即可方便求得表达式的值。
1 设变量lvalue和rvalue分别用以记录表达式树中左子树和右子树的值，初始均为0。
2 如果当前结点为叶子（结点为操作数），则返回该结点的数值，否则（结点为运算符）执行以下操作：
● 递归计算左子树的值记为lvalue；
● 递归计算右子树的值记为rvalue；
● 根据当前结点运算符的类型，将lvalue和rvalue进行相应运算并返回。
请仔细阅读上述内容，编程实现输入一个中缀表达式，采用任意一种方法构建表达式树，并完成表达式的计算。为方便约定了初始操作数均个位整数，运算符只包括+、-、*、/种，中间运算结果也均为整数。此外可自行增加合适的功能，可作为额外的实验成绩进行加分，如：
● 操作数扩展到大于个位的整数。
● 操作数扩展到浮点数
● 操作数扩展到负数
● 添加其他运算符
……
2、以小组为单位认真填写实验报告，实验报告可包括各类数据类型的结构定义说明，各类数据的组织方式，系统的功能结构，各个操作的定义以及实现方法，运行结果与分析，难点如何解决，存在问题以及可改进之处等。同时，在实验报告中需写明小组每位同学的分工，得分（小组总分不超过12分）等。
3、实验报告文件取名为表达式求值_(各小组成员名字).doc。每组还必须制作一个答辩PPT，PPT的命名为PPT_表达式求值_(各小组成员名字).PPT。实验报告以及PPT同时作为实验成绩一部分。
4、每位组长上传实验报告文件、源程序文件以及答辩PPT压缩打包后到BB平台上。
5、允许参考其他相应的设计原理方法等，但拒绝复制，一经发现，整小组本次实验成绩计0分处理。
3、实验结果与总结
（1）小组分工
郑博思：建立对应的二叉树、输出该二叉树的前序序列、中序序列、后序序列、ppt制作
郑超：求该二叉树的高度、计算该二叉树的表达式值、ppt制作
徐慧：求该二叉树的结点总数、求该二叉树的叶子结点数、分析实验报告
（二）代码分析如下：
class tree:
    def __init__(self):
        self.data=0
        self.left=None
        self.right=None
分析：中序遍历子程序：二叉树不为空，遍历首先遍历左子树，然后访问根结点，最后遍历右子树。   
def inorder(ptr):   
    if ptr!=None:
        inorder(ptr.left)
        print(ptr.data,' ',end='')
        inorder(ptr.right)
分析：前序遍历子程序 ：二叉树不为空，首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
def preorder(ptr):     
    if ptr!=None:
        print(ptr.data,' ', end='')
        preorder(ptr.left)
        preorder(ptr.right)
分析：后序遍历子程序：首先遍历左子树，然后遍历右子树，最后访问根结点。
def postorder(ptr):   
    if ptr!=None:
        postorder(ptr.left)
        postorder(ptr.right)
        print(ptr.data,' ',end='')
分析：求二叉树的结点总数：如果是空树则为0，如果不是计算根节点左子树与根节点右子树，再将左子树节点个数+右子树节点个数+根节点个数1=即为整颗树的节点个数。
def nodecount(ptr): 
先序中序后序遍历二叉树    if ptr==None:
        return 0
    else:
        return nodecount(ptr.left)+nodecount(ptr.right)+1
分析：递归求叶子节点个数：如果是空树，叶子节点为0，返回0；左、右子树均不为空，则
是叶子节点，且叶子节点数为1，返回1根节点的子树叶子节点数 = 左子树叶子节点数 +T右子树叶子节点数。
def leave(ptr):
    if ptr==None:
        return 0
    elif ptr.lchild ==None hild == None :
        return 1
    else:
        return (self.leave(ptr.lchild)+self.hild))
         
分析：求二叉树的深度：若不为空树，m为左子树的深度，n为右子树的深度，取两者最大在
加上一个根结点。
def TreeDepth(ptr):
    if ptr==None:
        return 0
    else:
        m=TreeDepth(ptr.left)
        n=TreeDepth(ptr.right)
        return max(m,n)+1
分析：建立二叉树的函数
def create_tree(root,val):   
    newnode=tree()
    newnode.data=val
    newnode.left=None
    newnode.right=None
    if root==None:
        root=newnode
        return root
    else:
        current=root
        while current!=None:
            backup=current
            if current.data > val:
                current=current.left
            else:
                current=current.right
        if backup.data >val:

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。