P1305 新二叉树

Problem

题目简述

给你一个二叉树，求前序遍历。
输入的方法为左右孩子表示法。

思路

这道题的话可以DFS。定义一个结构体 \(node\), 存储 \(3\) 个信息： \(fa ,l,r\) 分别表示父亲、左子树、右子树。然后下标就是字母的 \(ACSII\) 码。

然后每次将左子树、右子树的 \(fa\) 更新，然后从 \(root\) 开始 \(DFS\)。

代码

#include <bits/stdc++.h>

using namespace std;

int n;

struct node {
    char fa, l, r;
} a[1010];

// 先序遍历：根左右
void dfs(char s) {
    printf("%c", s);
    if (a[s].l != '*') dfs(a[s].l);
    if (a[s].r != '*') dfs(a[s].r);
}

int main() {
    scanf("%d", &n);
    char c, root;
    for (int i = 1; i <= n; i++) {
        cin >> c;
        if (i == 1) root = c; // 输入的第一个一定为根。
        cin >> a[c].l >> a[c].r;
        a[a[c].l].fa = a[a[c].r].fa = c;
    }
    dfs(root); // 从root开始搜。
    return 0;
}