本文共 1228 字，大约阅读时间需要 4 分钟。

题目链接：

题目大意：给一个二叉树，输出中缀表达式，且加上括号表示运算的优先级。

解题思路：首先根据所有孩子结点编号寻找 1～n 中没有出现过的编号标记为 rt，即树的根结点。然后进行从 rt 结点开始 inT(rt) 如果当前 id == -1 说明当前没有结点则返回空字符串；当 r != -1 说明该结点不是叶子节点(不可能存在只有左边没有右边的情况的啦，因为那不符合一个算式～左边可以是空表示0～右边不可以的～)，那么就将左右结点的 da 和自身的 da 串成字符串，保存在自己的 da 中～如果当前 id 又不是根结点，那就在左右两边加上括号～最后输出 inT(rt) 的结果即可。

Ps：struct：如果在构造一个新的构造函数中参数里带有 string 类型，一定要补上默认的0参数构造函数；如果用 char* 替代 string，那么不需要补默认构造函数。

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;struct node{    int l,r,idx,local;    string da;    node(){}    node(int l,int r,string da):l(l),r(r),da(da){}};int rt;int vis[30];vector
     
       v;string inT(int id){    if(id==-1) return "";    if(v[id].r!=-1)    {        v[id].da=inT(v[id].l) + v[id].da + inT(v[id].r);        if(id!=rt) v[id].da="(" + v[id].da + ")";    }    return v[id].da;}int main(){    int n,l,r;    char da[20];    scanf("%d",&n);    v.resize(30);    for(int i=1;i<=n;i++)    {        scanf("%s%d%d",da,&l,&r);        v[i]=node(l,r,da);        vis[r==-1?0:r]=vis[l==-1?0:l]=1;    }    for(int i=1;i<=n;i++) if(vis[i]==0){rt=i; break;}    cout<
      
       <
      
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/82016389 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！