JavaScript实现二叉搜索树

让我来详细地讲解一下"JavaScript实现二叉搜索树"的攻略。

什么是二叉搜索树

二叉搜索树是一种树型数据结构，其中每个节点最多有两个子节点，且满足以下性质：

• 左子节点上所有的值都小于该节点的值。
• 右子节点上所有的值都大于该节点的值。

JavaScript 实现二叉搜索树

1. 创建二叉搜索树节点的类

我们可以用 JavaScript 类的方式来创建二叉搜索树。首先我们需要创建节点类：

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

该类包含了一个存储数据的 data 属性，和两个指向左子节点和右子节点的属性 left 和 right。

2. 创建二叉搜索树类

接下来，在 BinarySearchTree 类中添加节点和其它操作：

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

  insert(data) {
    const node = new Node(data)

    if (!this.root) {
      this.root = node
      return
    }

    let current = this.root

    while (true) {

      if (data < current.data) {

        if (!current.left) {
          current.left = node
          break
        } else {
          current = current.left
        }

      } else if (data > current.data) {

        if (!current.right) {
          current.right = node
          break
        } else {
          current = current.right
        }

      } else {

        break

      }

    }
  }

  search(data) {
    let current = this.root

    while (current) {

      if (data === current.data) {
        return true
      } else if (data < current.data) {
        current = current.left
      } else {
        current = current.right
      }

    }

    return false
  }

  inOrderPrint(callback) {
    const inOrder = (node) => {
      if (node) {
        inOrder(node.left)
        callback(node)
        inOrder(node.right)
      }
    }

    inOrder(this.root)
  }

  preOrderPrint(callback) {
    const preOrder = (node) => {
      if (node) {
        callback(node)
        preOrder(node.left)
        preOrder(node.right)
      }
    }

    preOrder(this.root)
  }

  postOrderPrint(callback) {
    const postOrder = (node) => {
      if (node) {
        postOrder(node.left)
        postOrder(node.right)
        callback(node)
      }
    }

    postOrder(this.root)
  }
}

我们定义了 insert() 方法，该方法会遍历二叉搜索树的节点，寻找合适的位置插入新节点。

search() 方法会在二叉搜索树中查找给定数据的节点，如果找到则返回 true，否则返回 false。

inOrderPrint()，preOrderPrint() 和 postOrderPrint() 方法会遍历整个树，并在每个节点上执行回调函数，分别对应中序遍历、先序遍历和后序遍历。

3. 使用示例

现在我们来看两个使用二叉搜索树的例子。

第一个例子是将一组数据插入到二叉搜索树中，并使用中序遍历打印二叉搜索树的节点值：

const bst = new BinarySearchTree()

bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)
bst.insert(13)
bst.insert(17)

bst.inOrderPrint((node) => {
  console.log(node.data)
})

输出结果为：

3
5
7
10
13
15
17

第二个例子是在二叉搜索树中查找一个节点：

const bst = new BinarySearchTree()

bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)
bst.insert(13)
bst.insert(17)

console.log(bst.search(13))

输出结果为 true，表示二叉搜索树中存在一个值为 13 的节点。

至此，我们已经完成了一个 JavaScript 实现的二叉搜索树。