二叉搜索树

发表于 分类于

二叉搜索树（Binary Search Tree）

二叉树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。支持对数据的快速查找、插入和删除操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @description: 二叉搜索树节点
 * @param {*} val
 * @param {*} left
 * @param {*} right
 * @return {*}
 */
function BSTNode (val = 0, left = null, right = null) {
  this.val = val
  this.left = left
  this.right = right
}
/**
 * @description: 二叉搜索树
 * @param {*} root
 * @return {*}
 */
function BinarySearchTree (root = null) {
  this.root = root
}
查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @description: 查找数据是否存在二叉搜索树中
 * @param {*} val
 * @return {*}
 */
BinarySearchTree.prototype.search = function (root, val) {
  if (!root) {
    return false
  }
  if (val === root.val) {
    return true
  } else if (val < root.val) {
    return this.search(root.left, val)
  } else {
    return this.search(root.right, val)
  }
}
插入
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
/**
 * @description: 在二叉树中插入节点
 * @param {*} root
 * @param {*} val
 * @return {*}
 */
BinarySearchTree.prototype.insert = function (root, val) {
  if (!root) {
    return new BSTNode(val)
  }

  if (val < root.val) {
    if (root.left === null) {
      root.left = new BSTNode(val)
    } else {
      this.insert(root.left, val)
    }
  } else if (val > root.val) {
    if (root.right === null) {
      root.right = new BSTNode(val)
    } else {
      this.insert(root.right, val)
    }
  }

  return root
}
删除
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
/**
 * @description: 删除二叉树中的节点
 * @param {*} root
 * @param {*} val
 * @return {*}
 */
BinarySearchTree.prototype.delete = function (root, val) {
  const getMinNode = (cur) => {
    while (cur.left !== null) {
      cur = cur.left
    }
    return cur
  }

  if (!root) {
    return null
  }

  if (root.val === val) {
    if (!root.left) {
      root = root.right
    } else if (!root.right) {
      root = root.left
    } else {
      // 如果左子树和右子树同时不为空，则用右子树的最小节点覆盖要删除的节点
      // 然后再将右子树的最小节点删除
      let minNode = getMinNode(root.right)
      root.val = minNode.val
      root.right = this.delete(root.right, minNode.val)
    }
  } else if (root.val < val) {
    root.right = this.delete(root.right, val)
  } else {
    root.left = this.delete(root.left, val)
  }
  return root
}