题目:
P1305 新二叉树 - 洛谷 | 计算机科学教育新生态
题目描述
输入一串二叉树,输出其前序遍历。
输入格式
第一行为二叉树的节点数 n。(1≤n≤26)
后面 n 行,每一个字母为节点,后两个字母分别为其左右儿子。特别地,数据保证第一行读入的节点必为根节点。
空节点用 *
表示
输出格式
二叉树的前序遍历。
输入输出样例
输入 #1
6 abc bdi cj* d** i** j**
输出 #1
abdicj
思路:
1.可以用一维数组+结构体的方法构建一个二叉树,由于题目所说(特别地,数据保证第一行读入的节点必为根节点。)并且我们前序遍历的时候需要知道根节点的下标,所以我们可以提取第一行输入,记录其根节点的下标,之后就是正常的n-1行的输入。
代码如下:
#include<iostream>
#include<string>
using namespace std;
struct Node{char left;char right;
};
Node tree[5000];
int n;
string s;
void dfs(char pos)
{cout << pos;if(tree[pos].left != '*')dfs(tree[pos].left);if(tree[pos].right != '*')dfs(tree[pos].right);}
int main(void)
{cin >> n;cin >> s;char root,l,r;root = s[0] ;l = s[1];r = s[2];tree[root].left = l;tree[root].right = r;for(int i = 1 ; i <= n - 1 ; i++){cin >> s;tree[s[0]].left = s[1];tree[s[0]].right = s[2];}dfs(root);}