题解：洛谷 P1305 新二叉树

【题目来源】

洛谷：P1305 新二叉树 - 洛谷

【题目描述】

输入一串二叉树，输出其前序遍历。

【输入】

第一行为二叉树的节点数 \(n\)。(\(1\le n\le 26\))

后面 \(n\) 行，每一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。

空节点用 * 表示

【输出】

二叉树的前序遍历。

【输入样例】

6
abc
bdi
cj*
d**
i**
j**

【输出样例】

abdicj

【解题思路】

【算法标签】

《洛谷 P1305 新二叉树》 #字符串# #搜索# #树形数据结构# #递归#

【代码详解】

#include <bits/stdc++.h>
using namespace std;// 定义二叉树节点结构体
struct Node 
{int left;   // 左子节点索引int right;  // 右子节点索引
} t[30];       // 最多26个字母节点（a-z）int n;         // 节点数量
int root;      // 根节点索引
string s;      // 临时输入字符串/*** 前序遍历二叉树* @param x 当前节点索引*/
void preOrder(int x)
{if (x == -1) return;  // 空节点返回cout << char(x + 'a');  // 输出当前节点字符preOrder(t[x].left);    // 递归遍历左子树preOrder(t[x].right);   // 递归遍历右子树
}int main()
{// 输入节点数量cin >> n;// 读取每个节点的信息for (int i = 0; i < n; i++) {cin >> s;// 第一个节点作为根节点if (i == 0) {root = s[0] - 'a';}// 处理左子节点if (s[1] == '*') {t[s[0] - 'a'].left = -1;  // '*'表示空节点}else {t[s[0] - 'a'].left = s[1] - 'a';}// 处理右子节点if (s[2] == '*') {t[s[0] - 'a'].right = -1;  // '*'表示空节点}else {t[s[0] - 'a'].right = s[2] - 'a';}}// 执行前序遍历preOrder(root);return 0;
}

【运行结果】

6
abc
bdi
cj*
d**
i**
j**
abdicj