数据结构之二叉树

列表队列都是线性的数据结构,对应的还有非线性数据结构,其中树(tree)是比较常见的非线性数据结构。

tree

在树结构中,每个节点都有一个前节点(父节点),有一个或者多个后节点(子节点)。没有父节点的节点称为根节点,没有子节点的节点称为叶子节点。一个结点所拥有的子结点的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二叉树是一种最简单的数结构,它的子节点个数不超过两个,分别称为该结点的左子树与右子树。

节点的结构

节点是由节点保存的数据和指向左右树的指针组成,我们可以这么定义一个节点类:

1
2
3
4
5
function Node(data) {
this.data = data;
this.left = null; // 左节点
this.right = 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
function Tree() {
this.root = null; // 根节点

this.insert = function(data) {
var node = new Node(data);
if (!this.root) {
this.root=node;
} else {
var current = this.root;
var parent;
while (true) {
parent = current;
// 插入的节点与所有的节点的值进行比较,当大于当前节点的值,则插到左边,当小于当前节点的值,则插到右边,我们搜索时也采用统一的比较规则,快速找到节点位置
if (data < current.data) {
current = current.left;
if (current == null) {
parent.left = node;
break;
}
} else {
current = current.right;
if (current == null) {
parent.right = node;
break;
}
}
}
}
}
}

节点查找

节点查找可以按照节点插入规律:小左大右,依次循环比较每个节点的值和查找值,直到找到节点值和查找值一致的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
this.find = function(value) {
var current = this.root;
while (current != null) {
if (current.data < value) {
current = current.right;
} else if (current.data > value) {
current = current.left;
} else {
return current;
}
}

return null;
}

遍历

按照根节点访问的顺序不同,树的遍历分为以下三种:

  • 前序遍历:根->左->右
    1. 访问根节点
    2. 前序遍历左节点
    3. 前序遍历右节点
  • 中序遍历:左->根->右
    1. 中序遍历左节点
    2. 访问根节点
    3. 中序遍历右节点
  • 后序遍历:左->右->根
    1. 后序遍历左节点
    2. 后序遍历右节点
    3. 访问根节点

tree

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
// 前序遍历,根左右
this.preOrder = function(node) {
if (node != null) {
console.log(node.data);
this.preOrder(node.left);
this.preOrder(node.right);
}
}

// 中序遍历,左根右
this.inOrder = function(node) {
if (node != null) {
this.inOrder(node.left);
console.log(node.data);
this.inOrder(node.right);
}
}

// 后序遍历,左右根
this.postOrder = function(node) {
if (node != null) {
this.postOrder(node.left);
this.postOrder(node.right);
console.log(node.data);
}
}

二叉树的遍历是递归的典型运用场景。

查找最小值

根据插入的规则,最大的值应该在最左的叶子节点,因此,我们只需要遍历左子树,只到左子树left为null;

1
2
3
4
5
6
7
8
// 根据插入规则,最左的值,应该是最小值
this.getMin = function() {
var current = this.root;
while (current.left != null) {
current = current.left;
}
return current.data;
}

查找最大值

根据插入的规则,最大的值应该在最右的叶子节点,因此,我们只需要遍历右子树,只到右子树right为null;

1
2
3
4
5
6
7
8
// 根据插入规则,最右的值,应该是最大值
this.getMax = function() {
var current = this.root;
while (current.right != null) {
current = current.right;
}
return current.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
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// 二叉树

function Node(data) {
this.data = data;
this.left = null; // 左节点
this.right = null; // 有节点
}

function Tree() {
this.root = null; // 根节点

this.insert = function(data) {
var node = new Node(data, null, null);
if (!this.root) {
this.root=node;
} else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;
if (current == null) {
parent.left = node;
break;
}
} else {
current = current.right;
if (current == null) {
parent.right = node;
break;
}
}
}
}
}

// 前序遍历,根左右
this.preOrder = function(node) {
if (node != null) {
console.log(node.data);
this.preOrder(node.left);
this.preOrder(node.right);
}
}

// 中序遍历,左根右
this.inOrder = function(node) {
if (node != null) {
this.inOrder(node.left);
console.log(node.data);
this.inOrder(node.right);
}
}

// 后序遍历,左右根
this.postOrder = function(node) {
if (node != null) {
this.postOrder(node.left);
this.postOrder(node.right);
console.log(node.data);
}
}

this.find = function(value) {
var current = this.root;
while (current != null) {
if (current.data < value) {
current = current.right;
} else if (current.data > value) {
current = current.left;
} else {
return current;
}
}

return null;
}

// 根据插入规则,最左的值,应该是最小值
this.getMin = function() {
var current = this.root;
while (current.left != null) {
current = current.left;
}
return current.data;
}

// 根据插入规则,最右的值,应该是最大值
this.getMax = function() {
var current = this.root;
while (current.right != null) {
current = current.right;
}
return current.data;
}
}
有用就打赏一下作者吧!