js 实现tree
JavaScript 实现树结构
在 JavaScript 中实现树结构通常涉及创建节点类和树类，或使用对象和数组的组合来表示树。以下是几种常见的实现方式：
使用类和对象实现树
定义一个 TreeNode 类表示树的节点，再定义一个 Tree 类管理树的操作。
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
addChild(childNode) {
this.children.push(childNode);
}
}
class Tree {
constructor(rootValue) {
this.root = new TreeNode(rootValue);
}
traverseDFS(node = this.root, callback) {
callback(node.value);
node.children.forEach(child => this.traverseDFS(child, callback));
}
traverseBFS(callback) {
const queue = [this.root];
while (queue.length) {
const currentNode = queue.shift();
callback(currentNode.value);
queue.push(...currentNode.children);
}
}
}使用纯对象实现树
如果不需要复杂的操作，可以直接用对象和数组表示树结构。
const tree = {
value: 'root',
children: [
{
value: 'child1',
children: [
{ value: 'grandchild1', children: [] },
{ value: 'grandchild2', children: [] }
]
},
{
value: 'child2',
children: []
}
]
};树的遍历方法
深度优先遍历（DFS）和广度优先遍历（BFS）是树的两种基本遍历方式。
// 深度优先遍历（递归）
function dfs(node) {
console.log(node.value);
node.children.forEach(dfs);
}
// 广度优先遍历（队列）
function bfs(root) {
const queue = [root];
while (queue.length) {
const node = queue.shift();
console.log(node.value);
queue.push(...node.children);
}
}树的常见操作
- 查找节点：可以通过遍历查找特定值的节点。
- 插入节点：找到父节点后，将新节点添加到其子节点列表。
- 删除节点：找到节点及其父节点，从父节点的子节点列表中移除。
function findNode(root, value) {
if (root.value === value) return root;
for (const child of root.children) {
const found = findNode(child, value);
if (found) return found;
}
return null;
}使用第三方库
如果需要更复杂的树操作，可以使用现成的库如：
tree-model：提供丰富的树操作功能。d3-hierarchy：适用于数据可视化的层次结构操作。
// 使用 tree-model 示例
const TreeModel = require('tree-model');
const tree = new TreeModel();
const root = tree.parse({ id: 1, children: [{ id: 2 }] });以上方法可以根据具体需求选择适合的实现方式。
