JavaScript数据结构 - 树

定义

树是一种由一组链接的节点组成的数据结构，表示层次结构。每个节点通过父子关系与其他节点相连。树中的第一个节点是根节点，而没有任何子节点的节点是叶子节点。

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

• key：节点的键
• value：节点的值
• parent：节点的父节点（如果没有则为null）
• children：指向节点子节点的指针数组

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

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

实现

class TreeNode {
  constructor(key, value = key, parent = null) {
    this.key = key;
    this.value = value;
    this.parent = parent;
    this.children = [];
  }

```js
class TreeNode {
  constructor(key, value = key, parent = null) {
    this.key = key;
    this.value = value;
    this.parent = parent;
    this.children = [];
  }

  get isLeaf() {
    return this.children.length === 0;
  }

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

class Tree {
  constructor(key, value = key) {
    this.root = new TreeNode(key, value);
  }

  *preOrderTraversal(node = this.root) {
    yield node;
    if (node.children.length) {
      for (let child of node.children) {
        yield* this.preOrderTraversal(child);
      }
    }
  }

  *postOrderTraversal(node = this.root) {
    if (node.children.length) {
      for (let child of node.children) {
        yield* this.postOrderTraversal(child);
      }
    }
    yield node;
  }

  insert(parentNodeKey, key, value = key) {
    for (let node of this.preOrderTraversal()) {
      if (node.key === parentNodeKey) {
        node.children.push(new TreeNode(key, value, node));
        return true;
      }
    }
    return false;
  }

  remove(key) {
    for (let node of this.preOrderTraversal()) {
      const filtered = node.children.filter(c => c.key !== key);
      if (filtered.length !== node.children.length) {
        node.children = filtered;
        return true;
      }
    }
    return false;
  }

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

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

• 创建一个TreeNode的class，其中包含一个constructor方法，用于初始化key、value、parent和children属性。
• 定义一个isLeaf的getter方法，使用Array.prototype.length来检查children是否为空。
• 定义一个hasChildren的getter方法，它是isLeaf的相反值。
• 创建一个Tree的class，其中包含一个constructor方法，用于初始化树的root。
• 定义一个preOrderTraversal()的generator方法，以前序遍历的方式遍历树，使用yield*语法将遍历委托给自身进行递归遍历。
• 定义一个postOrderTraversal()的generator方法，以后序遍历的方式遍历树，使用yield*语法将遍历委托给自身进行递归遍历。
• 定义一个insert()方法，使用preOrderTraversal()方法和Array.prototype.push()将新的TreeNode添加到树中。
• 定义一个remove()方法，使用preOrderTraversal()方法和Array.prototype.filter()从树中删除一个TreeNode。
• 定义一个find()方法，使用preOrderTraversal()方法在树中检索给定的节点。

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

tree.insert(1, 11, 'AC'); tree.insert(1, 12, 'BC'); tree.insert(12, 121, 'BG');

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

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.remove(12);

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

树插入节点1，11，'AC'； 树插入节点1，12，'BC'； 树插入节点12，121，'BG'；

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

树的根节点的值为'AB'； 树的根节点有子节点； 查找节点12，节点12不是叶子节点； 查找节点121，节点121是叶子节点； 节点121的父节点的值为'BC'；

移除节点12；

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