树结构的遍历

发表于： 分类于：
字数： 441 阅读：≈ 1分钟 浏览：

树的结构 

let tree = [
  {
    value: '1',
    label: '节点1',
    children: [
      {
        value: '1-1',
        label: '节点1-1'
      },
      {
        value: '1-2',
        label: '节点1-2'
      }
    ]
  },
  {
    value: '2',
    label: '节点2',
    children: [
      {
        value: '2-1',
        label: '节点2-1'
      }
    ]
  },
  ...
]

查找节点 

function treeEach (tree, func) {
  let node, list = [...tree]
  while (node = list.shift()) {
    if (func(node)) {
      return node
    }
    node.children && list.push(...node.children)
  }
}

应用上面的代码，查找value为'1-1’的节点

treeEach(tree, (node) => node.value === '1-1')

树转化为列表 

function treeToList (tree, res = []) {
  tree.forEach(node => {
    res.push(node)
    node.children && treeToList(node.children, res)
  })
  return res
}

执行上面的代码，得到如下结构：

let list = treeToList (tree);
cosnole.log(list)
// 输出
[
  {
    value: '1',
    label: '节点1',
  },
  {
    value: '1-1',
    label: '节点1-1',
  },
  {
    value: '1-2',
    label: '节点1-2',
  },
  {
    value: '2',
    label: '节点2',
  },
  {
    value: '2-1',
    label: '节点2-1',
  }
]

查找树节点路径

采用回溯法的思想，使用先序遍历，维护一个队列存储路径上每个节点的id，假设节点就在当前分支，如果当前分支查不到，则回溯。

function treeFindPath (tree, func, path = []) {
  if (!tree) return []
  for (const data of tree) {
    path.push(data.id)
    if (func(data)) return path
    if (data.children) {
      const findChildren = treeFindPath(data.children, func, path)
      findChildren.length && return findChildren
    }
    path.pop()
  }
  return []
}