树形结构

2017-12-24 数据结构与算法

树形结构是一种层次嵌套的结构。它提供了一种有序的组织方式，能够方便地表示层次关系和结构化数据，在文件系统、数据库索引、DOM 等场景中被广泛应用。树形结构的遍历、搜索和操作等算法也是计算机中常见的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const tree = [
  {
    "id": 74,
    "parentId": null,
    "children": [
      {
        "id": 62,
        "parentId": 74
      },
      {
        "id": 86,
        "parentId": 74,
      }
    ]
  }
]

树的遍历

树的遍历是树数据结构的最基础操作，是树的转换、查找、筛选等一系列操作的基础。

树的遍历遍历分为广度优先遍历（BFS）和深度优先遍历（DFS）。深度优先遍历按节点的访问顺序又分为先序遍历、后序遍历，二叉树还有中序遍历，实现方法可以是递归，也可以是循环，而广度优先遍历是非递归的，使用循环来实现。

深度优先是按路径遍历，访问一条路径（一颗子树），直到末端节点，不能再深入为止，然后回溯并访问其他分支。而访问子树的时候，先访问根再访问根的子树，称为先序遍历，先访问子树再访问根，称为后序遍历。广度优先是按层序遍历，按顺序逐层遍历，遍历完第 n 层再遍历 n+1 层。

广度优先

1
2
3
4
5
6
7
8
function forEachTree(tree, callback, childrenName = 'subList') {
  let node
  const list = [...tree]
  while ((node = list.shift())) {
    callback(node)
    node[childrenName] && list.push(...node[childrenName])
  }
}

子节点 push 到队列后面，遍历时从队列前面 shift 节点，即一层层遍历（队列先进先出）。

深度优先

  • 递归

递归的深度优先搜索也被称为回溯。

1
2
3
4
5
6
7
// 先序遍历
function forEachTree(tree, callback) {
  tree.forEach(item => {
    callback(item)
    item.children && forEachTree(item.children, callback)
  })
}
1
2
3
4
5
6
7
// 后序遍历与先序遍历思想一致，只不过调换一下节点访问和子树遍历的顺序
function forEachTree (tree, callback) {
  tree.forEach(item => {
    item.children && forEachTree(item.children, callback)
    callback(item)
  })
}
  • 循环
1
2
3
4
5
6
7
8
// 先序遍历与广度优先实现类似，要维护一个队列，不同的是子节点不追加到队列最后，而是加到队列最前面
function forEachTree (tree, callback) {
  let node, list = [...tree]
  while (node = list.shift()) {
    callback(node)
    node.children && list.unshift(...node.children)
  }
}

子节点 unshift 到队列前面，遍历时从队列前面 shift 节点，即一颗颗子树遍历（栈先进后出）。

JavaScript 中可用 Array 实现 List 和 Stock。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 后序遍历略微复杂一点，需要不断将子树扩展到根节点前面去，执行列表遍历，遍历到某个节点如果它没有子节点或者它的子节点已经扩展到它前面了，则执行访问操作，否则扩展子节点到当前节点前面
function forEachTree (tree, callback) {
  let node, list = [...tree], i =  0
  while (node = list[i]) {
    let childCount = node.children ? node.children.length : 0
    if (!childCount || node.children[childCount - 1] === list[i - 1]) {
      callback(node)
      i++
    } else {
      list.splice(i, 0, ...node.children)
    }
  }
}

列表和树的相互转换

列表转树

  • 递归
1
2
3
4
5
6
7
8
9
10
11
const data = [
  { id: 56, parentId: 62 },
  { id: 81, parentId: 80 },
  { id: 74, parentId: null },
  { id: 76, parentId: 80 },
  { id: 63, parentId: 62 },
  { id: 80, parentId: 86 },
  { id: 87, parentId: 86 },
  { id: 62, parentId: 74 },
  { id: 86, parentId: 74 },
];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 父元素 id 默认为 null，从根节点开始构建
function listToTree(list, parentId = null) {
  const tree = []
  list.forEach((item) => {
    // 判断当前元素是否为子元素
    if (item.parentId === parentId) {    
      // 将当前元素作为父元素，获取当前元素的子元素                   
      const children = listToTree(list, item.id)  
      if (children.length) {
        item.children = children
      }
      tree.push(item)                             
    }
  })
  return tree                                  
}

listToTree(data)

使用 filter 和 map 简化上述代码。

1
2
3
4
5
6
7
8
9
10
function listToTree(list, parentId = null) {
  return list.filter((item) => item.parentId === parentId)
    .map((item) => {
      const children = listToTree(list, item.id)
      if (children.length) {
        return {...item, children}
      }
      return {...item}
    })
}
  • 引用

利用 JavaScript 引用类型特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// list 最好是深拷贝一下，否则引用类型特性，会导致原始数据改变
function listToTree(list) {
  function findParentEl(id) {
    for (let i = 0; i < list.length; i += 1) {
      if (list[i].id === id) {
        return list[i]
      }
    }
  }

  let root = null
  list.forEach((el) => {
    if (!el.parentId) {
      root = el
      return
    }

    const parentEl = findParentEl(el.parentId)
    parentEl.children = [...(parentEl.children || []), el]
  })
  return root
}

使用 map 结构，以空间换时间，可将上面的算法时间复杂度由 O(n^2) 优化到 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function listToTree(list) {
  const idMap = list.reduce((acc, el, i) => {
    acc[el.id] = i
    return acc
  }, {})

  let root = null
  list.forEach((el) => {
    if (!el.parentId) {
      root = el
      return
    }
    const parentEl = list[idMap[el.parentId]]
    parentEl.children = [...(parentEl.children || []), el]
  })

  return root
}

