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

本文链接：https://blog.csdn.net/Blackoutdragon/article/details/110876840

博客讨论了如何设计二叉树的抽象数据类型，包括采用递归方法处理基本操作。此外，还介绍了如何将后缀表达式转换为表达式二叉树，并提供了中缀、前缀和后缀遍历的结果。在实现过程中，作者遇到了困难，但最终解决了括号处理的问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

文章目录

问题描述 :

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

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

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

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

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

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

参考函数原型：

//后缀表达式生成表达式二叉树

template<class ElemType>

BinaryTreeNode<ElemType> * Suffix_BinaryTree(SqStack <BinaryTreeNode<ElemType> *> &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 <BinaryTreeNode *> &S
        , string &suffix) {
    //scan the whole suffix
    int i = 0 ;
    string temp = "";
    BinaryTreeNode<string> *mid,*right,*left;

    while(i < suffix.length()) {
        if(suffix.at(i) >= '0' && suffix.at(i) <= '9') {
            while(suffix.at(i) != ' ') {
                temp.push_back(suffix.at(i));
                i ++;
            }
            mid = new BinaryTreeNode<string>(temp);
            S.push(mid);
            temp = "";

        }
        //deal with signal
        else {
            S.pop(right);
            S.pop(left);
            temp = string(1,suffix.at(i));
            mid = new BinaryTreeNode<string>(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)<getOperPri(temp)){

            cout<<"(";
            InOrderRur(root->GetLChild(),visit2);
            cout<<")";
        }else{
            InOrderRur(root->GetLChild(),visit2);
        }
        visit2(root);
        if(isoperator(right)
           && getOperPri(right)<getOperPri(temp)){
            cout<<"(";
            InOrderRur(root->GetRChild(),visit2);
            cout<<")";
        }else{
            InOrderRur(root->GetRChild(),visit2);
        }
        return true;
    }
    return false;
}

事故现场

第一次提交

在这里插入图片描述

我真的觉得很离奇，我这次数过了，确实都是末尾有空格的，就算没有我也不会修改。对比下面，我觉得是一样的。
看样例吧

在这里插入图片描述

内心是崩溃的，抓紧写完树，可也受够了。

最后一次提交

在这里插入图片描述

分析与总结

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