PAT a1130

目的：根据二叉树，输出相应的中缀表达式

输入：

N  <=20 树上的节点数目

N个节点的信息

数据  左孩子  右孩子

数据是一个不超过10位的字符串，孩子是左右节点的标号。节点的标号从1~N

NULL由-1表示。

输出：

输出中缀表达式

算法：

中序遍历二叉树，得到正确的顺序。然后要添加括号。

怎么加括号呢？

#include<stdio.h>
#include<string>
#include<iostream>

using namespace std;

struct node{
    string data;
    int left,right;
};
int N,root = 1;
node tree[100];
int hash1[100] = {0};
string ans;

void DFS(int r)
{
    if(r == -1) return;
    if((tree[r].left != -1||tree[r].right!=-1)&&r!=root)
    {
        ans += "(";
        DFS(tree[r].left);
        ans += tree[r].data;
        DFS(tree[r].right);
        ans += ")";
    }else
    {
        if(r==root)
        {
            DFS(tree[r].left);
            ans += tree[r].data;
            DFS(tree[r].right);
        }else
        {
            ans += tree[r].data;
        }
    }
}

int main()
{
    scanf("%d",&N);

    for(int i=1;i<=N;i++)
    {
        cin>>tree[i].data>>tree[i].left>>tree[i].right;
        hash1[tree[i].left] = hash1[tree[i].right] = 1;
    }

    while(hash1[root]==1) root++;
    DFS(root);
    cout<<ans;
    return 0;
}

反思：这道题思路错误，看了大佬的才恍然大悟。总结，应该是对于树的遍历和递归了解得不够透彻。以及中缀表达式不熟悉。还有括号这个单词看不懂。还有要熟悉string的各种操作，加法和取子串等等。