二叉树的构建与遍历
二叉树的构建与遍历
问题描述
假设二叉树中的每个结点值为单个整数,采用二叉链结构存储,假定每颗二叉树不超过2000个节点。设计算法完成
- 按从左到右的顺序输出二叉树的叶子结点
- 按从右到左的顺序输出二叉树的叶子结点
- 输出二叉树所有的节点,按照从根节点开始,逐层输出,同一层按照从右向左的顺序
输入形式
每个测试是一颗二叉树的括号表示法字符串
输出形式
第一行是按从左到右的顺序输出二叉树的叶子结点,结点之间用空格隔开 第二行是按从右到左的顺序输出二叉树的叶子结点,结点之间用空格隔开 第三行是输出二叉树所有的节点,按照从根节点开始,逐层输出,同一层按照从右向左的顺序,结点之间用空格隔开
样例输入
1
1(2(4,5),3)
样例输出
1
2
3
4 5 3
3 5 4
1 3 2 5 4
题解
这是作者数据结构课的作业,属于是最基础的二叉树构建、dfs和bfs。这道题选择使用数组链表来进行构建,不得不说这种构建方式真是十分美妙。由于获取到的是一个字符串表达式,我们可以用指针来对这一个串进行递归,这里用到了*&,即对指针的引用,这为递归提供了很大的便利。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstring>
#include <iostream>
using namespace std;
const int N = 10010;
/* l数组表示当前节点的左节点,r数组同理,e表示节点值,q为后面用到的队列 */
int l[N], r[N], e[N], q[N], root, idx;
char line[N];
int pars(char *&s) {
if (*s == '\0' || !isdigit(*s)) return 0;
int u = ++idx;
int val = 0;
while (isdigit(*s)) {
val = val * 10 + (*s - '0');
s++;
}
e[idx] = val;
if (*s == '(') {
s++;
l[u] = pars(s); // 先递归左树,后递归右树
if (*s == ',') {
s++;
r[u] = pars(s);
}
if (*s == ')') {
s++;
}
}
return u;
}
void dfs1(int u) {
if (!u) return;
int left = l[u], right = r[u];
if (!left && !right) {
printf("%d ", e[u]);
return;
}
dfs1(left);
dfs1(right);
}
void dfs2(int u) {
if (!u) return;
int left = l[u], right = r[u];
if (!left && !right) {
printf("%d ", e[u]);
return;
}
dfs2(right);
dfs2(left);
}
/* 队列实现bfs */
void bfs(int u) {
int hh = 0, tt = 0;
q[0] = u;
while (hh <= tt) {
int v = q[hh++];
if (v) {
q[++tt] = r[v];
q[++tt] = l[v];
printf("%d ", e[v]);
}
}
puts("");
}
int main() {
// freopen("in.txt", "r", stdin);
memset(line, 0, sizeof line);
scanf("%s", line);
char *input = line;
root = pars(input);
dfs1(root);
puts("");
dfs2(root);
puts("");
bfs(root);
return 0;
}
This post is licensed under CC BY 4.0 by the author.