表达式与二叉树的相互转换

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

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

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

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

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

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

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

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

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

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

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

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

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

基于二叉树的表达式求值算法实验报告一、实验目的1. 学习基于二叉树的表达式求值算法。

2. 掌握二叉树的遍历方法和递归算法。

3. 设计并实现基于二叉树的表达式求值程序。

二、实验环境操作系统：Windows 10开发环境：Visual Studio Code 1.57.1编程语言：C++三、算法描述1. 表达式转二叉树将中缀表达式转换为二叉树的过程可以通过递归算法实现。

具体步骤如下：（1）如果表达式只有一个数字，那么将其作为叶子节点返回。

（2）如果表达式包含多个操作符，则以操作符优先级最低的操作符为根节点，将表达式分成两部分，分别递归处理左子树和右子树。

（3）如果表达式中有括号，则将括号中的表达式作为一棵子树递归处理。

2. 表达式求值二叉树求值的过程可以通过递归算法实现。

对于一个二叉树节点，分别计算其左子树和右子树的值，并根据节点的操作符计算节点的值。

具体步骤如下：（1）如果节点是叶子节点，则其值为对应数字。

（2）如果节点是加法节点，则将左右子树的值相加。

（3）如果节点是减法节点，则将左子树的值减去右子树的值。

（4）如果节点是乘法节点，则将左右子树的值相乘。

（5）如果节点是除法节点，则将左子树的值除以右子树的值。

四、实验步骤1. 定义二叉树节点结构体c++struct node {char oper; 节点的操作符double val; 节点的值node* left; 左子树节点node* right; 右子树节点};2. 实现表达式转二叉树函数c++node* expressionToTree(string exp) { int len = exp.length();node* root = NULL;如果表达式是一个数字if (len == 1) {root = new node;root->oper = '#';root->val = exp[0] - '0';root->left = NULL;root->right = NULL;return root;}如果表达式包含多个操作符int pos = 0, priority = 0;for (int i = 0; i < len; i++) {if (exp[i] == '(') {priority += 10;continue;}if (exp[i] == ')') {priority -= 10;continue;}if (exp[i] == '+' exp[i] == '-') {if (priority <= 1) {root = new node;root->oper = exp[i];root->left = expressionT oTree(exp.substr(pos, i - pos));root->right = expressionToTree(exp.substr(i + 1));return root;}}if (exp[i] == '*' exp[i] == '/') {if (priority <= 2) {root = new node;root->oper = exp[i];root->left = expressionT oTree(exp.substr(pos, i - pos));root->right = expressionToTree(exp.substr(i + 1));return root;}}}return root;}3. 实现表达式求值函数c++double evaluate(node* root) {if (root == NULL) return 0.0;if (root->left == NULL && root->right == NULL) return root->val;double left_val = evaluate(root->left), right_val =evaluate(root->right);switch (root->oper) {case '+': return left_val + right_val;case '-': return left_val - right_val;case '*': return left_val * right_val;case '/': return left_val / right_val;default: return 0.0;}}4. 测试程序c++int main() {string exp = "((5-2)*(3+4))/7";node* root = expressionToTree(exp);cout << exp << " = " << evaluate(root) << endl; 输出结果为3 return 0;}五、实验结果分析本实验设计并实现了基于二叉树的表达式求值程序。

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

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

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

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

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

