二叉树的前中后序遍历以及表达式树
- 格式：pdf
- 大小：243.89 KB
- 文档页数：8
文档推荐
-
C语言实现二叉树的前序遍历(递归)页数:3
-
二叉树的建立及几种简单的遍历方法页数:6
-
二叉树的遍历(先序、中序、后序)页数:6
-
实验报告-二叉树的中序遍历页数:4
-
二叉树前序、中序、后序遍历相互求法页数:5
-
二叉树中序遍历的非递归算法实现页数:5
下载文档原格式
合集下载
数据结构应用-二叉树
数据结构应⽤-⼆叉树1.表达式树描述：表达式树的叶节点为操作数，其他节点为运算符。
对表达式式树采⽤不同的遍历策略可以分别得到前中后缀三种表达式。
先序遍历：前缀表达式（不常⽤）中序遍历：中缀表达式后序遍历：后缀表达式构造表达式树：把后缀表达式转化为表达式树（中缀转后缀已经在栈的应⽤中提到过），本质上还是借助了栈。
类似后缀表达式求值，从头开始逐字符读⼊表达式，遇到操作数则建⽴⼀个单节点树，将其指针压⼊栈中，当遇到运算符时，将栈顶的两个指针弹出并作为当前运算符的⼦节点构成⼀棵⼆叉树，将该树的指针压⼊栈中。
读到表达式末尾时，留在栈中的只剩下指向最终的表达式树的指针。
2.编码树编码：将信息转化为⼆进制码传输的过程就是编码。
解码：将接受到的⼆进制码恢复为原信息就是解码。
编码表：字符集中的任意字符都能在编码表中找到唯⼀对应的⼆进制串。
字符集到编码表是单射。
解码歧义：编码可以做到⼀⼀对应，解码却未必。
⽐如，规定S->11，M->111，那么现有⼆进制串“111111”，这个⼆进制串应该解码为SSS还是MM呢？这就产⽣了歧义。
产⽣歧义的根源在于，编码表中的某些编码，是其他编码的前缀。
在上例中，S对应的11就是M对应的111的前缀。
前缀⽆歧义编码（PFC）：既然知道了产⽣歧义的根源，就可以针对此根源来避免歧义。
避免歧义的本质要求就是，保证字符集中的每⼀个字符所对应的⼆进制串不是编码表中其他任何⼆进制串的前缀。
⼆叉编码树：⽤⼆叉树来描述编码⽅案。
我们知道从⼆叉树的根节点到任⼀其他节点的通路是唯⼀的，那么如果，我们使每⼀个节点之间的通路都表⽰⼆进制码0和1（左通路0，右通路1），这样从根节点出发到某节点的通路就变成了⼀个唯⼀的⼆进制串。
↑⼀棵普通的⼆叉编码树，来⾃《数据结构（C++语⾔版）》邓俊辉PFC编码树：由上图可以清晰地看出，S所对应的⼆进制码之所以会成为M（所对应的⼆进制码）的前缀，是因为S是M的⼦节点。
数据结构先序中序后序理解
数据结构先序中序后序理解数据结构是计算机科学中的重要概念之一，它是指一组数据的组织方式以及对这组数据进行操作的方法。
在学习数据结构的过程中，我们经常会遇到先序、中序和后序这三个概念。
它们是用来描述二叉树的遍历方式的，也可以用来表示表达式的计算顺序。
本文将从先序、中序和后序这三个角度来解释数据结构的含义和应用。
一、先序遍历先序遍历是指按照根节点、左子树、右子树的顺序访问二叉树的节点。
在先序遍历中，我们首先访问根节点，然后递归地遍历左子树和右子树。
先序遍历的应用非常广泛，比如在文件系统的目录结构中，我们可以使用先序遍历来列出所有的文件和文件夹。
二、中序遍历中序遍历是指按照左子树、根节点、右子树的顺序访问二叉树的节点。
在中序遍历中，我们首先递归地遍历左子树，然后访问根节点，最后再递归地遍历右子树。
中序遍历在二叉搜索树的操作中非常常见，它可以按照从小到大的顺序输出二叉搜索树中的元素。
三、后序遍历后序遍历是指按照左子树、右子树、根节点的顺序访问二叉树的节点。
在后序遍历中，我们首先递归地遍历左子树和右子树，最后访问根节点。
后序遍历常用于对二叉树进行一些计算操作，比如计算二叉树的深度、判断二叉树是否对称等。
除了用于二叉树的遍历，先序、中序和后序还可以用来表示表达式的计算顺序。
在数学表达式中，运算符和操作数之间的顺序非常重要，它决定了表达式的计算结果。
先序、中序和后序可以用来表示运算符的位置，从而决定表达式的计算顺序。
先序表示法中，运算符位于操作数之前，如"+ 3 4"表示加法运算。
中序表示法中，运算符位于操作数之间，如"3 + 4"表示加法运算。
后序表示法中，运算符位于操作数之后，如"3 4 +"表示加法运算。
不同的表示法对应着不同的计算顺序，但它们都能得到相同的结果。
先序、中序和后序在数据结构中有着广泛的应用。
它们不仅仅是一种遍历方式，还可以表示表达式的计算顺序。
二叉树常用的三种遍历方法
二叉树常用的三种遍历方法二叉树是一种常用的数据结构，它由一个根节点和两个子节点组成，其中左子节点小于根节点，右子节点大于根节点。
遍历二叉树是对所有节点进行访问的过程，常用的三种遍历方法是前序遍历、中序遍历和后序遍历。
下面将详细介绍这三种方法的实现步骤。
一、前序遍历前序遍历是指先访问根节点，然后按照左子树、右子树的顺序依次访问每个节点。
具体实现步骤如下：1. 如果当前节点为空，则返回。
2. 访问当前节点。
3. 递归进入左子树。
4. 递归进入右子树。
代码实现：void preorderTraversal(TreeNode* root) {if (root == NULL) return;cout << root->val << " ";preorderTraversal(root->left);preorderTraversal(root->right);}二、中序遍历中序遍历是指先访问左子树，然后访问根节点，最后访问右子树。
具体实现步骤如下：1. 如果当前节点为空，则返回。
2. 递归进入左子树。
3. 访问当前节点。
4. 递归进入右子树。
代码实现：void inorderTraversal(TreeNode* root) {if (root == NULL) return;inorderTraversal(root->left);cout << root->val << " ";inorderTraversal(root->right);}三、后序遍历后序遍历是指先访问左子树，然后访问右子树，最后访问根节点。
具体实现步骤如下：1. 如果当前节点为空，则返回。
2. 递归进入左子树。
3. 递归进入右子树。
4. 访问当前节点。
代码实现：void postorderTraversal(TreeNode* root) {if (root == NULL) return;postorderTraversal(root->left);postorderTraversal(root->right);cout << root->val << " ";}总结：以上就是二叉树常用的三种遍历方法的详细介绍和实现步骤。
前序后序中序详细讲解
前序后序中序详细讲解1.引言1.1 概述在数据结构与算法中，前序、中序和后序是遍历二叉树的三种基本方式之一。
它们是一种递归和迭代算法，用于按照特定的顺序访问二叉树的所有节点。
通过遍历二叉树，我们可以获取有关树的结构和节点之间关系的重要信息。
前序遍历是指先访问根节点，然后递归地访问左子树，最后递归地访问右子树。
中序遍历是指先递归地访问左子树，然后访问根节点，最后递归地访问右子树。
后序遍历是指先递归地访问左子树，然后递归地访问右子树，最后访问根节点。
它们的不同之处在于访问根节点的时机不同。
前序遍历可以帮助我们构建二叉树的镜像，查找特定节点，或者获取树的深度等信息。
中序遍历可以帮助我们按照节点的大小顺序输出树的节点，或者查找二叉搜索树中的某个节点。
后序遍历常用于删除二叉树或者释放二叉树的内存空间。
在实际应用中，前序、中序和后序遍历算法有着广泛的应用。
它们可以用于解决树相关的问题，例如在Web开发中，树结构的遍历算法可以用于生成网页导航栏或者搜索树结构中的某个节点。
在图像处理中，前序遍历可以用于图像压缩或者图像识别。
另外，前序和后序遍历算法还可以用于表达式求值和编译原理中的语法分析等领域。
综上所述，前序、中序和后序遍历算法是遍历二叉树的重要方式，它们在解决各种与树有关的问题中扮演着关键的角色。
通过深入理解和应用这些遍历算法，我们可以更好地理解和利用二叉树的结构特性，并且能够解决更加复杂的问题。
1.2文章结构文章结构是指文章中各个部分的布局和组织方式。
一个良好的文章结构可以使读者更好地理解和理解文章的内容。
本文将详细讲解前序、中序和后序三个部分的内容和应用。
首先，本文将在引言部分概述整篇文章的内容，并介绍文章的结构和目的。
接下来，正文部分将分为三个小节，分别对前序、中序和后序进行详细讲解。
在前序讲解部分，我们将定义和解释前序的意义，并介绍前序在实际应用中的场景。
通过详细的解释和实例，读者将能更好地理解前序的概念和用途。
树和二叉树的实验报告
《数据结构》实验报告题目: 树和二叉树一、用二叉树来表示代数表达式（一）需求分析输入一个正确的代数表达式, 包括数字和用字母表示的数, 运算符号+ - * / ^ =及括号。
系统根据输入的表达式建立二叉树, 按照先括号里面的后括号外面的, 先乘后除的原则, 每个节点里放一个数字或一个字母或一个操作符, 括号不放在节点里。
分别先序遍历, 中序遍历, 后序遍历此二叉树, 并输出表达式的前缀式, 中缀式和后缀式。
（二）系统设计1.本程序中用到的所有抽象数据类型的定义；typedef struct BiNode //二叉树的存储类型{char s[20];struct BiNode *lchild,*rchild;}BiTNode,*BiTree;2.主程序的流程以及各程序模块之间的层次调用关系, 函数的调用关系图:3. 列出各个功能模块的主要功能及输入输出参数void push(char cc)初始条件: 输入表达式中的某个符号操作结果: 将输入的字符存入buf数组中去BiTree Create_RTree()初始条件: 给出二叉树的定义表达式操作结果：构造二叉树的右子树, 即存储表达式等号右侧的字符组BiTree Create_RootTree()初始条件: 给出二叉树的定义表达式操作结果：构造存储输入表达式的二叉树, 其中左子树存储‘X’, 根节点存储‘：=’void PreOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：先序遍历T, 对每个节点调用函数Visit一次且仅一次void InOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：中序遍历T, 对每个节点调用函数Visit一次且仅一次void PostOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：后序遍历T, 对每个节点调用函数Visit一次且仅一次int main()主函数, 调用各方法, 操作成功后返回0（三）调试分析调试过程中还是出现了一些拼写错误, 经检查后都能及时修正。
计算机中二叉树遍历的讲解
计算机中二叉树遍历的讲解一、二叉树遍历的基础概念二叉树遍历就是按照某种特定的顺序来访问二叉树中的每个节点。
这就好比你要去一个有好多房间的大房子里找人，你得有个顺序去一间间找，不然就乱套啦。
二叉树有三种主要的遍历方式哦，分别是前序遍历、中序遍历和后序遍历。
二、前序遍历前序遍历的顺序是根节点、左子树、右子树。
想象一下，你站在二叉树这个大树前，你先看树根，这就是根节点啦，然后再去看树根左边的那些小树枝小树叶（左子树），最后再看树根右边的那些（右子树）。
就像是你先和这个大家庭的家长打招呼，然后再去和家长左边的家人聊天，最后再和右边的家人聊天一样。
比如有这么一个简单的二叉树，根节点是A，A的左子节点是B，右子节点是C，B 下面还有左子节点D和右子节点E，C下面有左子节点F。
那前序遍历的结果就是A - B - D - E - C - F。
三、中序遍历中序遍历的顺序是左子树、根节点、右子树。
这就像是你先和大家庭里左边的家人聊聊天，然后再和家长打招呼，最后再和右边的家人聊。
还是刚刚那个二叉树，中序遍历的结果就是 D - B - E - A - F - C。
四、后序遍历后序遍历的顺序是左子树、右子树、根节点。
这就好比你先和左边家人玩一玩，再和右边家人玩一玩，最后才和家长说拜拜。
按照那个二叉树来说，后序遍历的结果就是 D - E - B - F - C - A。
五、二叉树遍历的实际应用二叉树遍历在计算机里有很多用处呢。
比如说在表达式求值的时候，我们可以把表达式转化成二叉树的形式，然后通过特定的遍历方式来计算结果。
又比如说在文件系统里，文件夹和文件的结构也可以看成是一种二叉树，遍历它就可以方便地查找文件啦。
这就像在图书馆里找书一样，如果知道了一种查找的顺序（类似二叉树遍历顺序），就能很快找到你想要的那本书啦。
六、二叉树遍历的代码实现（以简单的编程语言为例）在编程里实现二叉树遍历也不是特别难。
比如说用Python语言，我们先定义一个二叉树的节点类，像这样：pythonclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right然后实现前序遍历的函数：pythondef preorderTraversal(root):result = []def helper(node):if node:result.append(node.val) helper(node.left)helper(node.right)helper(root)return result中序遍历的函数：pythondef inorderTraversal(root): result = []def helper(node):if node:helper(node.left)result.append(node.val)helper(node.right)helper(root)return result后序遍历的函数：pythondef postorderTraversal(root):result = []def helper(node):if node:helper(node.left)helper(node.right)result.append(node.val)helper(root)return result这样我们就可以轻松地对二叉树进行遍历啦。
算术表达式(例题)-二叉树
最早提出遍历问题的是对存储在计算机中的表达式求值。
例如：(a+b ×(c-d))-e/f 。
表达式用树形来表示，如图8-11-1所示。
运算符在树中放在非终端结点的位置上，操作数放在叶子结点处。
当我们对此二叉树进行先序、中序和后序遍历后，便可得到表达式的前缀、中缀和后缀书写形式：前缀：-+a*b-cd/ef中缀：a+b*c-d-e/f 后缀：abcd-*+ef/-其中，中缀形式是算术表达式的通常形式，只是没有括号。
在计算机内，使用后缀表达式易于求值。
例1 输入一个算术表达式，判断该表达式是否合法，若不合法，给出错误信息；若合法，则输出合法表达式的表达式树。
【算法分析】表达式不合法有三种情况：①左右括号不匹配；②变量名不合法；③运算符两旁无参与运算的变量或数。
分析表达式树可以看到：表达式的根结点及其子树的根结点为运算符，其在树中的顺序是按运算的先后顺序从后到前，表达树的叶子为参与运算的变量或数。
表达式树如图8-11-2处理时，首先找到运算级别最低的运算符“+”作为根结点，继而确定该根结点的左、右子树结点在表达式串中的范围为a 和(b-c)/d ，再在对应的范围内寻找运算级别最低的运算符作为子树的根结点，直到范围内无运算符，则剩余的变量或数为表达式树的叶子。
【算法步骤】① 设数组ex 存放表达式串的各字符，lt 、rt 作为结点的左右指针，变量left 、right 用于存放每次取字符范围的左、右界。
② 设置左界初值为1；右界初值为串长度。
③ 判断左右括号是否匹配，不匹配则认为输入有错误。
④ 在表达式的左右界范围内寻找运算级别最低的运算符，同时判断运算符两旁有否参与运算的变量或数。
若无，则输入表达式不合法；若有，作为当前子树的根结点，设置左子树指针及其左右界值，设置右子树指针及其左右界值。
⑤ 若表达式在左右界范围内无运算符，则为叶子结点，判断变量名或数是否合法。
⑥ 转④，直到表达式字符取完为止。
NOIP初赛复习4二叉树的遍历和性质
二叉树的遍历（图1）（图2）二叉树的遍历运算（递归定义）(1)先序遍历：根，左子树，右子树根在先例如图1：271653894；图2：ABCKDEHFJG(2)中序遍历：左子树，根，右子树根在中例如图1：175632849；图2：BKCAHEDHFG(3)后序遍历：左子树，右子树，根根在后例如图1：153674982；图2：KCBHEJGFDA题型一：已知其中一些遍历结果，求其他遍历结果题型二：统计ｎ个不同的点可以构造多少棵不同的二叉树?Catalan数=C(n,2*n)/(n+1)题型三：中缀表达式向前缀和后缀表达式的转化每日练习注：题1已知先序和中序，二叉树是唯一的。
题2已知后序和中序，二叉树是唯一的。
题3已知先序和后序，二叉树不是唯一的。
1、已知先序：1243576，中序：2417536，请画出整棵二叉树。
2、已知后序：4526731，中序：4257631，请画出整棵二叉树。
3、已知先序：123456，后序：325641，请画所有二叉树的情况。
4、如果只知道先序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？5、如果只知道中序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？6、如果只知道后序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？往年真题1.一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）。
A．0B．2C．4D．62.表达式a*(b+c)-d的后缀表达式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd3.二叉树T，已知其先序遍历是1243576（数字为节点编号，以下同），后序遍历是4275631，则该二叉树的中根遍历是（）A．4217536B．2417536C．4217563D．24157364.二叉树T，已知其先根遍历是1243576（数字为结点编号，以下同），中根遍历是2415736，则该二叉树的后根遍历是（）A.4257631B.4275631C.7425631D.42765315.已知7个节点的二叉树的先根遍历是1245637(数字为结点的编号，以下同),后根遍历是4652731,则该二叉树的可能的中根遍历是()A.4265173B.4256137C.4231567D.42561736.已知7个节点的二叉树的先根遍历是1245637（数字为节点的编号，以下同），中根遍历是4265173，则该二叉树的后根遍历是（）A．4652731B．4652137C．4231547D．46531 727.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是325641，则该二叉树的可能的中根遍历是（）A.321465B.321546C.231546D.231465二叉树的性质性质1：二叉树第i层上的结点数目最多为。
二叉树实验知识点总结
二叉树实验知识点总结
一、二叉树的基本概念
二叉树是一种特殊的树形结构，其每个节点最多只有两个子节点。
二叉树分为满二叉树、完全二叉树和普通二叉树等类型。
二、遍历方式
1.前序遍历：先访问当前节点，再遍历左子树和右子树；
2.中序遍历：先遍历左子树，再访问当前节点，最后遍历右子树；
3.后序遍历：先遍历左子树和右子树，最后访问当前节点；
4.层次遍历：按照从上到下、从左到右的顺序依次访问每个节点。
三、常见操作
1.插入节点：在二叉搜索树中插入一个新的节点；
2.删除节点：在二叉搜索树中删除一个指定的节点；
3.查找节点：在二叉搜索树中查找一个指定的节点；
4.求深度：计算二叉搜索树的深度。
四、平衡二叉树
平衡二叉树是一种特殊的二叉搜索树，其左右子树高度差不能超过1。
常见的平衡二叉搜索包括红黑树、AVL 树等。
五、应用场景
1.数据库索引；
2.哈夫曼编码；
3.表达式求值；
4.图形处理等。
六、注意事项
1.二叉树的插入、删除和查找操作需要保证二叉树的结构不被破坏；
2.平衡二叉树的实现需要注意平衡因子的计算和旋转操作的实现；
3.在使用二叉树进行算法设计时，需要考虑遍历方式和时间复杂度等问题。
七、总结
二叉树是一种重要的数据结构，在算法设计中有广泛的应用。
掌握二叉树的基本概念、遍历方式、常见操作和应用场景，可以帮助我们更好地理解和使用这种数据结构。
同时，我们需要注意在实际应用中遵循相关规范，保证程序的正确性和效率。
二叉树遍历稿ppt课件
特别讨论
若已知先序（或后序）遍历结果和中序遍历结 果，能否“恢复”出二叉树？
例：已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析：
①由后序遍历特征，根结点必在后序序列尾部（即A）；
②由中序遍历特征，根结点必在其中间，而且其左部必全 部是左子树的子孙（即BDCE），其右部必全部是右子树的 子孙（即FHG）；
知识拓展—利用遍历建立二叉树
如何把二叉树存入电脑内？ 怎样利用遍历建立一棵二叉树？
例：将下面的二叉树以二叉链表形式存入计算机内。
A
B
C
D
E
F
考虑1：输入结点时怎样表示“无孩子”？ 考虑2：以何种遍历方式来输入和建树？
字符串输完后应当再 以加先一序特遍殊历的最结为束合符适号， 用空格字符表示 让(如每$个)，结因点为都能及时无 ‘无孩子’或指针 被法连惟接一到表位示。结束。 为空
三种遍历算法分析
1. 从前面的三种遍历算法可以知道：如果将print语句抹去， 从递归的角度看，这三种算法是完全相同的，或者说这三种 遍历算法的访问路径是相同的，只是访问结点的时机不同。
A
B
C
D
E
F
G
从虚线的出发点到终点的路径 上，每个结点经过3次。 第1次经过时访问，是先序遍历 第2次经过时访问，是中序遍历 第3次经过时访问，是后序遍历
难
的遍历方法。
二叉树遍历
➢理解二叉树
的应用。
点
的遍历算法
烧伤病人的治疗通常是取烧伤病人的 健康皮 肤进行 自体移 植，但 对于大 面积烧 伤病人 来讲， 健康皮 肤很有 限，请 同学们 想一想 如何来 治疗该 病人
若已知先序（或后序）遍历结果和中序遍历结 果，能否“恢复”出二叉树？
例：已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析：
①由后序遍历特征，根结点必在后序序列尾部（即A）；
②由中序遍历特征，根结点必在其中间，而且其左部必全 部是左子树的子孙（即BDCE），其右部必全部是右子树的 子孙（即FHG）；
知识拓展—利用遍历建立二叉树
如何把二叉树存入电脑内？ 怎样利用遍历建立一棵二叉树？
例：将下面的二叉树以二叉链表形式存入计算机内。
A
B
C
D
E
F
考虑1：输入结点时怎样表示“无孩子”？ 考虑2：以何种遍历方式来输入和建树？
字符串输完后应当再 以加先一序特遍殊历的最结为束合符适号， 用空格字符表示 让(如每$个)，结因点为都能及时无 ‘无孩子’或指针 被法连惟接一到表位示。结束。 为空
三种遍历算法分析
1. 从前面的三种遍历算法可以知道：如果将print语句抹去， 从递归的角度看，这三种算法是完全相同的，或者说这三种 遍历算法的访问路径是相同的，只是访问结点的时机不同。
A
B
C
D
E
F
G
从虚线的出发点到终点的路径 上，每个结点经过3次。 第1次经过时访问，是先序遍历 第2次经过时访问，是中序遍历 第3次经过时访问，是后序遍历
难
的遍历方法。
二叉树遍历
➢理解二叉树
的应用。
点
的遍历算法
烧伤病人的治疗通常是取烧伤病人的 健康皮 肤进行 自体移 植，但 对于大 面积烧 伤病人 来讲， 健康皮 肤很有 限，请 同学们 想一想 如何来 治疗该 病人
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
if (s[i] == ' ' || s[i] == '=') {
i++; continue;
}
else if (s[i] == '(') {
op.push (s[i++]);
}
else if (s[i] == ')') {
while (op.top () != '(') {
ret += op.top (); ret += ' ';
while (i >= 0) {
if (s[i] == ' ' || s[i] == '=') {
i--; continue;
}
else if (s[i] == ')') {
op.push (s[i--]);
}
else if (s[i] == '(') {
while (op.top () != '#' && op.top () != ')') {
表达式求值，逆波兰式(后缀表达式)算法 输入(可以有空格，支持小数，实现'+-/*%')： ((1+2)*5+1)/4= 注意：取模一定是要整型，实现版本数字全是 double，强制类型转换可能倒置错误 转换为后缀表达式： 得到：1 2 + 5 * 1 + 4 / = 计算后缀表达式：得到：4.00 */ bool is_digit(char ch) { return '0' <= ch && ch <= '9'; }
ret += op.top (); ret += ' ';
op.pop ();
}
ret += '=';
return ret;
}
double solve(string str) {
//计算后缀表达式
string s = get_postfix (str);
while (!num.empty ()) num.pop ();
default: return 0;
}
}
string get_prefix(string s) {
//中缀表达式转变前缀表达式
while (!op.empty ()) op.pop ();
op.push ('#');
string ret = "";
int len = s.length (), i = len - 1;
}
int i;
double get_num(string s) { double x = 0; while (is_digit (s[i])) { x = x * 10 + s[i] - '0'; i++; } if (s[i] == '.') { double k = 10.0, y = 0; i++; while (is_digit (s[i])) { y += ((s[i] - '0') / k); i++; k *= 10; } x += y; } return x;
ret += op.top (); ret += ' ';
op.pop ();
}
op.push (s[i++]);
}
else {
while (is_digit (s[i]) || s[i] == '.') {
ret += s[i++];
}
ret += ' ';
}
}
while (op.top () != '#') {
* Created Time :2015/10/29 星期四 16:12:53
* File Name :BT.cpp
************************************************/
#include <cstdio> #include <algorithm> #include <iostream> #include <sstream> #include <cstring> #include <cmath> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <list> #include <map> #include <set> #include <bitset> #include <cstdlib> #include <ctime> #include <iomanip> using namespace std;
举个栗子：表达式：1 + 2 * (3 - 4) - 5 / 6，那么它的前缀表达式就是：- + 1 * 2 - 3 4 / 5 6， 那么可以建立二叉树，如图：
最后，附上代码
/************************************************
* Author
:你们亲爱的室友
}
return 0;
}
string get_postfix(string s) {
//中缀表达式转变后缀表达式
while (!op.empty ()) op.pop ();
op.push ('#');
string ret = "";
int len = s.length (), i = 0;
while (i < len) {
ret += op.top (); ret += ' ';
op.pop ();
}
op.push (s[i--]);
}
else {
while (is_digit (s[i]) || s[i] == '.') {
ret += s[i--];
}
ret += ' ';
}
}
while (op.top () != '#') {
二叉树的前中后序遍历以及表达式树
昨天数据结构课布置了上机实验，要求递归方式建立表达式二叉树，输出树的前中后序遍历的结 果，并计算表达式的值。网上其他人的做法无非就是先求出后缀表达式，然后后序遍历的方式+栈建 立二叉树，可是本题的要求是递归方式，所以我的方法就是求出前缀表达式，用前序遍历的方法可以 递归建立二叉树，最后用后序遍历的方式求解表达式树。
op.pop ();
}
op.pop (); i++;
}
else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '%')
{
while (prior (op.top ()) >= prior (s[i])) {
}
if (s[i] == '.') {
double k = 10.0, y = 0;
i++;
while (is_digit (s[i])) {
y += ((s[i] - '0') / k);
i++; k *= 10;
} x += y; } num.push (x); } } return num.top (); } }E; typedef struct BT { char op; double data; BT *lch, *rch; }node, *btree;
error = false;
int len = s.length (), i = 0;
while (i < len) {
if (s[i] == ' ' || s[i] == '=') {i++; continue;}
else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '%')
ret += op.top (); ret += ' ';
op.pop ();
}
reverse (ret.begin (), ret.end ());
reble a, double b, char ch) {
if (ch == '+') return a + b;
}
//中序遍历
void post_order(btree T) { //后序遍历 if (T != NULL) { post_order (T -> lch); post_order (T -> rch); print (T); }