在计算机科学中，二叉搜索树（BST）是一种常用的数据结构，可提供高效的搜索、插入和删除操作。在本文中，我们将探讨如何使用 JavaScript 实现二叉搜索树。我们将讨论 BST 背后的概念，提供实现的分步说明，并通过代码示例演示 BST 类的用法。

在 JavaScript 中实现二叉搜索树

什么是二叉搜索树（BST)

二叉搜索树是一种二叉树，其中每个节点都有一个值、一个左子节点和一个右子节点。BST 的关键属性是，对于每个节点，其左侧子树中的所有值都小于节点的值，其右侧子树中的所有值都大于节点的值。此属性可实现高效的搜索、插入和删除操作。

二叉搜索树算法

要在 JavaScript 中实现二叉搜索树，我们可以创建一个带有插入、删除和搜索操作方法的 BST 类。每个操作的算法方法可以总结如下：

插入

从根节点开始。
如果要插入的值小于当前节点的值，请移动到左侧子节点。
如果左子节点为 null，则使用给定值创建一个新节点，并将其分配为左子节点。
如果要插入的值大于当前节点的值，请移动到右侧子节点。
如果正确的子节点为 null，则使用给定值创建一个新节点，并将其分配为正确的子节点。
重复上述步骤，直到插入该值。

删除
从根节点开始。
如果要删除的值小于当前节点的值，则移动到左子节点。
如果要删除的值大于当前节点的值，则移动到右子节点。
如果该值等于当前节点的值:则分3种情况

1、如果该节点没有子节点，只需删除该节点即可。
2、如果该节点只有一个子节点，则用其子节点替换该节点。
3、如果该节点有两个子节点，则找到右子树中的最小值（或左子树中的最大值），用该最小值（或最大值）替换该节点的值，并递归删除右子树（或左子树中的重复值） ) 子树。

重复上述步骤，直到该值被删除或找不到。

搜索
从根节点开始。
如果要查找的值小于当前节点的值，则移动到左子节点。
如果要查找的值大于当前节点的值，则移动到右子节点。
如果该值等于当前节点的值，则返回 true（已找到）。
如果子节点为null，则返回false（未找到）。

重复上述步骤，直到找到或没有找到该值。

JavaScript 代码实现：

二叉树定义

class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (this.root === null) {
  this.root = newNode;
} else {
  this.insertNode(this.root, newNode);
}
}
//对应插入
insertNode(node, newNode) {
if (newNode.value < node.value) {
  if (node.left === null) {
    node.left = newNode;
  } else {
    this.insertNode(node.left, newNode);
  }
} else {
  if (node.right === null) {
    node.right = newNode;
  } else {
    this.insertNode(node.right, newNode);
  }
}
}
delete(value) {
this.root = this.deleteNode(this.root, value);
}
//对应删除
deleteNode(node, value) {
if (node === null) {
  return null;
} else if (value < node.value) {
  node.left = this.deleteNode(node.left, value);
} else if (value > node.value) {
  node.right = this.deleteNode(node.right, value);
} else {
  if (node.left === null && node.right === null) {
    node = null;
  } else if (node.left === null) {
    node = node.right;
  } else if (node.right === null) {
    node = node.left;
  } else {
    const minValue = this.findMinValue(node.right);
    node.value = minValue;
    node.right = this.deleteNode(node.right, minValue);
  }
}
return node;
}
findMinValue(node) {
if (node.left === null) {
  return node.value;
}
return this.findMinValue(node.left);
}
search(value) {
return this.searchNode(this.root, value);
}
//对应搜索
searchNode(node, value) {
if (node === null) {
  return false;
} else if (value < node.value) {
  return this.searchNode(node.left, value);
} else if (value > node.value) {
  return this.searchNode(node.right, value);
} else {
  return true;
}
}
}

使用示例：

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(7);
bst.insert(12);
console.log(bst.search(7)); // Output: true
console.log(bst.search(20)); // Output: false
bst.delete(5);
console.log(bst.search(5)); // Output: false

代码解析：
在上面的代码中，我们首先定义一个 Node 类来表示二叉搜索树中的一个节点。每个节点都有一个值、一个左子节点和一个右子节点。
然后，我们定义 BinarySearchTree 类，它具有表示树的根节点的 root 属性。该类包含插入、删除和搜索操作的方法。
insert 方法将一个新节点插入到树中。如果树为空，则新节点成为根。否则，递归调用 insertNode 方法，根据新节点的值找到新节点的适当位置。
delete 方法从树中删除具有给定值的节点。递归调用 deleteNode 方法来执行删除。它处理要删除的节点没有子节点、一个子节点或两个子节点的情况。
search 方法检查树中是否存在具有给定值的节点。它递归地调用 searchNode 方法来遍历树，如果找到值则返回 true。
我们通过一个示例演示了 BST 类的用法。我们创建 BinarySearchTree 类的新实例，插入一些值，并对树执行搜索和删除操作。

总结

在 JavaScript 中实现二叉搜索树使我们能够以排序的方式有效地存储和检索数据。在本文中，我们探讨了 BST 背后的概念，并逐步说明了如何在 JavaScript 中实现 BST 类。我们介绍了插入、删除和搜索操作，以及它们各自的算法和代码示例。通过理解和实现 BST，您可以在需要高效搜索、排序和检索数据的各种应用程序中利用其优势。

在 JavaScript 中实现二叉搜索树

什么是二叉搜索树（BST)

二叉搜索树算法

插入

删除

搜索

JavaScript 代码实现：

总结

公众号

归档