js实现树形结构
使用对象和数组构建树形结构
在JavaScript中，树形结构通常通过对象和数组的组合来实现。每个节点是一个对象，包含数据和子节点的引用。
const tree = {
value: 'Root',
children: [
{
value: 'Child 1',
children: [
{ value: 'Grandchild 1', children: [] },
{ value: 'Grandchild 2', children: [] }
]
},
{
value: 'Child 2',
children: [
{ value: 'Grandchild 3', children: [] }
]
}
]
};递归遍历树结构
深度优先遍历(DFS)是处理树形结构的常见方法，递归是实现DFS的简洁方式。
function traverse(node) {
console.log(node.value);
node.children.forEach(child => {
traverse(child);
});
}
traverse(tree);使用类实现树节点
通过类可以更规范地定义树节点，便于扩展和维护。
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
addChild(childNode) {
this.children.push(childNode);
}
}
const root = new TreeNode('Root');
const child1 = new TreeNode('Child 1');
const child2 = new TreeNode('Child 2');
root.addChild(child1);
root.addChild(child2);扁平数据转树形结构
当数据以扁平数组形式存储时，可以使用以下方法转换为树形结构。
function buildTree(items, id = null, link = 'parentId') {
return items
.filter(item => item[link] === id)
.map(item => ({ ...item, children: buildTree(items, item.id) }));
}
const flatData = [
{ id: 1, name: 'Root', parentId: null },
{ id: 2, name: 'Child 1', parentId: 1 },
{ id: 3, name: 'Child 2', parentId: 1 },
{ id: 4, name: 'Grandchild', parentId: 2 }
];
const treeData = buildTree(flatData);广度优先遍历(BFS)
与DFS不同，BFS逐层遍历树节点，适合需要按层级处理的场景。
function bfs(root) {
const queue = [root];
while (queue.length) {
const node = queue.shift();
console.log(node.value);
node.children.forEach(child => {
queue.push(child);
});
}
}
bfs(tree);树形结构搜索
在树中搜索特定节点可以使用递归或迭代方法。
function searchTree(node, targetValue) {
if (node.value === targetValue) return node;
for (const child of node.children) {
const found = searchTree(child, targetValue);
if (found) return found;
}
return null;
}
const foundNode = searchTree(tree, 'Grandchild 2');树形结构可视化
使用缩进来可视化树形结构可以方便调试和展示。
function printTree(node, indent = 0) {
console.log(' '.repeat(indent) + node.value);
node.children.forEach(child => {
printTree(child, indent + 2);
});
}
printTree(tree);处理大型树的性能优化
对于大型树结构，可以考虑使用尾递归优化或迭代方法来避免堆栈溢出。
function traverseLargeTree(root) {
const stack = [root];
while (stack.length) {
const node = stack.pop();
console.log(node.value);
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]);
}
}
}
