這個問題建立在許多類似的問題之上，例如Construct hierarchy tree from flat list with parent field?
然而，扭曲是沒有父ID。例如
[
{id: 1, depth: 1, ...},
{id: 2, depth: 2, ...},
{id: 3, depth: 3, ...},
{id: 4, depth: 2, ...},
{id: 5, depth: 1, ...},
{id: 6, depth: 2, ...},
{id: 7, depth: 2, ...},
{id: 8, depth: 1, ...},
{id: 9, depth: 2, ...},
{id: 10, depth: 3, ...},
{id: 11, depth: 3, ...},
]
構建以下樹的高效方法是什么？請注意，孩子總是在父母之后，即可以從depth值中看到樹。例如，id 2是id 1since 它的深度為 2 且id 1深度為 13的子代。id 是id 2sinceid 3的深度為 3id 4的子代。是id 1 not id 3的子代，因為id 4其深度為 2（上一步id 3）深度 3
\\tree digram
1
2
3
4
5
6
7
8
9
10
11
應該有像
[
{id:1, depth:1, children: [
{id: 2, depth: 2, children: [...]},
...
]},
{id:5, depth:1, children: [...]},
{id:6, depth:1, children: [...]},
]
uj5u.com熱心網友回復：
您可以為此使用一個陣列，該陣列具有每個深度的索引。每時每刻，它將代表從（虛擬）根到當前節點的路徑。當處理一個節點時，它的父節點將位于 index depth-1，它可以插入到該父節點的children屬性中，并且節點本身將被放置在 index depth：
function createForest(flatdata) {
const path = [{ children: [] }];
for (const obj of flatdata) {
path[obj.depth - 1].children.push(path[obj.depth] = { ...obj, children: [] });
}
return path[0].children;
}
// demo
const flatdata = [{id: 1, depth: 1},{id: 2, depth: 2},{id: 3, depth: 3},{id: 4, depth: 2},{id: 5, depth: 1},{id: 6, depth: 2},{id: 7, depth: 2},{id: 8, depth: 1},{id: 9, depth: 2},{id: 10, depth: 3},{id: 11, depth: 3}];
const roots = createForest(flatdata);
console.log(roots);不規則深度
如果值與節點的實際depth深度不對應，但留下了間隙，則使用“字典”（普通物件）記錄與它們對應的實際深度的屬性值的映射：depth
function createForest(flatdata) {
const path = [{ children: [] }];
const depthMap = { 0: 0 };
for (const obj of flatdata) {
path[(depthMap[obj.depth] ??= path.length) - 1].children.push(
path[depthMap[obj.depth]] = { ...obj, children: []}
);
}
return path[0].children;
}
// demo
const flatdata = [{id: 1, depth: 10},{id: 2, depth: 20},{id: 3, depth: 30},{id: 4, depth: 20},{id: 5, depth: 10},{id: 6, depth: 20},{id: 7, depth: 20},{id: 8, depth: 10},{id: 9, depth: 20},{id: 10, depth: 30},{id: 11, depth: 30}];
const roots = createForest(flatdata);
console.log(roots);然而，如果唯一的不規則是深度并不總是從 1 開始，而是有時從 2 開始，那么在輸入資料前加上一個虛擬的 depth-one 節點，使用第一個函式，然后洗掉虛擬節點會更有效結果中的“根”（深度為 1）。
uj5u.com熱心網友回復：
遍歷陣列并將每個專案添加到樹以及面包屑路徑中。每個下一個專案要么作為一個孩子進入最后一個，要么通過面包屑路徑回溯到需要插入它的正確深度：
const peek = arr =>
arr[arr.length-1];
function toTree(arr) {
const tree = [];
const trail = [];
for (const item of arr) {
while ((peek(trail)?.depth ?? 0) >= item.depth) {
trail.pop();
}
const current = peek(trail)?.children ?? tree;
const treeNode = {...item, children: []};
current.push(treeNode);
trail.push(treeNode);
}
return tree;
}
const array = [
{id: 1, depth: 1, },
{id: 2, depth: 2, },
{id: 3, depth: 3, },
{id: 4, depth: 2, },
{id: 5, depth: 1, },
{id: 6, depth: 2, },
{id: 7, depth: 2, },
{id: 8, depth: 1, },
{id: 9, depth: 2, },
{id: 10, depth: 3 },
{id: 11, depth: 3 },
]
console.log(toTree(array));此解決方案克隆每個專案，以添加.children屬性。如果不需要克隆，item可以直接突變。
uj5u.com熱心網友回復：
您可以獲取最后插入的物件的陣列。
const
data = [{ id: 1, depth: 1 }, { id: 2, depth: 2 }, { id: 3, depth: 3 }, { id: 4, depth: 2 }, { id: 5, depth: 1 }, { id: 6, depth: 2 }, { id: 7, depth: 2 }, { id: 8, depth: 1 }, { id: 9, depth: 2 }, { id: 10, depth: 3 }, { id: 11, depth: 3 }],
result = data.reduce((r, { depth, ...o }) => {
r[depth - 1].push({ ...o, children: r[depth] = [] });
return r;
}, [[]])[0];
console.log(result);.as-console-wrapper { max-height: 100% !important; top: 0; }轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/477476.html
標籤：javascript 数组 树