Xây dựng mảng cây từ mảng phẳng trong JavaScript

Chúng ta có một tệp JSON phức tạp cần xử lý bằng JavaScript để làm cho nó phân cấp, nhằm sau này xây dựng một cây.

Mỗi mục của mảng JSON có:

• id – một id duy nhất,
• parentId – id của nút cha (là 0 nếu nút là gốc của cây)
• level – cấp độ độ sâu trong cây

Dữ liệu JSON đã được "sắp xếp", nghĩa là một mục sẽ có phía trên nó một nút cha hoặc nút anh em, và phía dưới nó một nút con hoặc nút anh em.

Mảng đầu vào là:

const arr = [
  { "id": "12", "parentId": "0", "text": "Man", "level": "1", "children": null },
  { "id": "6", "parentId": "12", "text": "Boy", "level": "2", "children": null },
  { "id": "7", "parentId": "12", "text": "Other", "level": "2", "children": null },
  { "id": "9", "parentId": "0", "text": "Woman", "level": "1", "children": null },
  { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": null }
];

Và đầu ra mong đợi là:

const output = [
  {
    "id": "12", "parentId": "0", "text": "Man", "level": "1",
    "children": [
      { "id": "6", "parentId": "12", "text": "Boy", "level": "2", "children": [] },
      { "id": "7", "parentId": "12", "text": "Other", "level": "2", "children": [] }
    ]
  },
  {
    "id": "9", "parentId": "0", "text": "Woman", "level": "1",
    "children": [
      { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": [] }
    ]
  }
];

Ví dụ

Mã thực hiện:

const arr = [
  { "id": "12", "parentId": "0", "text": "Man", "level": "1", "children": null },
  { "id": "6", "parentId": "12", "text": "Boy", "level": "2", "children": null },
  { "id": "7", "parentId": "12", "text": "Other", "level": "2", "children": null },
  { "id": "9", "parentId": "0", "text": "Woman", "level": "1", "children": null },
  { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": null }
];
const listToTree = (arr = []) => {
  let map = {}, node, res = [], i;
  for (i = 0; i < arr.length; i += 1) {
    map[arr[i].id] = i;
    arr[i].children = [];
  }
  for (i = 0; i < arr.length; i += 1) {
    node = arr[i];
    if (node.parentId !== "0") {
      arr[map[node.parentId]].children.push(node);
    } else {
      res.push(node);
    }
  }
  return res;
};
console.log(JSON.stringify(listToTree(arr), undefined, 4));

Kết quả

Kết quả trong console:

[
  {
    "id": "12",
    "parentId": "0",
    "text": "Man",
    "level": "1",
    "children": [
      { "id": "6", "parentId": "12", "text": "Boy", "level": "2", "children": [] },
      { "id": "7", "parentId": "12", "text": "Other", "level": "2", "children": [] }
    ]
  },
  {
    "id": "9",
    "parentId": "0",
    "text": "Woman",
    "level": "1",
    "children": [
      { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": [] }
    ]
  }
]