数据结构-树

树是一种分层数据的抽象模型。它是一种非顺序数据结构,对于存储需要快速查找的数据非常有用。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个节点:一个是左侧子节点,另一个是右侧子节点。
二叉搜索树(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
37
function BinarySearchTree() {
var Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
// insertNode 会帮助我们找到新节点应该插入的正确位置
var insertNode = function(node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
// 向树中插入一个新的键
this.insert = function(key) {
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
}

树的遍历

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function BinarySearchTree() {
// ...
var inOrderTraverseNode = function(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback); // 先左
callback(node.key);
inOrderTraverseNode(node.right, callback); // 后右
}
};
this.inOrderTraverse = function(callback) {
inOrderTraverseNode(root, callback);
};
}

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function BinarySearchTree() {
// ...
var preOrderTraverseNode = function(node, callback) {
if (node !== null) {
callback(node);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
};
this.preOrderTraverse = function(callback) {
preOrderTraverseNode(root, callback);
};
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function BinarySearchTree() {
// ...
var postOrderTraverseNode = function(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
};
this.postOrderTraverse = function(callback) {
postOrderTraverseNode(root, callback);
};
}

搜索树中的值

最大值和最小值

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
function BinarySearchTree() {
// ...
var minNode = function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
};
this.min = function() {
return minNode(root);
};
var maxNode = function(node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};
this.max = function() {
return maxNode(root);
};
}

特定值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function BinarySearchTree() {
// ...
var searchNode = function(node, key) {
if (node === null) {
return false;
}
if (key < node.key) {
return searchNode(node.left, key);
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true;
}
};
this.search = function(key) {
return searchNode(root, key);
};
}

移除一个节点

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
function BinarySearchTree() {
// ...
var removeNode = function(node, key) {
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = removeNode(node.right, key);
return node;
} else { // 键值等于node.key
// 第一种情况--一个叶节点
if (node.left === null && node.right === null) {
node = null;
return node;
}
// 第二种情况--一个只有一个子节点的节点
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
// 第三种情况--一个有两个子节点的节点
var aux = findMinNode(node.right); // 与 min 方法一致
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
};
this.remove = function(key) {
root = removeNode(root, key);
};
}