I have an array of topics each linked to a parent topic. So, basically what I want to do is form an array with all the children topics nested under the parent. So if I had an table of topics looking like this:
| id | name | parent_id |
|---|---|---|
| 1 | Topic 1 | null |
| 2 | Topic 2 | 1 |
| 3 | Topic 3 | 2 |
| 4 | Topic 4 | 2 |
| 5 | Topic 5 | 4 |
And if the json array looks like this:
[
{ id: 1, name: "Topic 1", parent_id: null },
{ id: 2, name: "Topic 2", parent_id: 1 },
{ id: 3, name: "Topic 3", parent_id: 2 },
{ id: 4, name: "Topic 4", parent_id: 2 },
{ id: 5, name: "Topic 5", parent_id: 4 },
]
I want the output array to look like this:
[
{
id: 1,
name: "Topic 1",
children: [
{
id: 2,
name: "Topic 2",
children: [
{ id: 3, name: "Topic 3", children: [] },
{
id: 4,
name: "Topic 4",
children: [{ id: 5, name: "Topic 5", children: [] }],
},
],
},
],
},
]
CodePudding user response：
We can achieve this with a simple recursive function and iterate from the top of your list of objects.
function BuildChild(data, currentChild){
//Creating current child object
var child = {};
child.id = currentChild.id;
child.name = currentChild.name;
child.children = [];
//Looking for childrens in all input data
var currentChildren = data.filter(item => item.parent_id == child.id);
if(currentChildren.length > 0){
currentChildren.forEach(function(item){
//Iterating threw children and calling the recursive function
//Adding the result to our current children
child.children.push(BuildChild(data,item));
});
}
return child; }
You can then call it while getting the "top parent" of your list :
BuildChild(data, data.find(child => child.parent_id == null))
Snippet with result :
function BuildChild(data, currentChild){
//Creating current child object
var child = {};
child.id = currentChild.id;
child.name = currentChild.name;
child.children = [];
//Looking for childrens in all input data
var currentChildren = data.filter(item => item.parent_id == child.id);
if(currentChildren.length > 0){
currentChildren.forEach(function(item){
//Iterating threw children and calling the recursive function
//Adding the result to our current children
child.children.push(BuildChild(data,item));
});
}
return child;
}
var data = [
{ id: 1, name: "Topic 1", parent_id: null },
{ id: 2, name: "Topic 2", parent_id: 1 },
{ id: 3, name: "Topic 3", parent_id: 2 },
{ id: 4, name: "Topic 4", parent_id: 2 },
{ id: 5, name: "Topic 5", parent_id: 4 },
]
console.log(BuildChild(data, data.find(child => child.parent_id == null)))CodePudding user response：
Get which IDs are at the root level, i.e. with no parents. For those IDs, recursively build their grouped data, similar to writing a depth-first search recursion.
Reading the code will probably be easier:
// Helper function, returns {ID -> set of child IDs}
function getAdjMatrix(data) {
const adjMatrix = new Map();
for (const entry of data) {
if (!adjMatrix.has(entry.id)) {
adjMatrix.set(entry.id, new Set());
}
if (entry.parent_id !== null) {
if (!adjMatrix.has(entry.parent_id)) {
adjMatrix.set(entry.parent_id, new Set());
}
adjMatrix.get(entry.parent_id).add(entry.id);
}
}
return adjMatrix;
}
// Helper function, returns grouped data for the given ID
function getGroupedDataForId(id, idToData, adjMatrix, processedIds) {
if (!idToData.has(id) || !adjMatrix.has(id) || processedIds.has(id)) {
return null;
}
const result = idToData.get(id);
result.children = [];
// Add children
for (const childId of adjMatrix.get(id)) {
const childIdData = getGroupedDataForId(
/*id=*/ childId, idToData, adjMatrix, processedIds);
if (childIdData !== null) {
result.children.push(childIdData);
}
processedIds.add(childId);
}
processedIds.add(id);
return result;
}
// Returns the final grouped data
function getGroupedData(data) {
// A map of ID to its data
const idToData = new Map(data.map(entry => [entry.id, entry]));
// Adjacency matrix
// Represented by {id -> set of children}
const adjMatrix = getAdjMatrix(data);
// Root IDs (no parents)
const rootIds =
data.filter(entry => entry.parent_id === null).map(entry => entry.id);
// IDs that have been grouped with children
const processedIds = new Set();
// Final result
const result = [];
// Recursively add IDs
for (const rootId of rootIds) {
groupedData = getGroupedDataForId(
/*id=*/ rootId, idToData, adjMatrix, processedIds);
if (groupedData !== null) {
result.push(groupedData);
}
}
return result;
}
// Test
const data = [
{'id': 1, 'name': 'Topic 1', 'parent_id': null},
{'id': 2, 'name': 'Topic 2', 'parent_id': 1},
{'id': 3, 'name': 'Topic 3', 'parent_id': 2},
{'id': 4, 'name': 'Topic 4', 'parent_id': 2},
{'id': 5, 'name': 'Topic 5', 'parent_id': 4},
{'id': 6, 'name': 'Topic 6', 'parent_id': null},
{'id': 7, 'name': 'Topic 7', 'parent_id': 1},
];
console.log(JSON.stringify(getGroupedData(data)));