7.Javascript二叉树

Javascript数据结构与算法 评论

7-二叉树（第10章）

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据 。本章将研究一种特殊的树： 二叉查找树。

7.1 什么是树

树是一种数据结构，由一组以边线连接的节点组成。以下就是一颗普通的树

树

树的节点：一棵树最上面的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。一个节点可以有 0 个、 1 个或多个子节点。没有任何子节点的节点称为叶子节点。

树的遍历：沿着树的一组特定的边，可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径，在图中用虚线表示。以某种特定顺序访问树中所有的节点称为树的遍历

树的深度：树可以分为几个层次，根节点是第 0 层，它的子节点是第 1 层，子节点的子节点是第 2层，以此类推。树中任何一层的节点可以都看做是子树的根，该子树包含根节点的子节点，子节点的子节点等。我们定义树的层数就是树的深度

7.2 二叉树

首先我们要了解下什么是二叉树，二叉树是一种特殊的树，它的子节点个数不超过两个。二叉查找树是在二叉树的基础上对树的结构进行了进一步的约束。

二叉查找树又名二叉排序树，有时候也叫二叉搜索树。它具有以下特征：

  • 若左子树不为空，则左子树上所有的结点的值均小于它根节点的值
  • 若右子树不为空，那么右子树上所有节点的值均大于它根节点的值
  • 左右子树也分别为二叉查找树
  • 没有键值相等的节点

7.3 实现一个二叉树

二叉树都是由节点组成的，所以我们要实现二叉树必须要先实现节点，一个节点通常包含三部分——数据、左子节点、右子节点。因此我们可以定义这样的一个node对象来代表我们的节点。

1
2
3
4
5
6
7
class Node {
  constructor(data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }
}

Node 对象既保存数据，也保存和其他节点的链接

现在我们可以创建一个类，用来表示二叉查找树，我们让类只包含一个数据成员：一个表示二叉查找树根节点的 Node 对象。该类的构造函数将根节点初始化为 null，以此创建一个空节点。

接下来我们来实现一个insert方法，用来向树中插入新的节点。实现这个方法的算法如下：

  1. 如果跟节点为null,则把根节点设置为要插入的节点

  2. 如果待插入节点保存的数据小于当前节点，则获取当前节点的左节点，如果左节点存在则与待插入的节点进行比较，重复步骤2。如果当前节点的左节点不存在，则直接把待插入的节点设置为当前节点的左节点

  3. 如果待插入节点保存的数据大于当前节点，则获取当前节点的右节点，如果右节点存在则与待插入的节点进行比较，重复步骤2。如果当前节点的右节点不存在，则直接把待插入的节点设置为当前节点的右节点

实现二叉树

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
class BST {
  constructor() {
    this.root = null
  }
  insert(data) {
    let n = new Node(data, null, null)
    if (this.root === null) {
      this.root = n
    } else {
      var current = this.root
      while (true) {
        if (n.data < current.data) {
          if (current.left === null) {
            current.left = n
            break
          }
          current = current.left
        } else {
          if (current.right === null) {
            current.right = n
            break
          }
          current = current.right
        }
      }
    }

  }
}

*验证二叉树

1
2
3
4
5
6
7
8
9
10
11
let bst = new BST()
bst.insert(8)
bst.insert(3)
bst.insert(6)
bst.insert(4)
bst.insert(9)
bst.insert(11)
bst.insert(2)
bst.insert(5)
bst.insert(7)
console.log('bst:',bst)

真实的打印结果很难显示在博客里，画成图的话如下：

二叉树图

实现是正确的，说明我们的二叉树程序没有问题

7.4 二叉树的遍历

二叉树遍历常用的有以下三种。

  • 前序遍历：先访问根->遍历左子树->遍历右子树
  • 中序遍历：遍历左子树->访问根->遍历右子树
  • 后序遍历：遍历左子树->遍历右子树->访问根

遍历的前中后顺序其实是指访问根节点的顺序

前序遍历：

1
2
3
4
5
6
7
8
// 前序遍历
preOrder(node) {
  if (node != null) {
    console.log(node.data)
    this.preOrder(node.left)
    this.preOrder(node.right)
  }
}

中序遍历：

1
2
3
4
5
6
7
8
// 中序遍历
inOrder(node) {
  if (node != null) {
    this.inOrder(node.left)
    console.log(node.data)
    this.inOrder(node.right)
  }
}

后序遍历

