【简单数据结构】二叉树的建立和递归遍历--洛谷 P1305

题目描述

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

输入格式

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

后面n行，每一个字母为节点，后两个字母分别为其左右儿子。

空节点用*表示

输出格式

前序排列的二叉树

输入输出样例

输入 #1

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

输出 #1

abdicj

代码：

 1 #include <cstdio>
 2 using namespace std;
 3
 4 struct Node{
 5     int lsh = -1 , rsh = -1;　　//左子树和右子树
 6 };
 7
 8 bool vis[30];　　//由于数组不是连续的，通过vis判断是否有值
 9 bool isNotRoot[100];　//不是根，最后只有一个节点的值是false
10 char s[5];
11 Node tree[50];　　//五十个节点
12
13 void build(int P,int l,int r)
14 {
15     vis[P] = true;
16     if (l >= 0)
17     {
18         tree[P].lsh = l;
19         isNotRoot[l] = true;
20         vis[l] = true;
21     }
22     if (r >= 0)
23     {
24         tree[P].rsh = r;
25         isNotRoot[r] = true;
26         vis[r] = true;
27     }
28 }
29
30 void dfs(int n)
31 {
32     if (n<0) return;
33     printf("%c",char(n+'a'));//前序遍历的递归写法，中序和后序调整位置即可
34     dfs(tree[n].lsh);
35     dfs(tree[n].rsh);
36 }
37
38 int main()
39 {
40     int n =0;
41     scanf("%d",&n);
42
43     for (int i=0;i<n;i++)
44     {
45         scanf("%s",s);
46         build(s[0]-'a',s[1]-'a',s[2]-'a');
47     }
48
49     for (int i=0;i<=26;i++){
50         if (vis[i] && !isNotRoot[i])　　//如果有值并且是根节点就遍历
51         {
52             dfs(i);
53             break;　　//考虑到只有一个根节点，一个循环结束就不用继续了
54         }
55     }
56     printf("\n");
57     return 0;
58 }