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;
}
标签:char,int,dfs,P1305,fa,二叉树,root
From: https://www.cnblogs.com/yhx0322/p/17739242.html