二叉树：后缀式转换成表达式二叉树（从后缀式的计算入手和遍历的递归实现入手）

您所在的位置：网站首页 › 表达式怎么转表达式树 › 二叉树：后缀式转换成表达式二叉树（从后缀式的计算入手和遍历的递归实现入手）

二叉树：后缀式转换成表达式二叉树（从后缀式的计算入手和遍历的递归实现入手）

2024-06-10 15:38| 来源: 网络整理| 查看: 265

文章目录问题描述 :输入说明 :输出说明 :输入范例 :输出范例 :思路分析实现伪码事故现场第一次提交最后一次提交分析与总结如果不妥，请留言，你的留言是对我最大的鼓励。当然加扣扣问也行，一定知无不言，言无不尽，一块商量进步学习

问题描述 :

内容：（1）请参照链表的ADT模板，设计二叉树并逐步完善的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的链表ADT原型文件，自行设计二叉树的ADT。）

注意：二叉树ADT的基本操作的算法设计很多要用到递归的程序设计方法。

（2）ADT的简单应用：使用该ADT设计并实现若干应用二叉树的算法设计。

应用：要求设计一个算法，将后缀表达式转换成表达式二叉树。二叉树的存储结构的建立参见二叉树应用1。

注意：假定输入的后缀表达式为合法的表达式。仅考虑有小括弧的场合。运算符包括+、-、*、/，运算数为整数（不局限于个位数）。

提示：使用1个栈：保存指向二叉树树根的指针栈Stack。算法函数返回指向表达式二叉树root的指针。

参考函数原型：

//后缀表达式生成表达式二叉树 template BinaryTreeNode * Suffix_BinaryTree(SqStack &Stack, string &suffix);

辅助函数：

（1）判断是否为运算符（用户函数）

//判断是否为运算符 bool isoperator( char op ){ switch(op){ case '+': case '-': case '*': case '/': case '(': case ')': return true; default: return false; } }

（2）求运算符的优先级（用户函数）

//求运算符的优先级 int getOperPri(char op) { switch(op) { case '(': return 1; break; case '+': case '-': return 2; break; case '*': case '/': return 3; break; default: return 0; } } 输入说明 :

第一行：后缀表达式字符串

输出说明 :

第一行：表达式二叉树前序遍历结果（前缀式）

第二行：表达式二叉树中序遍历结果（中缀式，带加括号处理）

第三行：表达式二叉树后序遍历结果（后缀式）

输入范例 : 12 14 + 3 * 400 30 10 5 * + / - 62 + 输出范例 : + - * + 12 14 3 / 400 + 30 * 10 5 62 (12+14)*3-400/(30+10*5)+62 12 14 + 3 * 400 30 10 5 * + / - 62 + 思路分析

先从后缀式的运算说起，模仿运算，生成的二叉树，然后根据二叉树生成中缀式在这里插入图片描述

附加后缀式运算的传送门的传送门

修改如下在这里插入图片描述

处理中序遍历中的括号在这里插入图片描述

专门修改针对符号的优先级，修改中序遍历的，很容易就看见所有的叶子结点都是数字，度数为2的点都是符号，并且没有括号的化，父节点的优先级大于或者等于子节点的优先级。如果不是就输出括号。

修改中序遍历实现。在这里插入图片描述

实现伪码 //后缀表达式生成表达式二叉树 BinaryTreeNode * Suffix_BinaryTree(SqStack &S , string &suffix) { //scan the whole suffix int i = 0 ; string temp = ""; BinaryTreeNode *mid,*right,*left; while(i while(suffix.at(i) != ' ') { temp.push_back(suffix.at(i)); i ++; } mid = new BinaryTreeNode(temp); S.push(mid); temp = ""; } //deal with signal else { S.pop(right); S.pop(left); temp = string(1,suffix.at(i)); mid = new BinaryTreeNode(temp,left,right); S.push(mid); i ++; temp = ""; } //在加一个是因为整个过程是使用空格进行分割的 i ++; } S.pop(mid); return mid; }

遍历的函数：只给出了子函数的递归部分，非递归部分

bool InOrderRur(BinaryTreeNode *root,bool (*visit)(BinaryTreeNode *temp)){ if(root) { char temp=' ',left= ' ',right=' '; if(root->GetLChild() &&root->GetRChild()){ temp = root->getData().at(0); left = root->GetLChild()->getData().at(0); right = root->GetRChild()->getData().at(0); if(isoperator(left) && getOperPri(left) InOrderRur(root->GetLChild(),visit2); } visit2(root); if(isoperator(right) && getOperPri(right) InOrderRur(root->GetRChild(),visit2); } return true; } return false; } 事故现场第一次提交

在这里插入图片描述

我真的觉得很离奇，我这次数过了，确实都是末尾有空格的，就算没有我也不会修改。对比下面，我觉得是一样的。在这里插入图片描述

看样例吧

在这里插入图片描述

内心是崩溃的，抓紧写完树，可也受够了。最后一次提交

在这里插入图片描述

分析与总结不得不说，今天真的是极其难受的一天，整整一天，参加个讲座怀疑自己上的是假大学，差距真大。整整一天就做了两道题，都是一开始思路就错了，用了好几个小时在证明自己是怎么错的。不过我还是做完了，啊哈哈不得不说，一开始思考的入手点真的很重要，虽然要坚信自己，但是不能一条道走到黑，最可怕的就是，到黑了，还是相信自己会对的。上面后序遍历生成二叉树很简单，但是遍历为带括号的中序式，我居然想用修改非递归的中序遍历，最后搞了一个小时，没出来。改递归的，十五分钟结束。如果不妥，请留言，你的留言是对我最大的鼓励。当然加扣扣问也行，一定知无不言，言无不尽，一块商量进步学习

【本文地址】

二叉树：后缀式转换成表达式二叉树（从后缀式的计算入手和遍历的递归实现入手）

二叉树：后缀式转换成表达式二叉树（从后缀式的计算入手和遍历的递归实现入手）

今日新闻

推荐新闻