0、举例：树形结构原始数据
1、序列化树形结构
/**
* 平铺序列化树形结构
* @param tree 树形结构
* @param result 转化后一维数组
* @returns Array<TreeNode>
*/
export function flattenTree(tree, result = []) {
if (tree.length === 0) {
return result
}
for (const node of tree) {
result.push(node);
if (node.children) {
flattenTree(node.children, result);
}
}
return result;
}
结果：
2、数组转化为树形结构
/**
* 数组转化为树形结构（常用于后台菜单数组转换成树形结构）
*/
export function arrToTree(data) {
let result = []
let map = new Map()
data.forEach(item => {
// 存入字典集里
map.set(item.id, item)
})
data.forEach(item => {
item.children = [];
// 判断字典集里是否有该键
let parent = map.get(item.pId)
if (parent) {
parent.children.push(item)
} else {
result.push(item)
}
})
return result
}结果：
3、BFS 寻找树形结构下指定节点id 上属直接或间接的祖先节点
/**
* 寻找树形结构下指定节点id 上属直接或间接的祖先节点
* @param {*} tree 树形结构
* @param {*} id 节点id
*/
bfsFindAncestors(tree, id) {
if (!tree?.length) return [];
// 初始化队列，将根节点和空的祖先数组放入队列
const queue = [{ node: tree[0], ancestors: [] }];
while (queue.length > 0) {
// 取出队列中的第一个节点和其祖先数组
const { node, ancestors } = queue.shift();
if (node.id === id) {
// 找到目标节点，返回该节点及其祖先节点的数组
return ancestors;
}
if (node.children && node.children.length > 0) {
// 将当前节点添加到子节点的祖先数组中
const newAncestors = [...ancestors, node];
for (const child of node.children) {
// 将子节点和新的祖先数组加入队列
queue.push({ node: child, ancestors: newAncestors });
}
}
}
// 如果遍历完整个树都没有找到目标节点，返回空数组
return [];
}4、BFS 遍历树形结构 寻找对应id的节点
/**
* BFS遍历树形结构 寻找对应id的节点
* @param {*} tree 树形结构
* @param {*} id 节点id
*/
getNode(tree, id) {
const queue = [...tree];
while (queue.length) {
const node = queue.shift();
if (node.id === id) return node;
if (node.children?.length) {
queue.push(...node.children);
}
}
return null;
}5、BFS 遍历树结构 给节点某属性赋值
/**
* 遍历树结构 给节点某属性赋值 BFS
* @param {*} tree 树形结构
* @param {*} prop 属性
* @param {*} value 值
*/
traverseTreeSetProperty(tree, prop, value) {
// 定义一个队列，用于存储待处理的节点
const queue = [...tree];
while (queue.length > 0) {
// 出队列
const node = queue.shift();
// 给当前节点赋值
node[prop] = value;
// 将当前节点的子节点入队列
if (node.children && node.children.length > 0) {
queue.push(...node.children);
}
}
}6、BFS 计算树形结构的最大宽度
/**
* 计算树形结构的最大宽度 BFS
* @param {*} tree 树形结构
*/
getMaxWidth(tree) {
if (!tree || tree.length === 0) {
return 0;
}
let maxWidth = 0;
let queue = [...tree];
while (queue.length > 0) {
const levelSize = queue.length;
maxWidth = Math.max(maxWidth, levelSize);
const nextLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue[i];
if (node.children && node.children.length > 0) {
nextLevel.push(...node.children);
}
}
queue = nextLevel;
}
return maxWidth;
}7、DFS 计算树形结构的最大深度
/**
* 计算树形结构的最大深度 DFS
* @param {*} tree 树形结构
*/
getMaxDepth(tree) {
const dfs = (nodes) => {
// 一级节点为空，层级则为0
if (!nodes?.length) return 0;
let maxDepth = 1;
// eslint-disable-next-line
for (const node of nodes) {
const curDepth = dfs(node.children) + 1;
maxDepth = Math.max(curDepth, maxDepth);
}
return maxDepth;
}
const treeHeight = dfs(tree)
return treeHeight;
}8、DFS 寻找指定节点id对应的父级节点
/**
* 寻找指定节点id对应的父级节点
* @param {*} tree
* @param {*} nodeId
*/
findParentByChildId(tree, nodeId) {
let parentOfFirstChild = null;
const dfs = (node, parent) => {
if (parentOfFirstChild !== null) {
return;
}
if (node.children && node.children.length > 0) {
// eslint-disable-next-line
for (const child of node.children) {
dfs(child, node);
}
}
// 找到对应节点后，返回其父节点
if (node.id === nodeId) parentOfFirstChild = parent;
}
// eslint-disable-next-line
for (const node of tree) {
dfs(node, null);
}
return parentOfFirstChild
}9、DFS 寻找第一个叶子节点及对应的父节点
/**
* 寻找第一个叶子节点及叶子节点的父节点
* @param {*} tree
*/
findFirstChildAndParent(tree) {
let firstChild = null;
let parentOfFirstChild = null;
const dfs = (node, parent) => {
if (firstChild !== null) {
return; // 如果已经找到了第一个子节点，则不再继续搜索
}
if (node.children && node.children.length > 0) {
for (const child of node.children) {
dfs(child, node);
}
} else {
firstChild = node;
parentOfFirstChild = parent;
}
}
for (const node of tree) {
dfs(node, null);
}
return {
firstChild,
parentOfFirstChild
};
}
