面向JavaScript入门初学者的二叉搜索树算法教程

下面是“面向JavaScript入门初学者的二叉搜索树算法教程”的完整攻略：

什么是二叉搜索树

二叉搜索树（Binary Search Tree，简称BST）是一种基于二分查找的数据结构，它满足下列性质：

左子树上所有结点的值均小于它的根结点的值；
右子树上所有结点的值均大于它的根结点的值；
左右子树也分别为BST；
没有重复的结点。

二叉搜索树的插入操作

二叉搜索树的插入操作分为两步：

在树中找到一个结点 p，使得新结点 n 的值要么等于 p 的值（即插入的结点值已经在树中已经存在），要么可以插入到 p 的左子树或者右子树中；
插入结点 n。

以下是JavaScript的插入操作的代码实现：

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

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

  insert(val) {
    if (!this.root) {
      this.root = new TreeNode(val);
      return;
    }

    let curr = this.root;
    while (true) {
      if (val < curr.val) {
        if (!curr.left) {
          curr.left = new TreeNode(val);
          break;
        }
        curr = curr.left;
      } else if (val > curr.val) {
        if (!curr.right) {
          curr.right = new TreeNode(val);
          break;
        }
        curr = curr.right;
      } else {
        break; // val 已经存在于树中
      }
    }
  }
}

二叉搜索树的查找操作

二叉搜索树的查找操作也很简单，从根结点开始沿着左右子树不断搜索，直到找到目标结点或者空结点。

以下是JavaScript实现的查找操作代码：

class BST {
  // ...

  find(val) {
    let curr = this.root;
    while (curr) {
      if (val < curr.val) {
        curr = curr.left;
      } else if (val > curr.val) {
        curr = curr.right;
      } else {
        return curr;
      }
    }
    return null;
  }
}

示例说明

示例一：插入操作

假设我们要向一颗空的二叉搜索树中插入以下结点：[5, 4, 3, 1, 7, 6, 10, 8]。将这些结点插入树中后，我们可以通过中序遍历来验证这颗树是不是一颗BST。

const bst = new BST();
[5, 4, 3, 1, 7, 6, 10, 8].forEach(num => bst.insert(num));
console.log(bst);

输出结果：

BST {
  root: TreeNode {
    val: 5,
    left: TreeNode {
      val: 4,
      left: TreeNode { val: 3, left: TreeNode { val: 1, left: null, right: null }, right: null },
      right: null
    },
    right: TreeNode {
      val: 7,
      left: TreeNode { val: 6, left: null, right: null },
      right: TreeNode { val: 10, left: TreeNode { val: 8, left: null, right: null }, right: null }
    }
  }
}

中序遍历结果：[1, 3, 4, 5, 6, 7, 8, 10]，符合BST的性质。

示例二：查找操作

假设我们要查找上面示例一中二叉搜索树中值为6的结点。

const node = bst.find(6);
console.log(node.val); // 6