简单算术表达式的二叉树的构建和求值

二叉树的建立与基本操作二叉树是一种特殊的树形结构，它由节点（node）组成，每个节点最多有两个子节点。

二叉树的基本操作包括建立二叉树、遍历二叉树、查找二叉树节点、插入和删除节点等。

本文将详细介绍二叉树的建立和基本操作，并给出相应的代码示例。

一、建立二叉树建立二叉树有多种方法，包括使用数组、链表和前序、中序、后序遍历等。

下面以使用链表的方式来建立二叉树为例。

1.定义二叉树节点类首先，定义一个二叉树节点的类，包含节点值、左子节点和右子节点三个属性。

```pythonclass Node:def __init__(self, value):self.value = valueself.left = Noneself.right = None```2.建立二叉树使用递归的方法来建立二叉树，先构造根节点，然后递归地构造左子树和右子树。

```pythondef build_binary_tree(lst):if not lst: # 如果 lst 为空，则返回 Nonereturn Nonemid = len(lst) // 2 # 取 lst 的中间元素作为根节点的值root = Node(lst[mid])root.left = build_binary_tree(lst[:mid]) # 递归构造左子树root.right = build_binary_tree(lst[mid+1:]) # 递归构造右子树return root```下面是建立二叉树的示例代码：```pythonlst = [1, 2, 3, 4, 5, 6, 7]root = build_binary_tree(lst)```二、遍历二叉树遍历二叉树是指按照其中一规则访问二叉树的所有节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。

1.前序遍历前序遍历是指先访问根节点，然后访问左子节点，最后访问右子节点。

```pythondef pre_order_traversal(root):if root:print(root.value) # 先访问根节点pre_order_traversal(root.left) # 递归访问左子树pre_order_traversal(root.right) # 递归访问右子树```2.中序遍历中序遍历是指先访问左子节点，然后访问根节点，最后访问右子节点。

/*一下总结一些二叉树的常见操作：包括建立二叉树先/中/后序遍历二叉树求二叉树的叶子节点个数求二叉树的单分支节点个数计算二叉树双分支节点个数计算二叉树的高度计算二叉树的所有叶子节点数*/#include<stdio.h> //c语言的头文件#include<stdlib.h>//c语言的头文件stdlib.h千万别写错了#define Maxsize 100/*创建二叉树的节点*/typedef struct BTNode //结构体struct 是关键字不能省略结构体名字可以省略（为无名结构体）//成员类型可以是基本型或者构造形，最后的为结构体变量。

{char data;struct BTNode *lchild,*rchild;}*Bitree;/*使用先序建立二叉树*/Bitree Createtree() //树的建立{char ch;Bitree T;ch=getchar(); //输入一个二叉树数据if(ch==' ') //' '中间有一个空格的。

