白筱汐

想都是问题,做都是答案

0%

二叉树的基本操作

二叉树的定义

二叉树是一种数据结构,它由一组称为节点的元素组成,这些节点通过边连接。每个节点最多可以有两个子节点,分别称为左子节点和右子节点。

二叉树的主要方法有:

  • 创建
  • 添加节点
  • 查找节点
  • 删除节点
  • 获得树的高度
  • 获得树的节点树
  • 各种遍历方法(请参考我的博客里对于二叉树的前序、中序、后续遍历描述的文章)

二叉树的实现

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
class Node {
constructor(data) {
this.parent = null
this.data = data
this.left = null
this.right = null
}
}

class Tree {
constructor() {
this.root = null
this.size = 0
}
// 插入
insert(data) {}

// 删除
remove(data) { }
// 节点树
size() { }
// 最小节点
minNode() { }
// 最大节点
maxNode() { }
// 高度
height() {}
}

插入节点

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
class Tree {
constructor() {
this.root = null
this.size = 0
}

// 插入
insert(data) {
const newNode = new Node(data)
// 如果树为空
if (!this.root) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
}

insertNode(node, newNode) {
// 要插入的值小于当前节点的值
if (newNode.data < node.data) {
// 左子节点不存在
if (!node.left) {
node.left = newNode
newNode.parent = node
} else {
// 向左子树递归进行对比判断,是插入到左子树还是右子树
this.insertNode(node.left, newNode)
}
} else {
// 要插入的值大于等于当前节点的值
if (!node.right) { // 右子节点不存在
node.right = newNode
newNode.parent = node
} else {
// 向右子树递归进行对比判断,是插入到左子树还是右子树
this.insertNode(node.right, newNode)
}
}
}
}

查找节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Tree {
// ...

find(data) {
return this.find(this.root,data)
}

//查找节点
findNode(node,data) {
if (!node) {
return null
}
// 找到节点
if (data == node.data) {
return node
// 检查目标值是否在左子树中
} else if (data < node.data) {
return this.findNode(node.left, data)
// 检查目标值是否在右子树中
} else {
return this.findNode(node.right, data)
}
}
}

删除节点

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
remove(data) {
// 先找到要删除的节点
let node = this.find(data)
if (node) {
this.size--
// 被删除的节点是根节点
if (node === this.root) {
this.root = null
return true
}
let left = node.left,right = node.right // 左右子树
let parent = node.parent // 父节点
let isLeft = parent && parent.left === node // 是左子树还是右子树
// 1. 被删除节点没有子节点,直接删除
if (!left && !right) {
if (isLeft) {
parent.left = null
} else {
parent.right = null
}
} else if (left && !right) {
// 2. 被删除节点只有左子节点 (被删除节点的左子节点指向父节点)
if (isLeft) {
parent.left = left
} else {
parent.right = left
}
left.parent = parent
} else if (!left && right) {
// 3. 被删除节点只有右子节点 (被删除节点的右子节点指向父节点)
if (isLeft) {
parent.left = right
} else {
parent.right = right
}
right.parent = parent
} else if (left && right) {
// 4. 被删除节点既有左子节点,又有右子节点
// 假设使用右子树继位,则需要找到右子树中最靠左边的值
let child = right
while (child.left) {
child = child.left
}
this.remove(child.data) // 然后改删除叶子节点
node.data = child.data // 找到右子树中最接近的值,覆盖原先要删除的节点的值
}
}
}

删除二叉树的节点比较复杂,主要有4种情况,这里解释一下每种情况的处理方法:

  1. 被删除的节点是叶子节点,直接删除即可。判断它是父节点的哪一边的孩子节点,将相应的属性设置为null。
  2. 被删除的节点只有左子节点,需要用它的左子节点把它自己给替换下去。
  3. 被删除的节点只有右子节点,需要用它的右子节点把它自己给替换下去。
  4. 被删除的节点有左右2个子节点。这时候我们需要考虑是用左子树继位还是用右子树继位。如果用左子树继位(实例代码中使用右子树继位),需要找到左子树最靠右的节点。如果该节点没有子节点,只需用它替换目标节点。如果该节点有一个左子节点,请将其替换为左子节点,然后将目标节点替换为最右边的节点。

删除节点的第四种情况最为复杂,一般书中给出的操作方式读起来非常的费劲。上面的解释来自书籍《算法基础》,但是具体操作的时候有一些技巧。在使用左子树继位的时候,找到了最右边的节点值,把它的值记录下来,然后删除这个节点,最后把原先要删除的值与记录的值替换。这样就相当于完成了上面的节点替换的操作(操作来自《JavaScript算法》)。

最大值与最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 最小节点
minNode(node) {
var cur = node || this.root
while (cur.left) {
cur = cur.left
}
return cur
}
// 最大节点
maxNode() {
var cur = this.root
while (cur.right) {
cur = cur.right
}
return cur
}
getMax() {
var node = this.maxNode()
return node ? node.data : null
}
getMin() {
var node = this.minNode()
return node ? node.data : null
}

高度

1
2
3
4
5
6
7
8
9
10
11
height() {
return this.getNodeHeight(this.root)
}
getNodeHeight(node) {
if (node == null) {
return 0
}
let leftChildHeight = this.getNodeHeight(node.left)
let rightChildHeight = this.getNodeHeight(node.right)
return Math.max(leftChildHeight, rightChildHeight) + 1
}

节点数量

1
2
3
4
5
6
7
8
9
10
11
size() { // this.getNodeSize(this.root)
return this.size
}
getNodeSize(node) {
if (node == null) {
return 0
}
let leftChildSize = this.getNodeSize(node.left)
let rightChildSize = this.getNodeSize(node.right)
return leftChildSize + rightChildSize + 1
}

翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 翻转二叉树
invertTree() {
if (root === null) {
return null;
}

// 交换左右子树
let temp = root.left;
root.left = root.right;
root.right = temp;

// 递归翻转左右子树
this.invertTree(root.left);
this.invertTree(root.right);

return root
}