题目描述：输入一串二叉树，输出其前序遍历。
输入格式：第一行为二叉树的节点数 $ n(1 \le n \le 26) $, 后面 \(n\) 行，每一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。空节点用*表示
输出格式：二叉树的前序遍历。
思路：对于二叉树中的每个结点, 将其类型定义为结构体类型, 结构体中的数据包括：当前节点的值、左儿子编号、右儿子编号。对于这类题目，基本上需要三个函数：第一个函数是新建节点, 第二个函数用来给结点添加儿子节点, 第三个函数用于输出遍历序列。对于此题, 每个结点为小写字母, 因此, 可以将每个结点 $ x $ 的编号定义为 $ x - 'a' + 1 $。对于先序遍历, 先递归左儿子然后递归右儿子即可。
点击查看代码
#include <bits/stdc++.h>
#define sz(a) ((int) (a).size())
using i64 = long long;
inline i64 read() {
bool sym = false; i64 res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
struct Node {
char data, l, r;
Node(char _d = '?', char _l = '?', char _r = '?') : data(_d), l(_l), r(_r) {}
};
const int N = 100 + 10;
Node nodes[N];
int idx;
void Newnode(char c) {
nodes[c - 'a' + 1].data = c;
}
void add(char x, char y, bool addright) {
//给结点x添加儿子节点y
if (addright) nodes[x - 'a' + 1].r = y;
else nodes[x - 'a' + 1].l = y;
}
void pre(int x) {
// 求树的先序遍历结果
printf("%c", nodes[x].data);
if (nodes[x].l != '?') pre(nodes[x].l - 'a' + 1);
if (nodes[x].r != '?') pre(nodes[x].r - 'a' + 1);
}
int main() {
int n = read(), root = 0;
for (int i = 1; i <= n; i++) {
std::string s;
std::cin >> s;
if (i == 1) root = s[0] - 'a' + 1;
for (auto c : s) {
if (c != '*') Newnode(c);
}
if (s[1] != '*') add(s[0], s[1], false);
if (s[2] != '*') add(s[0], s[2], true);
}
pre(root);
return 0;
}//