例如，下面是一个包含加、减、乘、除的表达式：```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。

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

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

实验六：二叉树及其应用一、实验目的树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。

二、问题描述首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。

其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。

如算术表达式：a+b*(c-d)-e/f三、实验要求如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。

求二叉树的深度。

十进制的四则运算的计算器可以接收用户来自键盘的输入。

由输入的表达式字符串动态生成算术表达式所对应的二叉树。

自动完成求值运算和输出结果。

四、实验环境PC微机DOS操作系统或Windows 操作系统Turbo C 程序集成环境或Visual C++ 程序集成环境五、实验步骤1、根据二叉树的各种存储结构建立二叉树；2、设计求叶子结点个数算法和树的深度算法；3、根据表达式建立相应的二叉树，生成表达式树的模块；4、根据表达式树，求出表达式值，生成求值模块；5、程序运行效果，测试数据分析算法。

六、测试数据1、输入数据：2.2*（3.1+1.20）-7.5/3正确结果：6.962、输入数据：(1+2)*3+(5+6*7);正确输出：56七、表达式求值由于表达式求值算法较为复杂，所以单独列出来加以分析：1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。

例如有如下的中缀表达式：a+b-c转换成后缀表达式为：ab+c-然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。

如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。

二叉链表求算数表达式二叉链表是一种常见的数据结构，用于表示二叉树。

在算术表达式求值中，也可以利用二叉链表来表示算术表达式的结构，方便进行计算和操作。

二叉链表表示算术表达式的方式是将表达式转化为二叉树的形式。

其中，二叉树的叶子节点存储操作数，内部节点存储运算符。

通过遍历二叉树，可以按照特定的规则解释算术表达式并求值。

下面是一个示例，展示如何将算术表达式转化为二叉链表：算术表达式: 2 + 3 * 41. 将运算符和操作数转化为节点，并建立二叉链表：```+/ \2 */ \3 4```2. 通过遍历二叉链表，按照运算符的优先级求值。

首先，遍历左子树进行运算，得到：2然后，遍历右子树进行运算，得到：3 * 4 = 12最后，根据根节点的运算符进行运算，得到：2 + 12 = 14算术表达式的求值过程可以通过二叉链表的先序遍历来实现，具体步骤如下：1. 如果节点是叶子节点（操作数），返回操作数的值。

2. 如果节点是内部节点（运算符），获取左子树和右子树的值。

3. 根据运算符进行相应的运算，并返回结果。

示例的先序遍历过程如下：先序遍历：+ 2 * 3 41. 访问根节点：+2. 访问左子树：23. 访问右子树的左子树：*4. 访问右子树的左子树：35. 访问右子树的右子树：4经过先序遍历的过程，可以逐步解释算术表达式并求值。

二叉链表表示算术表达式的方法在编译原理中得到了广泛的应用。

通过将表达式转化为二叉树的形式，可以方便地进行运算和求值。

在实际应用中，可以使用栈来实现二叉链表表示的算术表达式的求值，具体步骤如下：1. 遍历表达式的每个字符。

2. 如果字符是操作数，将其转化为节点并入栈。

3. 如果字符是运算符，取栈顶的两个节点作为右子树和左子树，将运算符作为根节点，再入栈。

4. 最终栈中只会剩下一个节点，即根节点。

通过这种方式，可以将表达式转化为二叉链表，并计算出最终的结果。

总结起来，二叉链表可以用来表示算术表达式的结构，并进行求值。

c语言基于二叉树的表达式求值算法C语言中，基于二叉树的表达式求值算法主要包括两部分：中缀表达式转换为后缀表达式和后缀表达式求值。

1.中缀表达式转换为后缀表达式中缀表达式是我们常见的数学表达方式，例如3 + 4 * 2 - 5。

为了方便计算机求值，我们需要将中缀表达式转换为后缀表达式，也叫做逆波兰表达式。

转换的过程使用栈数据结构来实现。

具体算法如下：1.定义一个栈和一个结果字符串，栈用于存储操作符，结果字符串用于保存后缀表达式。

2.从左到右遍历中缀表达式的每一个字符。

3.如果当前字符是数字，直接将其加入结果字符串。

4.如果当前字符是左括号"("，将其入栈。

5.如果当前字符是右括号")"，则依次将栈顶的操作符弹出并加入结果字符串，直到遇到左括号为止，同时将左括号从栈中弹出。

6.如果当前字符是操作符，需要将栈中优先级比当前操作符高或者相等的操作符弹出并加入结果字符串，然后将当前操作符入栈。

7.遍历完所有字符后，将栈中剩余的操作符依次弹出并加入结果字符串。

8.最终结果字符串就是后缀表达式。

例如，对于中缀表达式3 + 4 * 2 - 5，转换为后缀表达式为3 4 2 * + 5 -2.后缀表达式求值后缀表达式求值算法使用栈数据结构来实现。

具体算法如下：1.定义一个栈，用于存储操作数。

2.从左到右遍历后缀表达式的每一个字符。

3.如果当前字符是数字，则将其转换为对应的整数并入栈。

4.如果当前字符是操作符，则从栈中弹出两个操作数，先弹出的作为右操作数，后弹出的作为左操作数，根据操作符进行运算，得到结果后入栈。

5.遍历完所有字符后，栈顶的数字即为最终的结果。

例如，对于后缀表达式3 4 2 * + 5 -，求值的过程如下：1.入栈3。

2.入栈4。

3.入栈2。

4.弹出2和4，计算4 * 2 = 8，将8入栈。

5.弹出8和3，计算3 + 8 = 11，将11入栈。

6.入栈5。

7.弹出5和11，计算11 - 5 = 6，得到最终结果。

一、概述二、算术表达式的二叉树表示1. 什么是二叉树2. 算术表达式的二叉树表示方法三、算术表达式二叉树的构建1. 中缀表达式转换为后缀表达式2. 后缀表达式构建二叉树四、算术表达式二叉树的求值五、应用举例六、总结一、概述在数学和计算机科学中，处理算术表达式是一个常见的问题。

在计算机中，算术表达式通常以中缀、前缀或后缀的形式出现，其中中缀表达式最为常见。

而采用二叉树来表示和求解算术表达式，是一种常见且高效的方法。

二、算术表达式的二叉树表示1. 什么是二叉树二叉树是一种树形数据结构，它的每个节点最多只能有两个子节点，分别是左子节点和右子节点。

二叉树可以为空，也可以是非空的。

2. 算术表达式的二叉树表示方法在二叉树中，每个节点要么是操作符，要么是操作数。

操作符节点的左子节点和右子节点分别表示运算符的两个操作数，而操作数节点则不包含任何子节点。

通过这种方式，可以将算术表达式表示为一个二叉树结构。

三、算术表达式二叉树的构建1. 中缀表达式转换为后缀表达式为了构建算术表达式的二叉树，首先需要将中缀表达式转换为后缀表达式。

中缀表达式是人们常见的形式，例如"2 + 3 * 5"，而后缀表达式则更适合计算机处理，例如"2 3 5 * +"。

将中缀转后缀的算法即为中缀表达式的后缀转换法则。

2. 后缀表达式构建二叉树构建二叉树的过程通常采用栈来辅助完成。

从左到右扫描后缀表达式，对于每个元素，如果是操作数，则入栈；如果是操作符，则弹出栈顶两个元素作为其左右子节点，然后将操作符节点入栈。

最终栈中只剩一个节点，即为构建的二叉树的根节点。

四、算术表达式二叉树的求值算术表达式二叉树的求值是递归进行的。

对于二叉树的每个节点，如果是操作符节点，则递归求解其左右子节点的值，并进行相应的操作；如果是操作数节点，则直接返回其值。

最终得到根节点的值，即为整个算术表达式的值。

五、应用举例以中缀表达式"2 + 3 * 5"为例，首先将其转换为后缀表达式"2 3 5 * +"，然后根据后缀表达式构建二叉树，最终求得二叉树的根节点即为算术表达式的值。

中序表达式是一种二叉树表达式，用来表示一棵二叉树的节点值的中序遍历顺序。

中序表达式通常是一串用空格分隔的节点名，例如“左左右右右”。

而后序表达式是另一种二叉树表达式，它表示二叉树的节点值的后序遍历顺序。

后序表达式通常是一串用空格分隔的节点名，但是与中序表达式不同的是，后序表达式中最后一个出现的节点是根节点，例如“左右右”。

要将一个中序表达式转换为后序表达式，可以按照以下步骤进行：
1. 将中序表达式中的第一个节点记为根节点。

2. 从中序表达式中的第二个节点开始，依次根据中序表达式中该节点后面的所有节点的先后顺序，递归地将每个节点作为子表达式的根节点，并将该节点及其后代节点从中序表达式中删除。

3. 将剩余的节点组成新的后序表达式。

例如，对于中序表达式“左右左”，它对应的二叉树为：
左
/ \
左右
/ \ \
左右左
按照上述步骤，可以将其转换为后序表达式“左右右”。

需要注意的是，在中序表达式和后序表达式转换的过程中，可能会出现空节点或多个节点的情况，需要进行相应的处理。

构造表达式二叉树构造表达式二叉树，需要先确定二叉树的构造规则，然后将表达式按照规则转换为对应的二叉树结构。

下面是一个简单的例子，演示如何构造一个表达式的二叉树：假设我们有一个简单的四则运算表达式：3 + 4 2 - 1 / 2。

根据二叉树的构造规则，我们可以将这个表达式转换为如下的二叉树结构：```+/ \3/ \4 2/ \- 1/ \/ 2```这个二叉树表示的表达式是：3 + (4 2) - (1 / 2)。

其中，根节点表示运算符"+"，左子树表示3，右子树是一个二叉树，根节点表示运算符""，左子树表示4，右子树表示2。

在右子树的下面是一个三叉树，根节点表示运算符"-"，左子树是空，中子树表示1，右子树是一个二叉树，根节点表示运算符"/"，左子树是空，右子树表示2。

在构造这个二叉树时，需要注意以下几点：1. 先处理运算符和操作数。

在表达式中，运算符和操作数之间有一个空格。

在构造二叉树时，我们需要保留这个空格，将其视为两个节点的分隔符。

2. 根据运算符的优先级和结合性，确定子树的构造顺序。

在本例中，""的优先级高于"+"，所以先构造""的子树。

同时，""是左结合的，所以先构造左子树。

3. 对于复杂的表达式，需要使用括号来明确运算顺序。

在本例中，"1 / 2"被括起来，表示先进行除法运算。

在构造二叉树时，需要将括号视为一个节点，并将其作为父节点包含其它的子节点。

森林与二叉树之间相互转换的方法。

树中所有相邻兄弟之间加一条连线。

1.树中所有相邻兄弟之间加一条连线。

2.对树中的每个结点，只留存其与第一个孩子结点之间的连线，删掉其与其它孩子结点之间的连线。

3.以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。

森林切换为二叉树的方法如下：
1.将森林中的每棵树转换成相应的二叉树。

2.第一棵二叉树不颤抖，从第二棵二叉树已经开始，依次把后一棵二叉树的木结点做为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所获得的二叉树就是由森林切换获得的二叉树。

树和森林都可以转换为二叉树，二者的不同是:树转换成的二叉树,其根结点必然无右孩子，而森林转换后的二叉树，其根结点有右孩子。

将一棵二叉树还原为树或森林，具体方法如下：
1.若某结点就是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、……都与该结点的双亲结点用线连出来。

2.删掉原二叉树中所有双亲结点与右孩子结点的连线。

3.整理由1、2两步所获得的一棵或森林，并使之结构层次分明。