viviier

数据结构 - 二叉树的创建、遍历、查找和删除

数据结构 - 二叉树的创建、遍历、查找和删除

实现二叉查找树

二叉查找树由节点组成,所以我们要定义的第一个对象就是Node:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* @节点有data,左子节点,右子节点三个属性
* @以及一个show方法来输出节点的值
*/
class Node{
constructor(data, left, right) {
this.data = data
this.left = left
this.right = right
}
show(){
return this.data
}
}

接着来创建一个二叉查找树:

1
2
3
4
5
6
7
8
/*
* @BST默认有一个根节点root
*/
class BST{
constructor(){
this.root = null
}
}

当然,我们还需要为BST(二叉查找树)添加一些方法,如插入节点:

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
/*
* @insert方法,接受一个数据,然后通过new Node来创建节点
* @首先,判断当前的树是不是空树,如果是空树,那么这个newNode就是树的根节点
* @否则创建一个指针指向根节点,temp存储每次循环的父节点,对树进行循环判断
* @如果data小于指针所指向节点的data,那么,指向节点指向指向节点的左子节点,然后判断指向节点的left是否有值,
* @没有,就把newNode赋给指向节点的左子节点,跳出循环,如果有,就继续循环判断
* @否则,就将newNode进行右子节点的判断
*/
insert(data) {
let newNode = new Node(data, null, null)
if(this.root === null) {
this.root = newNode
} else {
let current = this.root,
temp
while(true) {
temp = current
if(data < current.data) {
current = current.left
if(current === null) {
temp.left = newNode
break
}
} else {
current = current.right
if(current === null) {
temp.left = newNodee
break
}
}
}
}
}

遍历二叉查找树

现在我们的BST已经初步成型,接下来就是实现遍历BST的方法。

树的遍历方法有三种:中序、先序和后序。中序遍历按照节点上的键值,以升序访问树上的所有节点。先序遍历先访问根节点,然后以再访问左子树和右子树。后序遍历先访问叶子节点,从左子树到右子树,再到根节点。

首先是中序遍历:

1
2
3
4
5
6
7
8
9
10
11
/*
* @用递归的方式实现中序遍历
* @先访问左子树,再访问根节点,最后访问右子树
*/
function inOrder(node) {
if(!(node === null)) {
inOrder(node.left)
console.log(node.show())
inOrder(node.right)
}
}

正序遍历:

1
2
3
4
5
6
7
8
9
10
11
/*
* @用递归的方式实现正序遍历
* @先访问根节点,再访问左子树,最后访问右子树
*/
function preOrder(node) {
if(!(node === null)) {
console.log(node.show())
inOrder(node.left)
inOrder(node.right)
}
}

后序遍历:

1
2
3
4
5
6
7
8
9
10
11
/*
* @用递归的方式实现后序遍历
* @先访问叶子节点,从左子树到右子树,最后访问根节点
*/
function postOrder(node) {
if(!(node === null)) {
inOrder(node.left)
inOrder(node.right)
console.log(node.show())
}
}

在二叉查找树上进行查找

对BST通常有三种查找类型:

  1. 查找給定值
  2. 查找最小值
  3. 查找最大值

我们先来实现查找最小值和最大值:

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
* @查找最小值
* @最小值总是在树的左子节点上
* @因此只需要对树的左子树挨个遍历,直到遍历到树的最左边的节点即可
*/
getMin(){
let current = this.root
while(!(current.left === null)) {
current = current.left
}
return current
}
1
2
3
4
5
6
7
8
9
10
11
12
13
/*
* @查找最大值
* @最大值总是在树的右子节点上
* @因此只需要对树的右子树挨个遍历,直到遍历到树的最右边的节点即可
*/
getMax(){
let current = this.root
while(!(current.right === null)) {
current = current.right
}
return current
}

接着我们来写查找給定值的函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* @查找給定值的节点
* @创建current指针指向当前根节点,进行比较后判断大小
* @如果給定值小于指针指向节点,那么向左遍历
* @反之,向右遍历
*/
find(data) {
let current = this.root
while(current !== null) {
if(data === current.data) {
return current
} else if(data < current.data) {
current = current.left
} else {
current = current.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
35
36
37
38
39
function remove(data) {
this.root = removeNode(this.root, data)
}
function getSmallest(node) {
if(node.left === null) {
return node
}
return getSmallest(node.left)
}
function removeNode(node, data) {
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
}
let tempNode = getSmallest(node.right)
node.data = tempNode.data
node.right = removeNode(node.left, tempNode.data)
return node
} else if(data < node.data) {
node.left = removeNode(node.left, data)
return node
} else {
node.right = removeNode(node.right, data)
return node
}
}
------本文结束感谢阅读------