数组树
2024年06月06日
一、树转扁平
实现
function flattenTree(tree) {
const result = [];
function traverse(node) {
const { id, pid, children } = node;
result.push({ id, pid });
if (children) {
for (const child of children) {
traverse(child);
}
}
}
for (const node of tree) {
traverse(node);
}
return result;
}
测试
const tree = [
{
id: 1,
pid: 0,
children: [
{
id: 11,
pid: 1,
children: [
{
id: 111,
pid: 11,
},
{
id: 112,
pid: 11,
},
],
},
{
id: 12,
pid: 1,
children: [
{
id: 121,
pid: 12,
},
{
id: 122,
pid: 12,
},
],
},
],
},
{
id: 2,
pid: 0,
children: [
{
id: 21,
pid: 2,
children: [
{
id: 211,
pid: 21,
},
{
id: 212,
pid: 21,
children: [
{
id: 2121,
pid: 212,
},
{
id: 2122,
pid: 212,
},
],
},
],
},
{
id: 22,
pid: 2,
children: [
{
id: 221,
pid: 22,
},
{
id: 222,
pid: 22,
},
],
},
],
},
];
const flattenedTree = flattenTree(tree);
console.log("flattenedTree: ", flattenedTree);
二、扁平转树
实现
function toTree(array) {
const map = {};
const result = [];
array.forEach((node) => {
map[node.id] = { ...node, children: [] };
});
array.forEach((node) => {
if (node.pid === 0) {
result.push(map[node.id]);
} else {
map[node.pid].children.push(map[node.id]);
}
});
return result;
}
测试
const array = [
{ id: 1, pid: 0, path: "1" },
{ id: 11, pid: 1, path: "1,11" },
{ id: 111, pid: 11, path: "1,11,111" },
{ id: 112, pid: 11, path: "1,11,112" },
{ id: 12, pid: 1, path: "1,12" },
{ id: 121, pid: 12, path: "1,12,121" },
{ id: 122, pid: 12, path: "1,12,122" },
{ id: 2, pid: 0, path: "2" },
{ id: 21, pid: 2, path: "2,21" },
{ id: 211, pid: 21, path: "2,21,211" },
{ id: 212, pid: 21, path: "2,21,212" },
{ id: 2121, pid: 212, path: "2,21,212,2121" },
{ id: 2122, pid: 212, path: "2,21,212,2122" },
{ id: 22, pid: 2, path: "2,22" },
{ id: 221, pid: 22, path: "2,22,221" },
{ id: 222, pid: 22, path: "2,22,222" },
];
const tree = toTree(array);
console.log("tree",tree);
三、树最大深度
3.1 对象最大深度
功能: 寻找一个树形元素中最大深度的元素
实现
function findTreeDepth(treeNode) {
let maxDepth = 0;
let maxDepthElement = null;
function traverse(node, depth) {
if (depth > maxDepth) {
maxDepth = depth;
maxDepthElement = node;
}
if (node.children) {
for (const child of node.children) {
traverse(child, depth + 1);
}
}
}
traverse(treeNode, 1);
return { maxDepth, maxDepthElement };
}
测试
const treeNode = {
id: 2,
pid: 0,
children: [
{
id: 21,
pid: 2,
children: [
{
id: 211,
pid: 21,
},
{
id: 212,
pid: 21,
children: [
{
id: 2121,
pid: 212,
},
{
id: 2122,
pid: 212,
},
],
},
],
},
{
id: 22,
pid: 2,
children: [
{
id: 221,
pid: 22,
},
{
id: 222,
pid: 22,
},
],
},
],
};
const result = findTreeDepth(treeNode);
console.log("Max Depth:", result.maxDepth);
console.log("Max Depth Element:", result.maxDepthElement);
3.2 数组最大深度
功能: 寻找所有树形数组中最大深度的元素
实现
function findTreeDepth(tree) {
let maxDepth = 0;
let maxDepthElement = null;
function traverse(node, depth) {
if (depth > maxDepth) {
maxDepth = depth;
maxDepthElement = node;
}
if (node.children) {
for (const child of node.children) {
traverse(child, depth + 1);
}
}
}
for (const node of tree) {
traverse(node, 1);
}
return { maxDepth, maxDepthElement };
}
测试
const tree = [
{
id: 1,
pid: 0,
children: [
{
id: 11,
pid: 1,
children: [
{
id: 111,
pid: 11,
},
{
id: 112,
pid: 11,
},
],
},
{
id: 12,
pid: 1,
children: [
{
id: 121,
pid: 12,
},
{
id: 122,
pid: 12,
},
],
},
],
},
{
id: 2,
pid: 0,
children: [
{
id: 21,
pid: 2,
children: [
{
id: 211,
pid: 21,
},
{
id: 212,
pid: 21,
children: [
{
id: 2121,
pid: 212,
},
{
id: 2122,
pid: 212,
},
],
},
],
},
{
id: 22,
pid: 2,
children: [
{
id: 221,
pid: 22,
},
{
id: 222,
pid: 22,
},
],
},
],
},
];
const result = findTreeDepth(tree);
console.log("Max Depth:", result.maxDepth);
console.log("Max Depth Element:", result.maxDepthElement);
四、扁平转树,附加路径
实现
function flattenTree(tree) {
const result = [];
function traverse(node, path = "") {
const { id, pid, children } = node;
const nodePath = path ? `${path},${id}` : `${id}`;
result.push({ id, pid, path: nodePath });
if (children) {
for (const child of children) {
traverse(child, nodePath);
}
}
}
for (const node of tree) {
traverse(node);
}
return result;
}
测试
const tree = [
{
id: 1,
pid: 0,
children: [
{
id: 11,
pid: 1,
children: [
{
id: 111,
pid: 11,
},
{
id: 112,
pid: 11,
},
],
},
{
id: 12,
pid: 1,
children: [
{
id: 121,
pid: 12,
},
{
id: 122,
pid: 12,
},
],
},
],
},
{
id: 2,
pid: 0,
children: [
{
id: 21,
pid: 2,
children: [
{
id: 211,
pid: 21,
},
{
id: 212,
pid: 21,
children: [
{
id: 2121,
pid: 212,
},
{
id: 2122,
pid: 212,
},
],
},
],
},
{
id: 22,
pid: 2,
children: [
{
id: 221,
pid: 22,
},
{
id: 222,
pid: 22,
},
],
},
],
},
];
const flattenedTree = flattenTree(tree);
console.log("flattenedTree: ", flattenedTree);