洛谷P1305 新二叉树【树】

链接

https://www.luogu.org/problemnew/show/P1305

大意

给定一棵有 n $n$个节点的二叉树，告诉你每个点的字母以及它的左儿子和右儿子的标号求它的先序遍历。

思路

树型思想，根据根左右的顺序遍历

代码

// luogu-judger-enable-o2
#include<cstdio>
using namespace std;
char tree[27][3];
int n;
void put(char x)
{
    if(x=='*') return;//结束
    for(int i=1;i<=n;i++)
    if(tree[i][0]==x)//找到这个节点
    {
        putchar(tree[i][0]);//输出它
        put(tree[i][1]);put(tree[i][2]);//继续遍历它的儿子
    }
}
int main()
{
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++) gets(tree[i]);//输入
    put(tree[1][0]);
}

也可以用map库优化

代码2

#include<cstdio>
#include<map>
using namespace std;
char tree[27][3];
map<char,int>p;
int n;
void put(char x)
{
    if(x=='*') return;
    putchar(x);
    int i=p[x];
    put(tree[i][1]);put(tree[i][2]);
}
int main()
{
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++) {gets(tree[i]);p[tree[i][0]]=i;}//保存地址
    put(tree[1][0]);
}