js实现树状
js实现树状结构
树状结构在JavaScript中通常用于表示层级数据，例如文件系统、组织架构或菜单。以下是几种常见的实现方式：
使用对象表示树
最简单的树状结构可以通过嵌套对象实现：
const tree = {
value: 'Root',
children: [
{
value: 'Child 1',
children: [
{ value: 'Grandchild 1', children: [] },
{ value: 'Grandchild 2', children: [] }
]
},
{
value: 'Child 2',
children: []
}
]
};使用类实现树节点
更结构化的方式是通过类定义树节点：
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 traverse(node) {
console.log(node.value);
node.children.forEach(child => traverse(child));
}非递归遍历
使用栈实现深度优先遍历：
function traverse(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]);
}
}
}树状结构可视化
使用递归生成HTML结构的示例：
function renderTree(node) {
if (!node.children.length) return `<li>${node.value}</li>`;
return `
<li>
${node.value}
<ul>
${node.children.map(child => renderTree(child)).join('')}
</ul>
</li>
`;
}查找节点
深度优先搜索实现：
function findNode(root, targetValue) {
if (root.value === targetValue) return root;
for (const child of root.children) {
const found = findNode(child, targetValue);
if (found) return found;
}
return null;
}性能优化
对于大型树结构，可以考虑以下优化：
- 使用备忘录模式缓存遍历结果
- 实现广度优先搜索时使用队列
- 为节点添加唯一标识符便于查找
实际应用示例
文件目录树的实现：
class FileSystem {
constructor(name, isFolder = false) {
this.name = name;
this.isFolder = isFolder;
this.children = [];
}
addItem(item) {
if (!this.isFolder) throw new Error('Can only add to folders');
this.children.push(item);
}
find(path) {
const parts = path.split('/');
let current = this;
for (const part of parts) {
if (!part) continue;
const found = current.children.find(item => item.name === part);
if (!found) return null;
current = found;
}
return current;
}
}
