定义

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

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 = [];

}

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;

}

}

用class创建一个类TreeNode，使用构造函数初始化 key, value, parent 和 children。

定义一个isLeaf getter方法，用Array.prototype.length检查children是否为空。

定义一个hasChildren getter方法，用来检查是否有子节点。

用 class 创建一个Tree，使用构造函数初始化树的根节点。

定义一个preOrderTraversal() 方法，按顺序遍历树的生成器方法，使用 yield* 语法将遍历委托给自身。

定义一个postOrderTraversal()方法，以后序遍历树的生成器方法，使用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']