1
2
3
4
5
6
7
8
// 后序遍历
postOrder(node) {
  if (node !== null) {
    this.postOrder(node.left)
    this.postOrder(node.right)
    console.log(node.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
class Node {
  constructor(data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }

}

class BST {
  constructor() {
    this.root = null
  }
  insert(data) {
    let n = new Node(data, null, null)
    if (this.root === null) {
      this.root = n
    } else {
      var current = this.root
      while (true) {
        if (n.data < current.data) {
          if (current.left === null) {
            current.left = n
            break
          }
          current = current.left
        } else {
          if (current.right === null) {
            current.right = n
            break
          }
          current = current.right
        }
      }
    }

  }
  // 前序遍历
  preOrder(node) {
    if (node != null) {
      console.log(node.data)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }
  // 中序遍历
  inOrder(node) {
    if (node != null) {
      this.inOrder(node.left)
      console.log(node.data)
      this.inOrder(node.right)
    }
  }
  // 后序遍历
  postOrder(node) {
    if (node !== null) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node.data)
    }
  }
}

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let bst = new BST()
bst.insert(8)
bst.insert(3)
bst.insert(6)
bst.insert(4)
bst.insert(9)
bst.insert(11)
bst.insert(2)
bst.insert(5)
bst.insert(7)

bst.preOrder(bst.root) // 8 3 2 6 4 5 7 9 11

bst.inOrder(bst.root) // 2 3 4 5 6 7 8 9 11

bst.postOrder(bst.root) // 2 5 4 7 6 3 11 9 8

测试没有，说明我们的遍历是正确的。

7.5 二叉树查找

  • 查找给定的值
  • 查找最大值
  • 查找最小值
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
// 查找最大是
getMax() {
  let node = this.root
  while (true) {
    if (node.right === null) {
      console.log(node.data)
      break
    }
    node = node.right
  }
}
// 查找最小值
getMin() {
  let node = this.root
  while (true) {
    if (node.left === null) {
      console.log(node.data)
      break
    }
    node = node.left
  }
}
getSomeNum(num) {
  let node = this.root
  while (node) {
    if (num < node.data) {
      node = node.left
    } else if (num > node.data) {
      node = node.right
    } else if (num === node.data) {
      console.log('node.data:', node.data)
      break
    }
  }
}

测试

1
2
3
4
bst.getMax() // 11
bst.getMin() // 2
bst.getSomeNum(9) // node.data: 9
bst.getSomeNum(1) //

7.6 从二叉树上删除节点

在二叉树上删除节点会比较复杂，如果要删除的节点没有子节点还好，如果要删除的节点有一个节点或者两个节点，都要考虑到这些节点的处理情况，这时就比较难以处理。

  • 如果待删除节点是叶子节点（没有子节点的节点），那么只需要将从父节点指向它的链接改为 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
getSmallest(ndoe) {
  while (node.left !== null) {
    node = node.left
  }
  return node
}
remove(data) {
  root = removeNode(this.root, data)
}
// 如果要删除的节点是当前节点，则返回null，否则返回原节点，并按照规则，递归查找下一个节点是不是目标节点
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 = this.getSmallest(node.right)
    node.data = tempNode.data
    node.right = removeNode(node.right, 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
  }
}

测试

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
class Node {
  constructor(data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }

}

class BST {
  constructor() {
    this.root = null
  }
  insert(data) {
    let n = new Node(data, null, null)
    if (this.root === null) {
      this.root = n
    } else {
      var current = this.root
      while (true) {
        if (n.data < current.data) {
          if (current.left === null) {
            current.left = n
            break
          }
          current = current.left
        } else {
          if (current.right === null) {
            current.right = n
            break
          }
          current = current.right
        }
      }
    }

  }
  // 前序遍历
  preOrder(node) {
    if (node != null) {
      console.log(node.data)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }
  // 中序遍历
  inOrder(node) {
    if (node != null) {
      this.inOrder(node.left)
      console.log(node.data)
      this.inOrder(node.right)
    }
  }
  // 后序遍历
  postOrder(node) {
    if (node !== null) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node.data)
    }
  }
  // 查找最大是
  getMax() {
    let node = this.root
    while (true) {
      if (node.right === null) {
        console.log(node.data)
        break
      }
      node = node.right
    }
  }
  // 查找最小值
  getMin() {
    let node = this.root
    while (true) {
      if (node.left === null) {
        console.log(node.data)
        break
      }
      node = node.left
    }
  }
  getSomeNum(num) {
    let node = this.root
    while (node) {
      if (num < node.data) {
        node = node.left
      } else if (num > node.data) {
        node = node.right
      } else if (num === node.data) {
        console.log('node.data:', node.data)
        break
      }
    }
  }
  getSmallest(ndoe) {
    while (node.left !== null) {
      node = node.left
    }
    return node
  }
  remove(data) {
    this.root = this.removeNode(this.root, data)
  }
  // 如果要删除的节点是当前节点，则返回null，否则返回原节点，并按照规则，递归查找下一个节点是不是目标节点
  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 = this.getSmallest(node.right)
      node.data = tempNode.data
      node.right = this.removeNode(node.right, tempNode.data)
      return node
    } else if (data < node.data) {
      node.left = this.removeNode(node.left, data)
      return node
    } else {
      node.right = this.removeNode(node.right, data)
      return node
    }
  }
}
let bst = new BST()
bst.insert(8)
bst.insert(3)
bst.insert(6)
bst.insert(4)
bst.insert(9)
bst.insert(11)
bst.insert(2)
bst.insert(5)
bst.insert(7)

bst.remove(9)

bst.inOrder(bst.root)
// 打印结果
2
3
4
5
6
7
8
11

从打印结果看，需要删除的数据被删除了，bst能正常遍历，中序遍历顺序也正确，说明我们删除程序没有问题。自此关于二叉树的知识点就基本讲完了。有实际情况时根据实际情况再调整。

锅锅复锅锅

中国贫困人口，特别需要关爱人群，微信guo330504。