数据结构与算法之二叉树
最后更新:
阅读时间: 5
min
前言
二叉树是一种非线性的数据结构，以分层的方式存储数据。用于存储有层级关系的数据，如计算机文件，公司组织结构等数据。在二叉树上进行添加，查找和删除数据非常快。
实现
要实现树结构首先需要 Node 节点类，节点保存数据和它左右节点的链接，show 方法返回节点数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Node {
data: number
left: Node = null
right: Node = null
constructor(data: number) {
this.data = data
}
show() {
return this.data
}
}
|
实现二叉树，首先需要向树中插入节点的方法，这个方法先创建一个节点，判断树是否有根节点，没有的话将新节点作为树的根节点，否则进行下一步；
- 设当前节点为树的根节点，开始循环
- 如果插入节点的数据小于当前节点的数据，将新当前节点设为原当前节点的左节点，否则执行第 4 步
- 如果当前节点的左节点为
null ，就将新的节点插入这个位置，退出循环；否则执行下一次循环
- 将新当前节点设为原当前节点的右节点
- 如果当前节点的右节点为
null ，就将新的节点插入这个位置，退出循环；否则执行下一次循环
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
| class BST {
root: Node = null
length: number = 0
insert(data: number) {
const node = new Node(data)
if (this.root === null) {
this.root = node
return;
} else {
let originNode
let currentNode = this.root
while (true) {
originNode = currentNode
if (data < currentNode.data) {
currentNode = currentNode.left
if (currentNode === null) {
originNode.left = node
break
}
} else {
currentNode = currentNode.right
if (currentNode === null) {
originNode.right = node
break
}
}
}
}
}
}
|
遍历二叉树，中序，先序，后序
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
|
inOrder(node: Node) {
if (node !== null) {
this.inOrder(node.left)
node.show()
this.inOrder(node.right)
}
}
preOrder(node: Node) {
if (node !== null) {
node.show()
this.preOrder(node.left)
this.preOrder(node.right)
}
}
postOrder(node: Node) {
if (node !== null) {
this.postOrder(node.left)
this.postOrder(node.right)
node.show()
}
}
|
查找节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| find(data: number): Node {
let currentNode = this.root
while (currentNode !== null) {
if (currentNode.data === data) {
return currentNode
} else if (currentNode.data > data) {
currentNode = currentNode.left
} else {
currentNode = currentNode.right
}
}
return null
}
|
删除节点
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
| remove(data: number) {
this.root = this.removeNode(this.root, data)
}
removeNode(node: Node, data: number): Node {
if (node === null) {
return null
}
if (data === node.data) {
if (node.left === null && node.right === null) {
return null
}
if (node.left === null) {
return node.right
}
if (node.right === null) {
return node.left
}
const tempNode = this.min(node.right)
node.data = tempNode.data
node.right = this.removeNode(node.right, tempNode.data)
return node
} else if (node.data > data) {
node.left = this.removeNode(node.left, data)
return node
} else {
node.right = this.removeNode(node.right, data)
return node
}
}
|
最大值，最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
min(node: Node = this.root): Node {
let currentNode = node
while (currentNode.left !== null) {
currentNode = currentNode.left
}
return currentNode
}
max(node: Node = this.root): Node {
let currentNode = node
while (currentNode.right !== null) {
currentNode = currentNode.right
}
return currentNode
}
|
应用
BST 可以用来记录一组数据中数据出现的次数，首先在 Node 类上添加 count 属性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Node {
data: number
left: Node = null
right: Node = null
count: number = 0
constructor(data: number) {
this.data = data
}
show() {
return this.data
}
}
|
在 BST 类上添加 update 方法，当插入数据为新值时使用 insert 方法，当插入已经存在的值时使用 update 方法
1
2
3
4
5
6
7
8
| update(data: number): Node {
const node = this.find(data)
if(node !== null) {
node.count++
console.log(`${node.data}: `, node.count)
return node
}
}
|
测试一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| const bst = new BST();
const array = [2, 3, 5, 6, 10, 3, 4, 2, 8, 5, 9, 1, 4, 2, 5]
for (let index = 0; index < array.length; index++) {
const num = array[index]
if (bst.find(num) !== null) {
bst.update(num);
}
else {
bst.insert(num);
}
}
|
