从 JavaScript 数组构建二叉搜索树

使用递归构建二叉搜索树

该解决方案使用 JavaScript 中的递归方法从数组构建二叉搜索树。

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  buildTree(nums) {
    if (nums.length === 0) return null;
    let mid = Math.floor(nums.length / 2);
    let node = new Node(nums[mid]);
    node.left = this.buildTree(nums.slice(0, mid));
    node.right = this.buildTree(nums.slice(mid + 1));
    return node;
  }
}
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree();
bst.root = bst.buildTree(nums);
console.log(bst.root);

使用迭代和队列的二叉搜索树

该解决方案使用队列的迭代方法构建二叉搜索树。

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  buildTree(nums) {
    if (nums.length === 0) return null;
    let mid = Math.floor(nums.length / 2);
    this.root = new Node(nums[mid]);
    let queue = [{ node: this.root, range: nums }];
    while (queue.length) {
      let { node, range } = queue.shift();
      let midIndex = Math.floor(range.length / 2);
      let leftSide = range.slice(0, midIndex);
      let rightSide = range.slice(midIndex + 1);
      if (leftSide.length) {
        node.left = new Node(leftSide[Math.floor(leftSide.length / 2)]);
        queue.push({ node: node.left, range: leftSide });
      }
      if (rightSide.length) {
        node.right = new Node(rightSide[Math.floor(rightSide.length / 2)]);
        queue.push({ node: node.right, range: rightSide });
      }
    }
  }
}
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree();
bst.buildTree(nums);
console.log(bst.root);

具有错误处理和输入验证的平衡二叉搜索树

该解决方案通过输入验证和优化的错误处理改进了递归方法。

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  buildTree(nums) {
    if (!Array.isArray(nums) || nums.length === 0) {
      throw new Error("Invalid input: nums must be a non-empty array.");
    }
    return this._buildRecursive(nums);
  }
  _buildRecursive(nums) {
    if (nums.length === 0) return null;
    let mid = Math.floor(nums.length / 2);
    let node = new Node(nums[mid]);
    node.left = this._buildRecursive(nums.slice(0, mid));
    node.right = this._buildRecursive(nums.slice(mid + 1));
    return node;
  }
}
try {
  const nums = [1, 2, 3, 4, 5, 6, 7];
  const bst = new BinarySearchTree();
  bst.root = bst.buildTree(nums);
  console.log(bst.root);
} catch (error) {
  console.error(error.message);
}

在 JavaScript 中构建二叉搜索树的常见问题

1. 递归如何帮助构建 BST？
2. 递归将数组划分为更小的子数组，并将中间元素指定为根，重复该过程直到放置所有元素。
3. 如何处理二叉搜索树中的重复值？
4. 您可以将重复项一致地放置在左子树或右子树中。这确保了 BST 属性得以维持。
5. 有何重要性 Math.floor() 在BST建设中？
6. Math.floor() 帮助确定数组的中间元素，该元素成为子树的根。
7. 为什么树平衡在 BST 中很重要？
8. 平衡可以防止树变得倾斜，确保搜索、插入和删除等操作花费 O(log n) 时间。
9. 怎么可以 slice() 改善树木结构？
10. slice() 用于将数组拆分为左子数组和右子数组，从而允许递归构造树的子树。
11. 输入验证应该检查什么？
12. 检查输入是否是有效的、已排序的数组。这确保了可以正确地构建树而不会出现错误。
13. 错误处理在 BST 构建中扮演什么角色？
14. 错误处理，例如使用 throw new Error()，有助于及早发现问题并防止应用程序崩溃。
15. 为什么选择迭代方法而不是递归？
16. 迭代，使用 queue，避免了递归深度的潜在问题，特别是在可能发生堆栈溢出的大型数据集中。
17. AVL和红黑树如何保持平衡？
18. 这些算法在每次插入或删除后自动重新平衡树，以确保对数搜索时间。
19. 选择中间元素作为根有什么意义呢？
20. 选择中间元素可确保树保持平衡，从而防止低效的搜索路径。

关于二叉搜索树的最终想法

从数组构建二叉搜索树涉及将数组拆分为子数组并将中间元素指定为根。此过程有助于维持高效且平衡的树结构。平衡树对于确保快速搜索、插入和删除操作至关重要。

通过使用递归和迭代方法，您可以确保实现的灵活性。实现错误处理和输入验证是防止运行时错误的关键。这些策略成功开发了既实用又可靠的二叉搜索树。