T=NULL;else{ T=(Bitree)malloc(sizeof(Bitree)); //生成二叉树(分配类型*)malloc(分配元素个数*sizeof(分配类型))T->data=ch;T->lchild=Createtree(); //递归创建左子树T->rchild=Createtree(); //地柜创建右子树}return T;//返回根节点}/*下面先序遍历二叉树*//*void preorder(Bitree T) //先序遍历{if(T){printf("%c-",T->data);preorder(T->lchild);preorder(T->rchild);}} *//*下面先序遍历二叉树非递归算法设计*/void preorder(Bitree T) //先序遍历非递归算法设计{Bitree st[Maxsize];//定义循环队列存放节点的指针Bitree p;int top=-1; //栈置空if(T){top++;st[top]=T; //根节点进栈while(top>-1) //栈不空时循环{p=st[top]; //栈顶指针出栈top--;printf("%c-",p->data );if(p->rchild !=NULL) //右孩子存在进栈{top++;st[top]=p->rchild ;}if(p->lchild !=NULL) //左孩子存在进栈{top++;st[top]=p->lchild ;}}printf("\n");}}/*下面中序遍历二叉树*//*void inorder(Bitree T) //中序遍历{if(T){inorder(T->lchild);printf("%c-",T->data);inorder(T->rchild);}}*//*下面中序遍历二叉树非递归算法设计*/void inorder(Bitree T) //中序遍历{Bitree st[Maxsize]; //定义循环队列，存放节点的指针Bitree p;int top=-1;if(T){p=T;while (top>-1||p!=NULL) //栈不空或者*不空是循环{while(p!=NULL) //扫描*p的所有左孩子并进栈{top++;st[top]=p;p=p->lchild ;}if(top>-1){p=st[top]; //出栈*p节点，它没有右孩子或右孩子已被访问。

浙江大学城市学院实验报告课程名称python高级程序设计实验项目名称实验五二叉树的应用----表达式求值实验成绩指导老师（签名）日期一.实验目的和要求1、掌握二叉树的链式存储结构；2、掌握在二叉链表上的二叉树的基本操作；3、掌握二叉树的简单应用----表达式树的操作。

二.实验内容1、在实验四中，已经实现了对一个中缀表达式可以用栈转换成后缀表达式，并可对后缀表达式进行求值计算的方法。

另一种思路是可以利用二叉树建立表达式树，通过对该表达式树进行求值计算，本实验实现：输入一个中缀表达式，建立该表达式的二叉树，然后对该二叉树进行表达式值的计算。

如一个中缀达式(6+2)*5 的二叉树表示为如下所示时，该二叉树的后序遍历62+5*正好就是后缀表达式。

设一般数学表达式的运算符包括+、-、*、/ 四种，当然允许（），且（）优先级高。

为方便实现，设定输入的表达式只允许个位整数。

要求设计一个完整的程序，对输入的一个日常的中缀表达式，实现以下功能：⏹建立对应的二叉树⏹输出该二叉树的前序序列、中序序列、后序序列⏹求该二叉树的高度⏹求该二叉树的结点总数⏹求该二叉树的叶子结点数⏹计算该二叉树的表达式值分析：（1）表达式树的构建方法：●构建表达式树的方法之一：直接根据输入的中缀表达式构建对于任意一个算术中缀表达式，都可用二叉树来表示。

表达式对应的二叉树创建后，利用二叉树的遍历等操作，很容易实现二叉树的求值运算。

因此问题的关键就是如何创建表达式树。

对于一个中缀表达式来说，其表达式对应的表达式树中叶子结点均为操作数，分支结点均为运算符。

由于创建的表达式树需要准确的表达运算次序，因此，在扫描表达式创建表达式树的过程中，当遇到运算符时不能直接创建结点，而应将其与前面的运算符进行优先级比较，根据比较结果进行处理。

这种处理方式在实验四中以采用过，可以借助一个运算符栈，来暂存已经扫描到的还未处理的运算符。

根据表达式树与表达式对应关系的递归定义，每两个操作数和一个运算符就可以建立一棵表达式二叉树，而该二叉树又可以作为另一个运算符结点的一棵子树。

山西大学课程设计任务书设计题目算术表达式与二叉树所属课程：数据结构系别软件学院专业软件工程班级软工1408班姓名霍志斌指导教师李雪梅设计任务下达日期 2015年 12 月15 日设计时间2016年1月4日至 2016年1月8日目录：一、需求分析二、概要设计1、数据类型的声明：2、表达式的抽象数据类型定义3、整体设计三、详细设计1、二叉树的存储类型2、顺序栈的存储类型3、表达式的基本操作4、主程序和其他伪码算法5、函数的调用关系四、设计和调试分析五、测试六、课程设计的心得和心得以及问题一、需求分析【课程设计要求】【问题的描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。

写一个程序，实现基于二叉树表示的算术表达式Expression的操作。

【基本要求】假设算术表达式Expression内可以含有变量（a-z）,常量（0-9）和二元运算符（+，-，*，/，^（乘幂））。

实现以下操作：（1）ReadExpr(E)――以字符序列的形式输入语法正确的前缀表达式并构造表达式E。

（2）WriteExpr(E)――用带括号的中缀表达式输出表达式E。

（3）Assign(V，c)――实现对变量V的赋值（V=c），变量的初值为0。

（4）Value(E)――对算术表达式E求值。

（5）CompoundExpr(p,E1,E2)――构造一个新的复合表达式（E1）p（E2）。

【测试数据】1)分别输入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并输出。

2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。

