树结构工具类
javascript
class TreeUtil {
/**
* 将树形结构平铺为一维数组（深度优先）
* @param {Array} tree - 树形结构数据
* @param {string} [childrenField='children'] - 子节点字段名
* @returns {Array} 平铺后的一维数组
*/
static flattenTree(tree, childrenField = 'children') {
const result = []
const stack = [...tree]
while (stack.length) {
const node = stack.pop()
if (!node) continue
result.push(node)
if (Array.isArray(node[childrenField])) {
stack.push(...[...node[childrenField]].reverse())
}
}
return result
}
/**
* 将平铺数组组装成树形结构
* @param {Array} list - 平铺数组
* @param {Object} [options] - 配置选项
* @param {string|number} [options.rootId=null] - 根节点ID值
* @param {string} [options.idField='id'] - ID字段名
* @param {string} [options.parentField='parentId'] - 父ID字段名
* @param {string} [options.childrenField='children'] - 子节点字段名
* @returns {Array} 树形结构
*/
static buildTree(list, options = {}) {
const {
rootId = null,
idField = 'id',
parentField = 'parentId',
childrenField = 'children',
orphanAsRoot = false, // 是否将孤立的节点作为根节点
} = options
const nodeMap = new Map()
const result = []
// 创建节点映射
list.forEach(item => {
nodeMap.set(item[idField], { ...item, [childrenField]: [] })
})
// 构建树结构
nodeMap.forEach(node => {
const parentId = node[parentField]
if (parentId === rootId || parentId === undefined) {
result.push(node)
} else {
const parent = nodeMap.get(parentId)
if (parent) {
parent[childrenField].push(node)
} else if (orphanAsRoot) {
// 如果找不到父节点，并且orphanAsRoot为true，则将孤立的节点作为根节点
result.push(node)
}
}
})
return result
}
/**
* 查找指定节点
* @param {Array} tree - 树形结构
* @param {string|number} id - 要查找的节点ID
* @param {Object} [options] - 配置选项
* @param {string} [options.idField='id'] - ID字段名
* @param {string} [options.childrenField='children'] - 子节点字段名
* @returns {Object|null} 找到的节点或null
*/
static findNode(tree, id, options = {}) {
const { idField = 'id', childrenField = 'children' } = options
const stack = [...tree]
while (stack.length) {
const node = stack.pop()
if (node[idField] === id) return node
if (Array.isArray(node[childrenField])) {
stack.push(...node[childrenField])
}
}
return null
}
/**
* 查找节点路径
* @param {Array} tree - 树形结构
* @param {string|number} id - 要查找的节点ID
* @param {Object} [options] - 配置选项
* @param {string} [options.idField='id'] - ID字段名
* @param {string} [options.parentField='parentId'] - 父ID字段名
* @returns {Array} 节点路径数组（从根节点到目标节点）
*/
static findPath(tree, id, options = {}) {
const { idField = 'id', parentField = 'parentId' } = options
const flatList = this.flattenTree(tree)
const nodeMap = new Map(flatList.map(node => [node[idField], node]))
const path = []
let currentNode = nodeMap.get(id)
while (currentNode) {
path.unshift(currentNode)
const parentId = currentNode[parentField]
currentNode = parentId ? nodeMap.get(parentId) : null
}
return path
}
/**
* 过滤树结构（保留匹配节点及其所有祖先）
* @param {Array} tree - 树形结构
* @param {Function} predicate - 过滤条件函数
* @param {Object} [options] - 配置选项
* @param {string} [options.childrenField='children'] - 子节点字段名
* @returns {Array} 过滤后的树形结构
*/
static filterTree(tree, predicate, options = {}) {
const { childrenField = 'children' } = options
const filterSubtree = nodes => {
return nodes
.map(node => ({ ...node }))
.filter(node => {
// 递归过滤子节点
if (Array.isArray(node[childrenField])) {
node[childrenField] = filterSubtree(node[childrenField])
}
// 保留当前节点或其子节点有匹配的节点
return predicate(node) || (node[childrenField] && node[childrenField].length > 0)
})
}
return filterSubtree(tree)
}
/**
* 获取所有叶子节点
* @param {Array} tree - 树形结构
* @param {Object} [options] - 配置选项
* @param {string} [options.childrenField='children'] - 子节点字段名
* @returns {Array} 叶子节点数组
*/
static getLeaves(tree, options = {}) {
const { childrenField = 'children' } = options
const leaves = []
const traverse = nodes => {
nodes.forEach(node => {
if (!node[childrenField] || node[childrenField].length === 0) {
leaves.push(node)
} else {
traverse(node[childrenField])
}
})
}
traverse(tree)
return leaves
}
/**
* 树形结构遍历（深度优先）
* @param {Array} tree - 树形结构
* @param {Function} callback - 回调函数
* @param {Object} [options] - 配置选项
* @param {string} [options.childrenField='children'] - 子节点字段名
*/
static traverseDFS(tree, callback, options = {}) {
const { childrenField = 'children' } = options
const traverse = (nodes, parent = null, level = 0) => {
nodes.forEach(node => {
callback(node, parent, level)
if (node[childrenField]) {
traverse(node[childrenField], node, level + 1)
}
})
}
traverse(tree)
}
/**
* 树形结构遍历（广度优先）
* @param {Array} tree - 树形结构
* @param {Function} callback - 回调函数
* @param {Object} [options] - 配置选项
* @param {string} [options.childrenField='children'] - 子节点字段名
*/
static traverseBFS(tree, callback, options = {}) {
const { childrenField = 'children' } = options
const queue = [...tree.map(node => ({ node, level: 0, parent: null }))]
while (queue.length) {
const { node, level, parent } = queue.shift()
callback(node, parent, level)
if (node[childrenField]) {
queue.push(
...node[childrenField].map(child => ({
node: child,
level: level + 1,
parent: node,
}))
)
}
}
}
/**
* 计算树的最大深度
* @param {Array} tree - 树形结构
* @param {Object} [options] - 配置选项
* @param {string} [options.childrenField='children'] - 子节点字段名
* @returns {number} 树的最大深度
*/
static getTreeDepth(tree, options = {}) {
const { childrenField = 'children' } = options
if (!tree || tree.length === 0) return 0
let maxDepth = 0
this.traverseDFS(
tree,
(_, __, level) => {
if (level > maxDepth) maxDepth = level
},
options
)
return maxDepth + 1
}
/**
* 在树中插入新节点
* @param {Array} tree - 树形结构
* @param {Object} newNode - 新节点
* @param {string|number} parentId - 父节点ID
* @param {Object} [options] - 配置选项
* @param {string} [options.idField='id'] - ID字段名
* @param {string} [options.childrenField='children'] - 子节点字段名
* @returns {boolean} 是否插入成功
*/
static insertNode(tree, newNode, parentId, options = {}) {
const { idField = 'id', childrenField = 'children' } = options
const parentNode = this.findNode(tree, parentId, options)
if (!parentNode) return false
if (!parentNode[childrenField]) {
parentNode[childrenField] = []
}
parentNode[childrenField].push(newNode)
return true
}
/**
* 从树中移除节点
* @param {Array} tree - 树形结构
* @param {string|number} id - 要移除的节点ID
* @param {Object} [options] - 配置选项
* @param {string} [options.idField='id'] - ID字段名
* @param {string} [options.childrenField='children'] - 子节点字段名
* @returns {boolean} 是否移除成功
*/
static removeNode(tree, id, options = {}) {
const { idField = 'id', childrenField = 'children' } = options
const findAndRemove = nodes => {
for (let i = 0; i < nodes.length; i++) {
if (nodes[i][idField] === id) {
nodes.splice(i, 1)
return true
}
if (nodes[i][childrenField]) {
if (findAndRemove(nodes[i][childrenField])) {
return true
}
}
}
return false
}
return findAndRemove(tree)
}
}
// 示例使用
const treeData = [
{
id: 1,
name: 'Node 1',
children: [
{ id: 2, name: 'Node 1.1', parentId: 1 },
{
id: 3,
name: 'Node 1.2',
parentId: 1,
children: [{ id: 4, name: 'Node 1.2.1', parentId: 3 }],
},
],
},
{
id: 5,
name: 'Node 2',
children: [{ id: 6, name: 'Node 2.1', parentId: 5 }],
},
]