排序二叉树
什么是排序二叉树
排序二叉树：树的左节点小于根节点，右节点大于根节点。
前序遍历：8->3->1->6->4->7->10->14->13 中序遍历：
- 根节点：最顶部的节点(例如上图中的节点 8)
- 中间节点：中间的节点
- 叶子结点：没有孩子节点的节点(上图中的节点 4，7，13)
- 节点层次：二叉树的高(高为 4)
- 排序二叉树：左子节点值小于父节点，右子节点值大于父节点
二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
前序遍历--根左右
规则：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。遍历顺序为：A->B->D->G->H->C->E->I->F。
var preOrderTraverseNode = function(node, callback) {
if (node !== null) {
callback(node.key);
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
2
3
4
5
6
7
8
9
10
11
中序遍历(升序)--左根右
规则是：若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。遍历顺序为：G->D->H->B->A->E->I->C->F
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
2
3
4
5
6
7
8
9
10
11
后序遍历--左右根
规则是：若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。遍历顺序为：G->H->D->B->I->E->F->C->A。
var postOrderTraverseNode = function(node, callback) {
if (node !== null) {
postOrderTraverseNodev(node.left, callback);
postOrderTraverseNodev(node.right, callback);
callback(node.key);
}
};
// 后序遍历接口--左右根
this.postOrderTraverse = function(callback) {
postOrderTraverseNode(root, callback);
};
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
层序遍历
规则是：若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。遍历顺序为：A->B->C->D->E->F->G->H->I。
查找二叉树中的最小值
找到根节点的左子树中没有左子树的叶子节点。
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);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
查找二叉树中的最大值
找到根节点的左右子树中没有右子树的叶子节点。
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
2
3
4
5
6
7
8
9
10
11
12
13
查找二叉树中的指定值
从根节点开始查找，如果要查找的节点值小于当前节点，则进入当前节点的左子树继续查找，否则进入当前节点的右子树进行查找。
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
删除节点
var findMinNode = function(key) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
}
return null;
};
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 {
// 针对叶子节点的情况
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);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
};
this.remove = function(key) {
root = removeNode(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
44
45
46
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