二、概要设计1、数据类型的声明：在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0typedef int Status;2、表达式的抽象数据类型定义ADT Expression{数据对象D：D是具有数值的常量C和没有数值的变量V；数据关系：R={<(V或者C)P(V或者C)>|V,C∈D, <(V或者C)P(V或者C)>表示由运算符P结合起来的表达式E}基本操作：Status Input_Expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string；参数flag表示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。

实验报告课程名称： 程序设计与数据结构 指导老师： ljq 成绩： 实验名称：基于二叉树结构的表达式求值算法 实验类型： 上机 同组学生姓名：一、实验目的和要求（必填）三、代码缺陷及修正记录五、讨论、心得二、实验内容和代码（必填） 四、实验结果与分析（必填）一、实验目的和要求1. 掌握编程工具的使用2. 掌握二叉树数据结构在计算机上的实现3. 掌握通过计算机编程解决问题的基本方法二、实验内容和代码1．实验内容：● 编程实现基于二叉树结构的表达式求值算法● 表达式包含加减乘除四则运算以及至少一层括弧运算● 首先将输入的原表达式转换成二叉树结构，然后采用二叉树的后序递归遍历方法求得表达式的值● 将所有实验内容合并到一个工程，增加交互操作和循环处理（持续）2．代码1.头文件expnbitree .h装订 线1 2 3 4 5 6 7 8 91011121314151617181920212223 #include<stdio.h>#include<string.h>#include<stdlib.h>#define EXP_LEN 100 //定义表达式的最大长度#define DATA_LEN 20 //定义每个操作数的最大长度typedef struct BiTNode{int dflag; //标志域,值为1,data[]存放操作运算符;值为0,data[]存放操作数char data[DATA_LEN + 1]; //数据域,存放:操作运算符或操作数struct BiTNode *lchild, *rchild; //分别指向结点的左、右子树}BiTNode, *BiTree; //定义二叉树结点及二叉树类型指针int CreateBiTree(BiTree &bt, char *p, int len);//创建二叉树,并用bt返回树的根地址,p为表达式的首地址,l为表达式的长度int Calculate(BiTree bt, double &rst);//计算表达式的值,bt为据表达式创建的二叉树,用rst返回表达式的值int PreOrderTraverse(BiTree bt);//先序遍历二叉树bt,输出先序遍历序列int InOrderTraverse(BiTree bt); //中序遍历二叉树bt,输出中序遍历序列int PostOrderTraverse(BiTree bt); //后序遍历二叉树bt,输出后序遍历序列int DestroyBiTree(BiTree &bt); //销毁二叉树//二叉树结构的表达式求解算法入口void expnbitree();2.源文件expntree.c1 2 3 4 5 6 7 8 910111213141516 #include<stdio.h>#include<string.h>#include<stdlib.h>#include"expnbitree.h"//ExpnBiTree实现子程序入口void expnbitree(){int n, len, i; //n标志量,值为0,退出程序;len存储表达式的长度;i一般变量char expn[EXP_LEN + 1]; //存放表达式double rst; //存放表达式计算结果BiTree bt = NULL; //声明一个二叉树gets_s(expn);do{1718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 i = 0;printf("请输入合法的表达式:\n");gets_s(expn);for (i = 0, len = 0; expn[i] != '\0'; i++) //去掉表达式中的空格,并计算表达式的长度if (expn[i] != ' ')expn[len++] = expn[i];expn[len] = '\0';printf("正在构建二叉树……\n");if (CreateBiTree(bt, expn, len))printf("二叉树构建成功!\n");else{ //销毁未成功建立的二叉树,释放动态申请的内存printf("二叉树构建失败!\n");printf("将销毁二叉树…………");if (DestroyBiTree(bt))printf("二叉树销毁成功!\n");else {printf("二叉树销毁失败!\n");exit(0);}continue;}printf("输出表达式的先序遍历序列……:\n");PreOrderTraverse(bt);printf("\n");printf("输出表达式的中序遍历序列……:\n");InOrderTraverse(bt);printf("\n");printf("输出表达式的后序遍历序列……:\n");PostOrderTraverse(bt);printf("\n");printf("计算表达式的值……:\n");if (Calculate(bt, rst))printf("%g\n", rst);elseprintf("计算表达式的值失败!\n");printf("即将销毁二叉树…………");if (DestroyBiTree(bt))printf("二叉树销毁成功!\n");else {printf("二叉树销毁失败!\n");exit(0);}printf("如果要继续计算下一个表达式,请输入1,否则,返回上一级:\n ");616263646566676869707172737475767778798081828384858687888990919293949596979899 100 101 102 103 104scanf_s("%d", &n);getchar();} while (n==1);}//创建二叉树int CreateBiTree(BiTree &bt, char *p, int len){int i = 0, lnum = 0, rpst1 = -1, rpst2 = -1, pn = 0;//lnum记录"("的未成对个数;//rpst1/rpst2记录表达式中优先级最低的("*"、"/")/("+"、"-")的位置;//pn记录操作数中"."的个数,以判断输入操作数是否合法if (len == 0)return 1;if (!(bt = (BiTree)malloc(sizeof(BiTNode)))) {printf("内存申请失败\n");return 0;}else{//初始化bt->lchild = bt->rchild = NULL;memset(bt->data, '\0', sizeof(bt->data));//memset是计算机中C/C++语言函数——memset(void*s,int ch,size_t n);//将s所指向的某一块内存中的后n个字节的内容全部设置为ch指定的ASCII值，//第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作，其返回值为s。

实验三——简易计算器（二叉树）05111341班李凌豪 11201312631．需求分析1.1.问题重述（1）问题描述由键盘输入一算术表达式，以中缀形式输入，试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该的后序遍历求出计算表达式的值。

（2）基本要求a．要求对输入的表达式能判断出是否合法。

不合法要有错误提示信息。

b．将中缀表达式转换成二叉表达式树。

c．后序遍历求出表达式的值（3）数据结构与算法分析一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。

a．建立表达式树。

二叉树的存储可以用顺序存储也可用链式存储。

当要创建二叉树时，先从表达式尾部向前搜索，找到第一个优先级最低的运算符，建立以这个运算符为数据元素的根结点。

注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树，右边部分对应的是二叉绔为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。

b．求表达式的值。

求值时同样可以采用递归的思想，对表达式进行后序遍历。

先递归调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值，最后读取根结点中的运算符，以刚才得到的左右子树的结果作为操作数加以计算，得到最终结果。

（4）测试1.2.问题分析本实验要求我们编写一个程序，利用二叉树，实现简易计算器的功能。

实现实数范围内的四则混合运算，而且要考虑括号对运算顺序的影响。

而且，题目要求用二叉树的知识来实现程序功能，因此需要将输入的中序表达式转换成逆波兰序列，然后就以此序列建立二叉链表，之后通过后序遍历实现运算的功能。

大概要求就是这样的。

2．概要设计2.1.抽象数据类型的定义考虑到，算符为字符型变量，算数为单精度浮点型变量。

考虑先讲输入的浮点数替换为char型的符号。

Struct jd为二叉链表的节点类型。

每一个节点都有字符域data，数字的话会有数值域shuzi为单精度浮点数。

struct jd{char data;float shuzi;struct jd *next1;struct jd *next2;};Struct haha 类型的数组ka[20]用来存放运算数，如果是运算数，就存进来，然后用字符域fuhao来代替数值域的单精度shuzi。

二叉树计算表达式计算表达式是计算机科学中常见的任务，而二叉树是一种常用的数据结构，用于表示表达式。

本文将介绍二叉树如何表示和计算表达式。

一、二叉树表示表达式二叉树是由节点和边组成的树状结构。

每个节点都包含一个值和两个指向左右子节点的指针。

二叉树可以用来表示数学表达式。

例如，下面是一个包含加、减、乘、除的表达式：```5 + 3 *6 / 2 - 4```将表达式转化为二叉树表示，根节点为`-`，其左子树是`+`，右子树是`4`。

`+`节点的左子树为`5`，右子树为`/`。

`/`节点的左子树为`*`，右子树为`2`。

`*`节点的左子树为`3`，右子树为`6`。

```-/ \+ 4/ \5 // \* 2/ \3 6```每个节点的值表示该节点的操作符或操作数。

叶子节点是操作数，内部节点是操作符。

二、计算二叉树表达式计算表达式需要递归地对二叉树进行遍历。

从根节点开始，如果是操作符节点，就对其左右子节点进行递归。

如果是操作数节点，就返回该节点的值。

等到递归完成后，就可以根据操作符节点的值和左右子节点的值对表达式进行计算了。

对于上面的表达式二叉树，计算的过程如下。

首先计算根节点的左右子节点，即`+`节点和`4`节点的值。

`+`节点还需要计算其左右子节点`5`和`/`节点的值。

`/`节点又需要计算其左右子节点`*`和`2`的值。

`*`节点需要计算其左右子节点`3`和`6`的值。

归纳起来，计算的顺序是从下到上，从左到右。

```-/ \+ 4/ \5 // \* 2/ \3 6```按照计算顺序求值：1. 计算`3 * 6`，得到18。

2. 计算`6 / 2`，得到3。

3. 计算`3 / 3`，得到1。

4. 计算`5 + 1`，得到6。

5. 计算`6 - 4`，得到2。

因此，表达式`5 + 3 * 6 / 2 - 4`的值是2。

三、扩展上面的例子说明了如何将表达式转为二叉树，并计算表达式的值。

但实际中会有更复杂的表达式，如函数调用、变量引用等。