P1305. 新二叉树

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 154 阅读时长 ≈ 1 分钟

考点

  • 二叉树

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int LEN = 30;
struct Node
{
    int lc_, rc_;
} tree[LEN];

int idx(char chr)
{
    return chr - 'a' + 1;
}

void pre_order(int root)
{
    if (!root)
        return;
    cout << (char)(root - 1 + 'a');
    pre_order(tree[root].lc_), pre_order(tree[root].rc_);
}

int main()
{
    int n, flag = true;
    cin >> n;
    char root, rt, lc, rc;
    while (n--)
    {
        cin >> rt >> lc >> rc;
        if (flag)
        {
            root = rt;
            flag = false;
        }
        tree[idx(rt)].lc_ = lc == '*' ? 0 : idx(lc);
        tree[idx(rt)].rc_ = rc == '*' ? 0 : idx(rc);
    }
    pre_order(idx(root));
    return 0;
}

思路

由于最多26个结点，且值均不重复；可将值作为结点在链式存储中的物理数组下标，即字母 - 'a' + 1

这样即可方便地修改父结点