JavaScript数据结构 - 二叉树

定义

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

JavaScript二叉树可视化

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

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

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

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

实现

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

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

  get isLeaf() {
    return this.left === null && this.right === null;
  }

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

class BinaryTree {
  constructor(key, value = key) {
    this.root = new BinaryTreeNode(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(
    parentNodeKey,
    key,
    value = key,
    { left, right } = { left: true, right: true }
  ) {
    for (let node of this.preOrderTraversal()) {
      if (node.key === parentNodeKey) {
        const canInsertLeft = left && node.left === null;
        const canInsertRight = right && node.right === null;
        if (!canInsertLeft && !canInsertRight) return false;
        if (canInsertLeft) {
          node.left = new BinaryTreeNode(key, value, node);
          return true;
        }
        if (canInsertRight) {
          node.right = new BinaryTreeNode(key, value, node);
          return true;
        }
      }
    }
    return false;
  }

  remove(key) {
    for (let node of this.preOrderTraversal()) {
      if (node.left && node.left.key === key) {
        node.left = null;
        return true;
      }
      if (node.right && node.right.key === key) {
        node.right = null;
        return true;
      }
    }
    return false;
  }

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

创建一个BinaryTreeNode类，其中包含一个constructor方法，用于初始化key、value、parent、left和right属性。
定义一个isLeaf的getter方法，使用Array.prototype.length来检查left和right是否都为空。
定义一个hasChildren的getter方法，它是isLeaf的相反值。
创建一个BinaryTree类，其中包含一个constructor方法，用于初始化二叉树的root。
定义一个preOrderTraversal()的生成器方法，以前序遍历的方式遍历二叉树，使用yield*语法将遍历委托给自身进行递归遍历。
定义一个postOrderTraversal()的生成器方法，以后序遍历的方式遍历二叉树，使用yield*语法将遍历委托给自身进行递归遍历。
定义一个inOrderTraversal()的生成器方法，以中序遍历的方式遍历二叉树，使用yield*语法将遍历委托给自身进行递归遍历。
定义一个insert()方法，使用preOrderTraversal()方法找到给定的父节点，并根据传入的选项对象，在left或right子节点位置插入一个新的BinaryTreeNode。
定义一个remove()方法，使用preOrderTraversal()方法和Array.prototype.filter()方法从二叉树中删除一个BinaryTreeNode。
定义一个find()方法，使用preOrderTraversal()方法在二叉树中查找给定的节点。

const tree = new BinaryTree(1, 'AB');

tree.insert(1, 11, 'AC');
tree.insert(1, 12, 'BC');
tree.insert(12, 121, 'BG', { right: true });

[...tree.preOrderTraversal()].map(x => x.value);
// ['AB', 'AC', 'BC', 'BCG']

[...tree.inOrderTraversal()].map(x => x.value);
// ['AC', 'AB', 'BC', 'BG']

tree.root.value;                // 'AB'
tree.root.hasChildren;          // true

tree.find(12).isLeaf;           // false
tree.find(121).isLeaf;          // true
tree.find(121).parent.value;    // 'BC'
tree.find(12).left;             // null
tree.find(12).right.value;      // 'BG'

tree.remove(12);

[...tree.postOrderTraversal()].map(x => x.value);
// ['AC', 'AB']