【树】洛谷 P1305 新二叉树

题目描述

输入一串完全二叉树，用遍历前序打出。

输入输出格式

输入格式：
第一行为二叉树的节点数n。

后面n行，每一个字母为节点，后两个字母分别为其左右儿子。

空节点用*表示

输出格式：
前序排列的完全二叉树

输入输出样例

输入样例#1：
6
abc
bdi
cj*
d**
i**
j**
输出样例#1：
abdicj

代码

#include<iostream>
using namespace std;
int lc[60],rc[60],s[60],t[60];
char ch[5];
int to[130];
char tto[60];
void qx(int x)
{
    if(x)
    {
        printf("%c",tto[x]);
        qx(lc[x]);
        qx(rc[x]);
    }
}
int main()
{
    int n;
    for(int i='a';i<='z';++i)to[i]=i-'a'+1;
    for(int i='A';i<='Z';++i)to[i]=i-'a'+1+26;
    for(int i=1;i<=26;++i)tto[i]=i+'a'-1;
    for(int i=27;i<=52;++i)tto[i]=i+'A'-1-26;
    scanf("%d\n",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ch+1);
        s[to[ch[1]]]=1;     
        lc[to[ch[1]]]=to[ch[2]];
        t[to[ch[2]]]=1;     
        rc[to[ch[1]]]=to[ch[3]];
        t[to[ch[3]]]=1;     
    }
    int root=0;
    for(int i=1;i<=52;++i)if(s[i]&&!t[i])root=i;
    qx(root);
    return 0;
}