有趣且重要的JS知识合集（22）树相关的算法

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) => {// 一级节点为空，层级则为0if (!nodes?.length) return 0;let maxDepth = 1;// eslint-disable-next-linefor (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-linefor (const child of node.children) {dfs(child, node);}}// 找到对应节点后，返回其父节点if (node.id === nodeId) parentOfFirstChild = parent;}// eslint-disable-next-linefor (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};}