blob: 2e584263d47d61610bf2a5a6fb3a57eaf420644e (
plain) (
blame)
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
|
---
abbrlink: 1421131593
categories:
- 往昔
date: "2025-05-25 18:46:37"
tags:
- 数据结构与算法
title: 【数据结构与算法】二叉树
---
## 定义
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
## 实现
### 结构定义
~~尝试了一下C语言，各种指针乱指，各种bug，暂时放自己一马，跟自己和解一下用js写写吧。~~
```js
class TreeNode {
constructor(data) {
this.data = data;
this.left = null; // 左节点
this.right = null; // 右边节点
}
}
```
### 创建对象并绑定节点
```js
// 手动绑定节点
let root = new TreeNode(1)
root.left = new TreeNode(2)
root.right = new TreeNode(3)
root.left.left = new TreeNode(4)
root.right.right = new TreeNode(5)
```
此时树的结构：
```
1
/ \
2 3
/ \ \
4 5 6
```
### 遍历二叉树
#### 前序遍历（DFS）
```js
function preOrder(node) {
if(node) {
console.log(node.data)
preOrder(node.left)
preOrder(node.right)
}
}
```
这里用递归调用，遍历到左右元素
#### 层序遍历（BFS）
```js
function levelOrder(root) {
const queue = [];
queue.push(root);
while (queue.length) {
const node = queue.shift();
console.log(node.data);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
```
|
