js 实现树形结构
树形结构的实现方法
在JavaScript中实现树形结构可以通过多种方式完成，以下是几种常见的方法：
使用对象表示树
可以通过嵌套对象来表示树形结构，每个节点包含一个值和一个子节点数组。
const tree = {
value: 'root',
children: [
{
value: 'child1',
children: []
},
{
value: 'child2',
children: [
{
value: 'grandchild1',
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('child1');
const child2 = new TreeNode('child2');
root.addChild(child1);
root.addChild(child2);使用数组表示扁平化树
扁平化的数组结构可以通过id和parentId来表示树形关系。
const flatTree = [
{ id: 1, parentId: null, name: 'root' },
{ id: 2, parentId: 1, name: 'child1' },
{ id: 3, parentId: 1, name: 'child2' },
{ id: 4, parentId: 2, name: 'grandchild1' }
];树形结构的遍历方法
深度优先遍历（DFS）
递归实现深度优先遍历：
function dfs(node) {
console.log(node.value);
node.children.forEach(child => dfs(child));
}
dfs(tree);广度优先遍历（BFS）
使用队列实现广度优先遍历：
function bfs(root) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
console.log(node.value);
node.children.forEach(child => queue.push(child));
}
}
bfs(tree);扁平化数组转树形结构
将扁平化数组转换为嵌套的树形结构：
function buildTree(items) {
const map = {};
const roots = [];
items.forEach(item => {
map[item.id] = { ...item, children: [] };
});
items.forEach(item => {
if (item.parentId === null) {
roots.push(map[item.id]);
} else {
map[item.parentId].children.push(map[item.id]);
}
});
return roots;
}
const nestedTree = buildTree(flatTree);
console.log(nestedTree);树形结构的常见操作
查找节点
通过递归查找特定节点：
function findNode(node, value) {
if (node.value === value) return node;
for (const child of node.children) {
const found = findNode(child, value);
if (found) return found;
}
return null;
}
const foundNode = findNode(tree, 'child2');
console.log(foundNode);删除节点
通过递归删除特定节点：
function removeNode(node, value) {
node.children = node.children.filter(child => child.value !== value);
node.children.forEach(child => removeNode(child, value));
}
removeNode(tree, 'grandchild1');
console.log(tree);树形结构的渲染
在前端页面中渲染树形结构，通常使用递归组件或动态生成DOM元素：
function renderTree(node, parentElement) {
const element = document.createElement('div');
element.textContent = node.value;
parentElement.appendChild(element);
if (node.children.length > 0) {
const childrenContainer = document.createElement('div');
childrenContainer.style.marginLeft = '20px';
parentElement.appendChild(childrenContainer);
node.children.forEach(child => renderTree(child, childrenContainer));
}
}
const container = document.getElementById('tree-container');
renderTree(tree, container);以上方法涵盖了树形结构的基本实现、遍历、转换和操作，可以根据具体需求选择适合的方式。
