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]);
    }
  }
}