二叉树的遍历#

1
void preorder(Node root) {
2
    cout << root.value << ' ';
3
    if (root.lson)
4
      preorder(tree[root.lson]);
5
    if (root.rson)
6
      preorder(tree[root.rson]);
7
}

1
void inorder(Node root) {
2
    if (root.lson)
3
      inorder(tree[root.lson]);
4
    cout << root.value << ' ';
5
    if (root.rson)
6
      inorder(tree[root.rson]);
7
}

1
void postorder(Node root) {
2
    if (root.lson)
3
      postorder(tree[root.lson]);
4
    if (root.rson)
5
      postorder(tree[root.rson]);
6
    cout << root.value << ' ';
7
}

1
void bfs(Node root) {
2
    queue<Node> Q;
3
    Q.push(root);
4

5
    while (!Q.empty()) {
6
        Node node = Q.front();
7
        Q.pop();
8
        cout << node.value << ' ';
9

10
        if (node.lson)
11
            Q.push(tree[node.lson]);
12
        if (node.rson)
13
            Q.push(tree[node.rson]);
14
    }
15
}

1
#include "bits/stdc++.h"
2
using namespace std;
3

4
const int N = 100010; // 数组大小，根据需求调整
5

6
struct Node {
7
    int value;    // 节点值
8
    int lson;     // 左子节点索引，0表示空
9
    int rson;     // 右子节点索引，0表示空
10
} tree[N];
11

12
int idx = 1; // 当前可用的节点索引，从1开始（0表示空节点）
13
unordered_map<int, int> val_to_idx; // 值到索引的映射
14
int n;
15

16

17
// 创建新节点（如果已存在则返回现有索引）
18
int create(int value) {
19
    if (val_to_idx.count(value)) {
20
        return val_to_idx[value];
21
    }
22
    tree[idx] = {value, 0, 0};
23
    val_to_idx[value] = idx;
24
    return idx++;
25
}
26

27
// 构建二叉树
28
void build(int n) {
29
    for (int i = 0; i < n; i++) {
30
        int root_val, l_val, r_val;
31
        cin >> root_val >> l_val >> r_val;
32

33
        int root_idx = create(root_val);
34

35
        if (l_val != 0) {
36
            int l_idx = create(l_val);
37
            tree[root_idx].lson = l_idx;
38
        }
39

40
        if (r_val != 0) {
41
            int r_idx = create(r_val);
42
            tree[root_idx].rson = r_idx;
43
        }
44
    }
45
}
46

47
void preorder(Node root) {
48
    cout << root.value << ' ';
49

50
    if (root.lson)
51
        preorder(tree[root.lson]);
52
    if (root.rson)
53
        preorder(tree[root.rson]);
54
}
55

56
void inorder(Node root) {
57
    if (root.lson)
58
        inorder(tree[root.lson]);
59

60
    cout << root.value << ' ';
61

62
    if (root.rson)
63
        inorder(tree[root.rson]);
64
}
65

66
void postorder(Node root) {
67
    if (root.lson)
68
        postorder(tree[root.lson]);
69
    if (root.rson)
70
        postorder(tree[root.rson]);
71

72
    cout << root.value << ' ';
73
}
74

75
void bfs(Node root) {
76
    queue<Node> Q;
77
    Q.push(root);
78

79
    while (!Q.empty()) {
80
        Node node = Q.front();
81
        Q.pop();
82
        cout << node.value << ' ';
83

84
        if (node.lson)
85
            Q.push(tree[node.lson]);
86
        if (node.rson)
87
            Q.push(tree[node.rson]);
88
    }
89
}
90

91
// 查找根节点（没有父节点的节点）
92
int find_root() {
93
    // 标记所有出现的节点
94
    vector<bool> has_parent(idx + 1, false);
95

96
    for (int i = 1; i < idx; i++) { // 对于节点i，它的子节点一定有父节点
97
        if (tree[i].lson != 0) {
98
            has_parent[tree[i].lson] = true;
99
        }
100
        if (tree[i].rson != 0) {
101
            has_parent[tree[i].rson] = true;
102
        }
103
    }
104

105
    // 找到没有父节点的节点（根节点）
106
    for (int i = 1; i < idx; i++) {
107
        if (!has_parent[i]) {
108
            return i;
109
        }
110
    }
111
    return 1; // 默认返回第一个节点
112
}
113

114
int main() {
115
    cin >> n;
116

117
    build(n);
118

119
    int root = find_root();
120

121
    cout << "先序遍历:" << endl;
122
    preorder(tree[root]);
123
    cout << '\n';
124
    cout << "中序遍历:" << endl;
125
    inorder(tree[root]);
126
    cout << '\n';
127
    cout << "后序遍历:" << endl;
128
    postorder(tree[root]);
129
    cout << '\n';
130
    cout << "层序遍历:" << endl;
131
    bfs(tree[root]);
132

133
    return 0;
134
}