一、什么是二叉树

二叉树是指每个节点最多含有两个子树的树结构。

特点:

  • 所有节点最多拥有两个子节点,即度不大于2
  • 左子树的键值小于根的键值,右子树的键值大于根的键值。
二、二叉树结构

每一个结点(除叶子结点外)都有左子树和右子树.

1
2
3
4
5
6
// 结点
var Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
}
三、遍历二叉树

在这里插入图片描述

  • 先序遍历 (根 => 左结点 => 右结点)
  • 中序遍历 (左结点 => 根 => 右结点)
  • 后序遍历 (左结点 => 右结点 => 根)

根据上图:

  • 先序遍历:ADBEFGC
  • 中序遍历:DBEAFGC
  • 后序遍历:DEBGFCA

代码封装:

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(node) {
if (node !== null) { // 判断参数(左孩子、右孩子、根结点)的值是否不为空
//访问左子树
inOrderTraverseNode(node.left);
console.log(node.key)
inOrderTraverseNode(node.right);
}
//如果为空,程序回溯,将结点的值输出
}

// 前序遍历
function(node) {
if (node !== null) { // 判断参数(左孩子、右孩子、根结点)的值是否不为空
console.log(node.key)
//访问左子树
preOrderTraverseNode(node.left);
preOrderTraverseNode(node.right);
}
//如果为空,程序回溯,将结点的值输出
}

// 后序遍历
function(node) {
if (node !== null) { // 判断参数(左孩子、右孩子、根结点)的值是否不为空
//访问左子树
postOrderTraverseNode(node.left);
postOrderTraverseNode(node.right);
console.log(node.key);
}
//如果为空,程序回溯,将结点的值输出
}
四、结点插入二叉树

根据二叉树的特点:左子树的键值小于根的键值,右子树的键值大于根的键值

比如:687234501这串数字插入到二叉树中
在这里插入图片描述
代码封装:

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
// 插入到二叉树
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
15
16
17
18
19
20
21
// 最小值
function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node.key
}
return null
}

// 最大值
function(node) {
if (node) {
while (node && node.right !== null) {
node = node.right
}
return node.key
}
return null
}
六、寻找二叉树的特定值

根据二叉树的特点:左子树的键值小于根的键值,右子树的键值大于根的键值

得:

  • 如果该值小于该结点则向左子树遍历。
  • 如果该值大于该结点则向右子树遍历。
  • 遍历到叶结点,还为找到该值,则该树没有改特定值。

代码封装:

1
2
3
4
5
6
7
8
9
10
11
12
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;
}
}
七、删除结点并保持二叉树结构不变
  1. 情况一:删除的结点是叶子结点:直接删除。
  2. 情况二:该结点小于(大于)当前遍历结点的值,则继续遍历左子树(右子树)。
  3. 情况三:结点刚好等于当前遍历结点值,此时还有分四种情况进行讨论(有左右子树没有左子树没有右子树没有左右子树
  4. 没有左右子树情况下,直接删除(node =null return node),即第一种情况。
    • 没有左子树 将 删除结点的右子树 赋值给 上层结点 的左子树或者右子树。
    • 没有右子树 将 删除结点的左子树 赋值给 上层结点 的左子树或者右子树。
    • 有左右子树 (1)在该结点的右子树中查找到最小值结点,(2)更新要删除结点的值为最小值,(3)删除最小值结点

代码封装:

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
//找到最小值的结点
function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node
}
return null
}
//删除结点
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)
} else { //相等
//没有左右子树,直接node 赋值为 null 返回null通过程序的回溯将node.left 或 node.right 赋值为 null
if (node.left === null && node.right === null) {
node = null;
return node;
}
//没有左子树,将 删除结点的右子树 赋值给 上层结点 的左子树或者右子树
if (node.left === null) {
node = node.right;
return node;
}
//没有右子树,将 删除结点的左子树 赋值给 上层结点 的左子树或者右子树
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;
}
}

源码下载