JavaScript数据结构 - 二叉搜索树

定义

二叉搜索树是一种数据结构，由一组有序的链接节点表示层次结构树。每个节点通过父子关系与其他节点相连。任何给定的节点最多可以有两个子节点（左子节点和右子节点）。二叉搜索树中的第一个节点是根节点，而没有任何子节点的节点是叶子节点。二叉搜索树的组织方式是，对于任何给定的节点，其左子树中的所有节点的键值小于该节点的键值，而其右子树中的所有节点的键值大于该节点的键值。

二叉搜索树数据结构中的每个节点必须具有以下属性：

key：节点的键值
value：节点的值
parent：节点的父节点（如果没有则为null）
left：指向节点的左子节点的指针（如果没有则为null）
right：指向节点的右子节点的指针（如果没有则为null）

二叉搜索树数据结构的主要操作包括：

insert：将一个节点插入到给定父节点的子节点中
remove：从二叉搜索树中删除一个节点及其子节点
has：检查给定节点是否存在
find：检索给定节点
preOrderTraversal：通过递归遍历每个节点及其子节点来遍历二叉搜索树
postOrderTraversal：通过递归遍历每个节点的子节点，然后是节点本身来遍历二叉搜索树
inOrderTraversal：通过递归遍历每个节点的左子节点，然后是节点本身，然后是其右子节点来遍历二叉搜索树

实现

class BinarySearchTreeNode {
  constructor(key, value = key, parent = null) {
    this.key = key;
    this.value = value;
    this.parent = parent;
    this.left = null;
    this.right = null;
  }

```javascript
class BinarySearchTreeNode {
  get isLeaf() {
    return this.left === null && this.right === null;
  }

  get hasChildren() {
    return !this.isLeaf;
  }
}

class BinarySearchTree {
  constructor(key, value = key) {
    this.root = new BinarySearchTreeNode(key, value);
  }

  *inOrderTraversal(node = this.root) {
    if (node.left) yield* this.inOrderTraversal(node.left);
    yield node;
    if (node.right) yield* this.inOrderTraversal(node.right);
  }

  *postOrderTraversal(node = this.root) {
    if (node.left) yield* this.postOrderTraversal(node.left);
    if (node.right) yield* this.postOrderTraversal(node.right);
    yield node;
  }

  *preOrderTraversal(node = this.root) {
    yield node;
    if (node.left) yield* this.preOrderTraversal(node.left);
    if (node.right) yield* this.preOrderTraversal(node.right);
  }

  insert(key, value = key) {
    let node = this.root;
    while (true) {
      if (node.key === key) return false;
      if (node.key > key) {
        if (node.left !== null) node = node.left;
        else {
          node.left = new BinarySearchTreeNode(key, value, node);
          return true;
        }
      } else if (node.key < key) {
        if (node.right !== null) node = node.right;
        else {
          node.right = new BinarySearchTreeNode(key, value, node);
          return true;
        }
      }
    }
  }

  has(key) {
    for (let node of this.postOrderTraversal()) {
      if (node.key === key) return true;
    }
    return false;
  }

  find(key) {
    for (let node of this.postOrderTraversal()) {
      if (node.key === key) return node;
    }
    return undefined;
  }

  remove(key) {
    const node = this.find(key);
    if (!node) return false;
    const isRoot = node.parent === null;
    const isLeftChild = !isRoot ? node.parent.left === node : false;
    const hasBothChildren = node.left !== null && node.right !== null;

if (node.isLeaf) {
  if (!isRoot) {
    if (isLeftChild) node.parent.left = null;
    else node.parent.right = null;
  } else {
    this.root = null;
  }
  return true;
} else if (!hasBothChildren) {
  const child = node.left !== null ? node.left : node.right;
  if (!isRoot) {
    if (isLeftChild) node.parent.left = child;
    else node.parent.right = child;
  } else {
    this.root = child;
  }
  child.parent = node.parent;
  return true;
} else {
  const rightmostLeft = [...this.inOrderTraversal(node.left)].slice(-1)[0];
  rightmostLeft.parent = node.parent;
  if (!isRoot) {
    if (isLeftChild) node.parent.left = rightmostLeft;
    else node.parent.right = rightmostLeft;
  } else {
    this.root = rightmostLeft;
  }
  rightmostLeft.right = node.right;
  node.right.parent = rightmostLeft;
  return true;
}
}

创建一个BinarySearchTreeNode的class，其中包含一个初始化适当的key、value、parent、left和right属性的constructor。
定义一个isLeaf的getter，使用Array.prototype.length来检查left和right是否都为空。
定义一个hasChildren的getter，它是isLeaf的反义词。
创建一个BinarySearchTree的class，其中包含一个初始化二叉搜索树的root的constructor。
定义一个preOrderTraversal()的生成器方法，它以前序遍历的方式遍历二叉搜索树，使用yield*语法将遍历递归委托给自身。
定义一个postOrderTraversal()的生成器方法，它以后序遍历的方式遍历二叉搜索树，使用yield*语法将遍历递归委托给自身。
定义一个inOrderTraversal()的生成器方法，它以中序遍历的方式遍历二叉搜索树，使用yield*语法将遍历递归委托给自身。
定义一个insert()方法，它使用while循环来搜索二叉搜索树，通过移动每个节点的子节点，直到找到适当的位置来插入一个新的子节点BinarySearchTreeNode，无论是作为left还是right子节点，取决于给定的key。
定义一个has()方法，它使用preOrderTraversal()方法来检查给定的节点是否存在于二叉搜索树中。
定义一个find()方法，它使用preOrderTraversal()方法来检索二叉搜索树中的给定节点。
定义一个remove()方法，它从二叉搜索树中删除给定的BinarySearchTreeNode，删除与之相关的任何链接，并更新二叉搜索树以保持其顺序。

```js const tree = new BinarySearchTree(30);

tree.insert(10); tree.insert(15); tree.insert(12); tree.insert(40); tree.insert(35); tree.insert(50);

[...tree.preOrderTraversal()].map(x => x.value); // [30, 10, 15, 12, 40, 35, 50]

[...tree.inOrderTraversal()].map(x => x.value); // [10, 12, 15, 30, 35, 40, 50]

[...tree.postOrderTraversal()].map(x => x.value); // [12, 15, 10, 35, 50, 40, 30]

tree.root.value; // 30 tree.root.hasChildren; // true

tree.find(12).isLeaf; // true tree.find(40).isLeaf; // false tree.find(50).parent.value; // 40 tree.find(15).left.value; // 12 tree.find(12).right; // null

tree.remove(12);

[...tree.preOrderTraversal()].map(x => x.value); // [30, 10, 15, 40, 35, 50]

tree.remove(10);

[...tree.preOrderTraversal()].map(v => ({ key: v.key, parent: v.parent ? v.parent.key : null, })); // [30, 15, 40, 35, 50]

tree.remove(40);

[...tree.preOrderTraversal()].map(x => x.value); // [30, 15, 40, 35, 50]

tree.remove(30);

[...tree.preOrderTraversal()].map(x => x.value); // [15, 35, 50]