人气最高的网络游戏排行榜_商城小程序报价_西安seo网站关键词优化_东莞商城网站建设

题目：

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);}