JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法示例

JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法示例

二叉树简介

二叉树是一种非常重要的数据结构，它可以给我们提供高效的算法实现，如查找、插入、删除等。二叉树是由节点（node）构成的，每个节点最多只有两个子节点。在 JavaScript 中，我们可以用对象的形式来表示一个二叉树节点，如下：

class Node {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

上面的代码中，我们定义了一个 Node 类，它有一个 value 属性，以及 left 和 right 两个子节点。

查找最小值、最大值、给定值

在二叉搜索树（BST）中，每个节点的值都大于其左子树中的任意节点的值，而小于其右子树中的任意节点的值。因此，在 BST 中，查找最小值时只需要访问树的最左侧节点即可，查找最大值时只需要访问树的最右侧节点即可。

以下是查找最小值、最大值、给定值的代码实现：

class BinarySearchTree {
  constructor() {
    this.root = null
  }

  // 插入节点
  insert(value) {
    let node = new Node(value)

    if (this.root === null) {
      this.root = node
    } else {
      this._insert(node, this.root)
    }
  }

  _insert(node, current) {
    if (node.value < current.value) {
      if (current.left === null) {
        current.left = node
      } else {
        this._insert(node, current.left)
      }
    } else {
      if (current.right === null) {
        current.right = node
      } else {
        this._insert(node, current.right)
      }
    }
  }

  // 查找最小值
  findMin() {
    if (this.root === null) {
      return null
    }

    let current = this.root
    while (current.left !== null) {
      current = current.left
    }

    return current.value
  }

  // 查找最大值
  findMax() {
    if (this.root === null) {
      return null
    }

    let current = this.root
    while (current.right !== null) {
      current = current.right
    }

    return current.value
  }

  // 查找给定值
  find(value) {
    if (this.root === null) {
      return false
    }

    let current = this.root
    while (current !== null) {
      if (value === current.value) {
        return true
      } else if (value < current.value) {
        current = current.left
      } else {
        current = current.right
      }
    }

    return false
  }
}

示例说明

示例 1：查找最小值和最大值

以下为示例序列，我们将其构建成一颗二叉搜索树。

          10
       /      \
      6        14
     / \      /  \
    4   8   12    16

查找最小值:

let bst = new BinarySearchTree()
bst.insert(10)
bst.insert(6)
bst.insert(14)
bst.insert(4)
bst.insert(8)
bst.insert(12)
bst.insert(16)

console.log(bst.findMin()) // 4

查找最大值：

let bst = new BinarySearchTree()
bst.insert(10)
bst.insert(6)
bst.insert(14)
bst.insert(4)
bst.insert(8)
bst.insert(12)
bst.insert(16)

console.log(bst.findMax()) // 16

示例 2：查找给定值

以下为示例序列，我们将其构建成一颗二叉搜索树。

          10
       /      \
      6        14
     / \      /  \
    4   8   12    16

查找给定值 12：

let bst = new BinarySearchTree()
bst.insert(10)
bst.insert(6)
bst.insert(14)
bst.insert(4)
bst.insert(8)
bst.insert(12)
bst.insert(16)

console.log(bst.find(12)) // true

以上即是关于二叉树实现查找最小值、最大值、给定值算法的完整攻略。