https://shenao1100.github.io/assets/2025-04-15-binary-tree-BqHqPd-I.js

1const n=`---
2title: 二叉树入门
3description: 学习笔记
4author: ShenNya
5date: 2025-04-15 17:07:00 +0800
6categories: [Algorithm]
7tags: [Algorithm, C++]
8math: true
9mermaid: true
10---
11
12> 如果你看到我写这些这样的笔记了，那一定是我的大脑存不下，而之后这个东西又比较常用
13
14# 二叉树
15
16二叉树是一种树形结构(废话)
17
18它的特点是一个\`根(root)\`最多有两个\`子节点(node)\`
19
20
21**根节点（Root）**：树的起始节点，所有操作都从根节点开
22
23**父节点（Parent）**：某个节点的直接上级节
24
25**子节点（Child）**：某个节点的直接下级节
26
27**叶子节点（Leaf）**：没有子节点的节
28
29**深度（Depth）**：节点到根节点的路径长
30
31**高度（Height）**：从当前节点到最远叶子节点的路径长
32
33\`\`\`text
34      A
35    /   \\
36   B     C
37  / \\   / \\
38 D   E F   G
39\`\`\`
40
41喏，二叉树
42
43
44以\`A\`为例，\`A\`为\`根\`，\`B\`和\`C\`为两个\`节点\`
45
46\`A\`为\`B\`的父节点
47
48同时以\`B\`为根, \`D\`和\`E\`为两个\`节点\`，以此类推
49
50
51# 种类
52
53## 满二叉树
54
55除了叶子节点（没有子节点的节点）外都有两个子节点的
56
57满二叉树：
58\`\`\`text
59      A
60    /   \\
61   B     C
62  / \\   / \\
63 D   E F   G
64
65\`\`\`
66
67**非**满二叉树：
68\`\`\`text
69      A
70    /   \\
71   B     C
72  / \\   / 
73 D   E F   
74
75\`\`\`
76
77
78## 完全二叉树
79
801. 除了最后一层外，每层的节点都填满了
812. 最后一层节点
82
83
84完全二叉树：
85
86\`\`\`text
87      A
88    /   \\
89   B     C
90  / \\   / \\
91 D   E F   G
92
93\`\`\`
94\`\`\`text
95      A
96    /   \\
97   B     C
98  / \\   / 
99 D   E F   
100
101\`\`\`
102
103**非**完全二叉树：
104
105\`\`\`text
106      A
107    /   \\
108   B     C
109  / \\     \\
110 D   E     G
111
112\`\`\`
113
114> 除此之外还有 *平衡二叉树* 和 *二叉搜索树*, 下次一定.jpg
115
116# 遍历
117
118\`\`\`text
119      A
120    /   \\
121   B     C
122  / \\   / \\
123 D   E F   G
124\`\`\`
125
126## 先序遍历 (Preorder)
127
128根 → 左 → 右
129
130\`\`\`
131ABDECFG
132\`\`\`
133
1341. 从根出发(A)
1352. 先遍历左子树(B)
1363. 发现\`B\`为\`D\` \`E\`的父节点
1374. 遍历\`B\`的左子树\`D\`
1385. \`D\`没有\`子节点\`, 于是遍历右子树\`E\`

1396. \`A\`的左子树\`B\`遍历完毕，开始遍历右子树\`C\`
1407. 以此类推
141
142## 中序遍历 (Inorder)
143
144左 → 根 → 右
145
146\`\`\`
147DBEAFCG
148\`\`\`
149## 后序遍历 (Postorder)
150
151左 → 右 → 根
152
153\`\`\`
154DEBFGCA
155\`\`\`
156## 层序遍历 (Level-order)
157
158按层从上到下、从左到右访问节点
159
160\`\`\`
161ABCDEFG
162\`\`\`
163
164
165# C++实现
166
167## 节点
168
169首先实现一个节点，这个节点有一个值，并且有0-2个子节点：
170
171\`\`\`cpp
172struct TreeNode{
173    char val;       // 当前节点的值
174    TreeNode* left; // 左子节点
175    TreeNode* right;// 右子节点
176    TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
177};
178\`\`\`
179
180## 创建一个树
181
182我们来创建一个这样的树：
183\`\`\`text
184      A
185     / \\
186    B   C
187   / \\
188  D   E
189\`\`\`
190
191\`\`\`cpp
192
193int main(){
194    TreeNode* root = new TreeNode('A');   // 这就是根节点
195    root->left = new TreeNode('B');
196    root->right = new TreeNode('C');
197    root->left->left = new TreeNode('D');
198    root->left->right = new TreeNode('E');
199
200    return 0;
201}
202\`\`\`
203
204## 先序排列
205
206传入根节点之后按照根左右的顺序递归
207
208\`\`\`cpp
209void preorder(TreeNode* root){
210    // 输出根
211    cout << root->val;
212    if (root->left != nullptr){
213        // 递归左子树 
214        preorder(root->left);
215    }
216    if (root->right != nullptr){
217        // 递归右子树 
218        preorder(root->right);
219    }
220}
221\`\`\`
222
223## 中序排列
224
225传入根节点之后按照左根右的顺序递归
226
227
228\`\`\`cpp
229void inorder(TreeNode* root){
230    if (root->left != nullptr){
231        inorder(root->left);
232    }
233    cout << root->val;
234    if (root->right != nullptr){
235        inorder(root->right);
236    }
237}
238\`\`\`
239
240## 后续排列
241
242传入根节点之后按照左右根的顺序递归
243
244\`\`\`cpp
245void postorder(TreeNode* root){
246    if (root->left != nullptr){
247        postorder(root->left);
248    }
249    if (root->right != nullptr){
250        postorder(root->right);
251    }
252    cout << root->val;
253}
254\`\`\`
255
256## 层序排列
257
258层序排列不想需要递归，使用队列即可
259
260\`\`\`cpp
261void levelorder(TreeNode* root){
262    queue<TreeNode*> q;
263    q.push(root);
264    while (!q.empty()){
265        TreeNode* node = q.front();
266        cout << node->val;
267        if (node->left){
268            q.push(node->left);
269        }
270        if (node->right){
271            q.push(node->right);
272        }
273        q.pop();
274    }
275}
276\`\`\`
277
278## 完整代码
279
280\`\`\`cpp
281#include <iostream>
282#include <queue>
283
284using namespace std;
285
286struct TreeNode{
287    char val;
288    TreeNode* left;
289    TreeNode* right;
290    TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
291};
292
293void preorder(TreeNode* root){
294    cout << root->val;
295    if (root->left != nullptr){
296        preorder(root->left);
297    }
298    if (root->right != nullptr){
299        preorder(root->right);
300    }
301}
302
303void inorder(TreeNode* root){
304    if (root->left != nullptr){
305        inorder(root->left);
306    }
307    cout << root->val;
308    if (root->right != nullptr){
309        inorder(root->right);
310    }
311}
312
313void postorder(TreeNode* root){
314    if (root->left != nullptr){
315        postorder(root->left);
316    }
317    if (root->right != nullptr){
318        postorder(root->right);
319    }
320    cout << root->val;
321}
322
323void levelorder(TreeNode* root){
324    queue<TreeNode*> q;
325    q.push(root);
326    while (!q.empty()){
327        TreeNode* node = q.front();
328        cout << node->val;
329        if (node->left){
330            q.push(node->left);
331        }
332        if (node->right){
333            q.push(node->right);
334        }
335        q.pop();
336    }
337}
338int main(){
339    TreeNode* root = new TreeNode('A');
340    root->left = new TreeNode('B');
341    root->right = new TreeNode('C');
342    root->left->left = new TreeNode('D');
343    root->left->right = new TreeNode('E');
344
345    preorder(root);
346    cout << endl;
347    inorder(root);
348    cout << endl;
349    postorder(root);
350    cout << endl;
351    levelorder(root);
352    return 0;
353}
354\`\`\`
355
356
357`;export{n as default};