JavaScript二叉搜索树构建操作详解

什么是二叉搜索树？

二叉搜索树（Binary Search Tree，简称BST）是一种二叉树，它满足以下限制：

• 对于每个节点，它的左子树中所有节点的值都小于这个节点的值；
• 对于每个节点，它的右子树中所有节点的值都大于这个节点的值；
• 左右子树都是二叉搜索树。

如何构建二叉搜索树？

遍历一棵空树时，我们首先得想到的是如何构建这棵树。接下来介绍三种不同的方法：

方法一：插入操作

从空的二叉搜索树开始，进行插入操作，对于每个节点，它会根据它的值和根节点的比较结果，决定到左子树或右子树中去查找下一个节点，直到找到一个空节点。然后，我们把新节点插入到这个空节点的位置上。

在代码实现中，我们需要创建 Node 类和 BinarySearchTree 类。Node 类表示二叉搜索树中的每个节点，它有 value、leftChild 和 rightChild 三个属性。BinarySearchTree 类用于创建二叉搜索树，它有 root 属性指向二叉搜索树的根节点，以及 insert 方法用于插入一个节点。

class Node {
  constructor(value) {
    this.value = value;
    this.leftChild = null;
    this.rightChild = null;
  }
}

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

  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
    } else {
      let currentNode = this.root;
      while (true) {
        if (value < currentNode.value) {
          if (!currentNode.leftChild) {
            currentNode.leftChild = newNode;
            break;
          }
          currentNode = currentNode.leftChild;
        } else {
          if (!currentNode.rightChild) {
            currentNode.rightChild = newNode;
            break;
          }
          currentNode = currentNode.rightChild;
        }
      }
    }
  }
}

const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

方法二：数组转二叉搜索树

我们也可以用一个已经有序的数组来构建二叉搜索树。在这种情况下，每个节点的值都是数组的中位数。然后我们把数组分成两半，分别用这两半的数来构建左子树和右子树。对于子树，我们采用递归的方式来构建。

function buildBSTFromArray(array) {
  if (array.length === 0) {
    return null;
  } else if (array.length === 1) {
    return new Node(array[0]);
  } else {
    const middleIndex = Math.floor(array.length / 2);
    const rootNode = new Node(array[middleIndex]);
    rootNode.leftChild = buildBSTFromArray(array.slice(0, middleIndex));
    rootNode.rightChild = buildBSTFromArray(array.slice(middleIndex + 1));
    return rootNode;
  }
}

const array = [3, 6, 8, 10, 15, 20];
const tree = new BinarySearchTree();
tree.root = buildBSTFromArray(array);

方法三：前序遍历和中序遍历

我们已经知道，对于二叉搜索树，每个节点的值都大于它左子树中所有节点的值，且小于它右子树中所有节点的值。所以前序遍历中的第一个节点就是二叉搜索树的根节点，而中序遍历中根节点的左侧都是左子树的节点值，右侧都是右子树的节点值。

我们可以根据这两个遍历结果，来构建一棵二叉搜索树。具体来说，我们首先取出前序遍历中的第一个节点作为根节点。然后，在中序遍历中找到这个节点，根据它左侧和右侧的节点，分别递归构建左子树和右子树。

function buildBST(preorder, inorder) {
  if (preorder.length === 0 || inorder.length === 0) {
    return null;
  }
  const rootValue = preorder[0];
  const rootNode = new Node(rootValue);
  const rootIndex = inorder.indexOf(rootValue);
  rootNode.leftChild = buildBST(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex));
  rootNode.rightChild = buildBST(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1));
  return rootNode;
}

const preorder = [10, 6, 3, 8, 15, 20];
const inorder = [3, 6, 8, 10, 15, 20];
const tree = new BinarySearchTree();
tree.root = buildBST(preorder, inorder);

示例说明

示例一：插入操作

以向一个空的二叉搜索树中依次插入节点 10、6、15、3、8 和 20 为例：

const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

这段代码的输出为：

BinarySearchTree {
  root: Node {
    value: 10,
    leftChild: Node { value: 6, leftChild: [Node], rightChild: [Node] },
    rightChild: Node { value: 15, leftChild: null, rightChild: [Node] }
  }
}

示例二：前序遍历和中序遍历

以前序遍历数组 [10, 6, 3, 8, 15, 20] 和中序遍历数组 [3, 6, 8, 10, 15, 20] 来构建二叉搜索树为例：

const preorder = [10, 6, 3, 8, 15, 20];
const inorder = [3, 6, 8, 10, 15, 20];
const tree = new BinarySearchTree();
tree.root = buildBST(preorder, inorder);

这段代码的输出为：

BinarySearchTree {
  root: Node {
    value: 10,
    leftChild: Node {
      value: 6,
      leftChild: Node { value: 3, leftChild: null, rightChild: [Node] },
      rightChild: Node { value: 8, leftChild: null, rightChild: null }
    },
    rightChild: Node {
      value: 15,
      leftChild: null,
      rightChild: Node { value: 20, leftChild: null, rightChild: null }
    }
  }
}

总结

二叉搜索树是一种非常重要的数据结构，在工程实践中广泛应用。我们可以采用插入操作、数组转二叉搜索树、前序遍历和中序遍历等多种方式来构建二叉搜索树。需要注意的是，在构建过程中，我们需要保证树满足二叉搜索树的限制。