使用 filter 找根节点，简化上述代码。

1
2
3
4
5
6
7
function listToTree (list) {
  let info = list.reduce((map, node) => (map[node.id] = node, node.children = [], map), {})
  return list.filter(node => {
    info[node.parentId] && info[node.parentId].children.push(node)
    return !node.parentId // 没有父节点的节点，即根节点
  })
}

树转列表

以采用深度优先中的递归和循环解法为例。

  • 递归
1
2
3
4
5
6
7
8
9
10
function flattenTree(tree, childrenName = 'children') {
  return tree.reduce((acc, item) => {
    const { [childrenName]: children, ...rest } = item
    const hasChildren = children && children.length > 0
    return acc.concat(
      rest,
      hasChildren ? flattenTree(children, childrenName) : []
    )
  }, [])
}

结果除了使用 reduce 累计外，还可作为参数传递累计，原理一样。

1
2
3
4
5
6
7
8
9
function flattenTree(tree, result = [], level = 0) {
  tree.forEach(node => {
    result.push(node)
    // 节点深度
    node.level = level + 1
    node.children && flattenTree(node.children, result, level + 1)
  })
  return result
}

转换时添加额外信息，比如 hasChildren、chain。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function flattenTree(tree, childrenName = 'children') {
  return tree.reduce((acc, item) => {
    let { [childrenName]: children, chain = [], ...rest } = item
    const hasChildren = children && children.length > 0

    const node = {
      ...rest,
      hasChildren,
      chain: [...chain, { ...rest }],
    }

    if (hasChildren) {
      children = children?.map((child) => {
        child.chain = node.chain
        return child
      })
    }

    return acc.concat(
      node,
      hasChildren ? flattenTree(children, childrenName) : []
    )
  }, [])
}
  • 循环
1
2
3
4
5
6
7
8
9
function flattenTree (tree) {
  let node, result = tree.map(node => (node.level = 1, node))
  for (let i = 0; i < result.length; i++) {
    if (!result[i].children) continue
    let list = result[i].children.map(node => (node.level = result[i].level + 1, node))
    result.splice(i+1, 0, ...list)
  }
  return result
}

树的其他操作

  • 查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 查找节点
function findTree(tree = [], callback, childrenName = 'subList') {
  for (const item of tree) {
    const { [childrenName]: children } = item
    
    if (callback(item)) {
      return item
    }

    const hasChildren = !!children?.length

    if (hasChildren) {
      const foundInChild = findTree(children, callback, childrenName)
      if (foundInChild) {
        return foundInChild
      }
    }
  }

  return null
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 查找节点路径
// 使用先序遍历查找路径，维护一个队列存储路径上每个节点 id，假设节点就在当前分支，如果当前分支查不到，则回溯
function findTreePath (tree, callback, path = []) {
  for (const data of tree) {
    path.push(data.id)
    if (callback(data)) {
      return path
    }
    if (data.children) {
      const foundInChild = findTreePath(data.children, callback, path)
      if (foundInChild.length) {
        return foundInChild
      }
    }
    path.pop()
  }
  return []
}

findTreePath(tree, (item) => item.id === 86) // [74, 86]
1
2
3
4
5
6
7
8
9
10
11
12
// 查找多个节点路径
function findTreePathList (tree, callback, path = [], result = []) {
  for (const data of tree) {
    path.push(data.id)
    callback(data) && result.push([...path])
    data.children && findTreePathList(data.children, callback, path, result)
    path.pop()
  }
  return result
}

findTreePathList(tree, (item) => [62, 86].includes(item.id)) // [[74, 62], [74, 86]]
  • 筛选
1
2
3
4
5
6
7
function filterTree (tree, callback) {
  // 使用 map 复制节点，防止修改原树
  return tree.map(node => ({ ...node })).filter(node => {
    node.children = node.children && filterTree(node.children, callback)
    return callback(node) || (node.children && node.children.length)
  })
}
  • 映射
1
2
3
4
5
6
7
8
function mapTree(tree, callback, childrenName = 'subList') {
  return JSON.parse(JSON.stringify(tree)).map(item => {
    item = callback(item)
    const hasChildren = !!item[childrenName]?.length
    item[childrenName] = hasChildren && mapTree(item[childrenName], callback, childrenName)
    return item
  })
}

使用 mapTree 计算节点的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mapTree(
  res.data,
  item => {
    // 计算节点深度
    item.level = (item.parentLevel || 0) + 1
    // 告诉子节点父节点的深度
    if (item.children) {
      item.children.map(child => {
        child.parentLevel = item.level
      })
    } 
    return item
  },
  'children'
)
  • 排序
1
2
3
4
5
6
7
const sortTree = (tree, callback, childrenName = 'subList') => {
  return tree
    .map(item => {
      return item[childrenName] ? { ...item, [childrenName]: sortTree(item[childrenName], callback, childrenName) } : item
    })
    .sort(callback)
}
  • 检测
1
2
3
4
5
6
7
8
9
10
11
12
function someTree(tree, callback, childrenName = 'subList') {
  for (const item of tree || []) {
    if (callback && callback(item)) {
      return true
    }
    const hasChildren = !!item[childrenName]?.length
    if (hasChildren && someTree(item[childrenName], callback, childrenName)) {
      return true
    }
  }
  return false
}