J'ai le tableau suivant (qui provient en fait d'un service backend):
// Get roots first
const roots: NestedItem[] = flat
.filter(item => !item.parentId)
.map((item): NestedItem => {
return { id: item.id, name: item.name, root: true }
});
// Add "children" to those roots
const treeData = roots.map(node => {
const children = flat
.filter(item => item.parentId === node.id)
.map(item => {
return { id: item.id, name: item.name }
});
return {
...node,
children,
count: node.count ? node.count + children.length : children.length
}
});
où Item est:
interface NestedItem {
id: string;
name: string;
root?: boolean;
count?: number;
children?: NestedItem[];
}
6 Réponses :
Ne faire aucune hypothèse sur l'ordre du tableau aplati ou sur la profondeur d'un objet imbriqué:
Array.prototype.reduce est suffisamment flexible pour obtenir cela terminé. Si vous n'êtes pas familier avec Array.prototype.reduce , je recommande lecture de ceci . Vous pouvez accomplir cela en procédant comme suit.
J'ai deux fonctions qui reposent sur la récursivité ici: findParent et checkLeftOvers . findParent tente de trouver le parent des objets et retourne true ou false selon qu'il le trouve. Dans mon réducteur, j'ajoute la valeur actuelle au tableau des restes si findParent renvoie false . Si findParent renvoie true , j'appelle checkLeftOvers pour voir si un objet dans mon tableau de gauche est l'enfant de l'objet findParent vient d'être ajouté.
Remarque: j'ai ajouté {id: 'b2-2-1', name: 'Item 2-2-1', parentId: 'b2-2'} au tableau flat pour démontrer que cela ira aussi loin que vous le souhaitez. J'ai également réorganisé flat pour démontrer que cela fonctionnera également dans ce cas. J'espère que cela vous aidera.
const flat = [
{ id: 'a2', name: 'Item 1', parentId: 'a' },
{ id: 'b2-2-1', name: 'Item 2-2-1', parentId: 'b2-2'},
{ id: 'a1', name: 'Item 1', parentId: 'a' },
{ id: 'a', name: 'Root 1', parentId: null },
{ id: 'b', name: 'Root 2', parentId: null },
{ id: 'c', name: 'Root 3', parentId: null },
{ id: 'b1', name: 'Item 1', parentId: 'b' },
{ id: 'b2', name: 'Item 2', parentId: 'b' },
{ id: 'b2-1', name: 'Item 2-1', parentId: 'b2' },
{ id: 'b2-2', name: 'Item 2-2', parentId: 'b2' },
{ id: 'b3', name: 'Item 3', parentId: 'b' },
{ id: 'c1', name: 'Item 1', parentId: 'c' },
{ id: 'c2', name: 'Item 2', parentId: 'c' }
];
function checkLeftOvers(leftOvers, possibleParent){
for (let i = 0; i < leftOvers.length; i++) {
if(leftOvers[i].parentId === possibleParent.id) {
delete leftOvers[i].parentId
possibleParent.children ? possibleParent.children.push(leftOvers[i]) : possibleParent.children = [leftOvers[i]]
possibleParent.count = possibleParent.children.length
const addedObj = leftOvers.splice(i, 1)
checkLeftOvers(leftOvers, addedObj[0])
}
}
}
function findParent(possibleParents, possibleChild) {
let found = false
for (let i = 0; i < possibleParents.length; i++) {
if(possibleParents[i].id === possibleChild.parentId) {
found = true
delete possibleChild.parentId
if(possibleParents[i].children) possibleParents[i].children.push(possibleChild)
else possibleParents[i].children = [possibleChild]
possibleParents[i].count = possibleParents[i].children.length
return true
} else if (possibleParents[i].children) found = findParent(possibleParents[i].children, possibleChild)
}
return found;
}
const nested = flat.reduce((initial, value, index, original) => {
if (value.parentId === null) {
if (initial.left.length) checkLeftOvers(initial.left, value)
delete value.parentId
value.root = true;
initial.nested.push(value)
}
else {
let parentFound = findParent(initial.nested, value)
if (parentFound) checkLeftOvers(initial.left, value)
else initial.left.push(value)
}
return index < original.length - 1 ? initial : initial.nested
}, {nested: [], left: []})
console.log(nested)
désolé pour l'acceptation tardive, je me suis éloigné de cela pendant un moment. Maintenant, revenons dessus. Je vous remercie! "Ne faire aucune hypothèse" est toujours la meilleure hypothèse :)
Heureux d'avoir pu aider. Bon codage :)
En supposant que le tableau d'éléments plats est toujours trié comme dans votre cas (les nœuds parents sont triés avant les nœuds enfants) . Le code ci-dessous devrait faire le travail.
Tout d'abord, je construis l'arborescence sans les propriétés count en utilisant la réduction sur le tableau pour créer une carte pour garder une trace de chaque nœud et relier les parents aux enfants:
let roots: NestedItem[] = Object.keys(nestedItemMap)
.map((key: string): NestedItem => nestedItemMap[key])
.reverse()
.map((item: NestedItem): NestedItem => {
if(item.children != undefined){
item.count = item.children
.map((child: NestedItem): number => {
return 1 + (child.count != undefined ? child.count : 0);
})
.reduce((a, b) => a + b, 0);
}
return item;
})
.filter((item: NestedItem): boolean => item.root)
.reverse();
Le fait que le nœud parent passe toujours en premier lors de la réduction du tableau garantit que le nœud parent est disponible dans nestedItemMap lors de la construction des enfants.
Ici, nous avons les arbres, mais sans les propriétés count :
let roots: NestedItem[] = Object.keys(nestedItemMap)
.map((key: string): NestedItem => nestedItemMap[key])
.filter((item: NestedItem): boolean => item.root);
Pour avoir le count code> propriétés remplies, je préférerais personnellement effectuer une recherche en profondeur après la commande sur les arbres. Mais dans votre cas, grâce aux noms des identifiants des nœuds (triés, les identifiants des nœuds parents viennent en premier). Vous pouvez les calculer en utilisant:
type NestedItemMap = { [nodeId: string]: NestedItem };
let nestedItemMap: NestedItemMap = flat
.reduce((nestedItemMap: NestedItemMap, item: Item): NestedItemMap => {
// Create the nested item
nestedItemMap[item.id] = {
id: item.id,
name: item.name
}
if(item.parentId == null){
// No parent id, it's a root node
nestedItemMap[item.id].root = true;
}
else{
// Child node
let parentItem: NestedItem = nestedItemMap[item.parentId];
if(parentItem.children == undefined){
// First child, create the children array
parentItem.children = [];
parentItem.count = 0;
}
// Add the child node in it's parent children
parentItem.children.push(
nestedItemMap[item.id]
);
parentItem.count++;
}
return nestedItemMap;
}, {});
Je viens d'inverser le tableau pour obtenir tous les enfants en premier (comme dans un DFS post-ordre), et calculer le count code> valeur.
Le dernier revers est ici juste pour être trié comme dans votre question :).
Si vous avez autant d'informations à l'avance, vous pouvez construire l'arborescence à l'envers beaucoup plus facilement. Étant donné que vous connaissez si bien la forme de l'entrée et que leurs relations sont clairement définies, vous pouvez facilement la séparer en plusieurs tableaux et la construire de bas en haut:
function buildTree(arr: Item[]): NestedItem[] {
/* first split the input into separate arrays based on their nested level */
const roots = arr.filter(r => /^\w{1}$/.test(r.id));
const levelOne = arr.filter(r => /^\w{1}\d{1}$/.test(r.id));
const levelTwo = arr.filter(r => /^\w{1}\d{1}-\d{1}$/.test(r.id));
/* then create the bottom most level based on their relationship to their parent*/
const nested = levelOne.map(item => {
const children = levelTwo.filter(c => c.parentId === item.id);
if (children) {
return {
...item,
count: children.length,
children
};
} else return item;
});
/* and finally do the same with the root items and return the result */
return roots.map(item => {
const children = nested.filter(c => c.parentId === item.id);
if (children) {
return {
...item,
count: children.length,
children,
root: true
};
} else return { ...item, root: true };
});
}
Ce n'est peut-être pas le plus performant solution, et il faudrait quelques ajustements en fonction de la forme attendue de l'entrée, mais c'est une solution propre et lisible.
Vous pouvez utiliser une approche standard pour un arbre qui prend une seule boucle et stocke la relation entre l'enfant et le parent et entre le parent et l'enfant.
Pour avoir des propriétés racine, vous avez besoin d'une vérification supplémentaire.
Ensuite, adoptez une approche itérative et récursive pour obtenir le nombre.
.as-console-wrapper { max-height: 100% !important; top: 0; }
var data = [{ id: 'a', name: 'Root 1', parentId: null }, { id: 'b', name: 'Root 2', parentId: null }, { id: 'c', name: 'Root 3', parentId: null }, { id: 'a1', name: 'Item 1', parentId: 'a' }, { id: 'a2', name: 'Item 1', parentId: 'a' }, { id: 'b1', name: 'Item 1', parentId: 'b' }, { id: 'b2', name: 'Item 2', parentId: 'b' }, { id: 'b3', name: 'Item 3', parentId: 'b' }, { id: 'c1', name: 'Item 1', parentId: 'c' }, { id: 'c2', name: 'Item 2', parentId: 'c' }, { id: 'b2-1', name: 'Item 2-1', parentId: 'b2' }, { id: 'b2-2', name: 'Item 2-2', parentId: 'b2' },],
tree = function (data, root) {
function setCount(object) {
return object.children
? (object.count = object.children.reduce((s, o) => s + 1 + setCount(o), 0))
: 0;
}
var t = {};
data.forEach(o => {
Object.assign(t[o.id] = t[o.id] || {}, o);
t[o.parentId] = t[o.parentId] || {};
t[o.parentId].children = t[o.parentId].children || [];
t[o.parentId].children.push(t[o.id]);
if (o.parentId === root) t[o.id].root = true; // extra
});
setCount(t[root]); // extra
return t[root].children;
}(data, null);
console.log(tree);
peut-être que cela peut vous aider, l'entrée est plate obj
nestData = (data, parentId = '') => {
return data.reduce((result, fromData) => {
const obj = Object.assign({}, fromData);
if (parentId === fromData.parent_id) {
const children = this.nestData(data, fromData.id);
if (children.length) {
obj.children = children;
} else {
obj.userData = [];
}
result.push(obj);
}
return result;
}, []);
};
Ceci est vraisemblablement tiré du code pour une tâche différente, mais liée. Il faudrait le nettoyer pour résoudre ce problème. Autonome, vous devrez supprimer this de l'appel récursif à nestData . Vous devrez changer parent_id en parentId et comme userData n'a rien à voir avec cette question, le bloc else Peut être enlevé. Le plus gros manque, cependant, est qu'il n'inclut pas les propriétés count ou root demandées. root est facile, mais count prendrait du travail. Une approche similaire se trouve dans la dernière mise à jour de une autre réponse .
Une autre approche pourrait ressembler à ceci:
.as-console-wrapper {min-height: 100% !important; top: 0}
const countKids = (nodes) =>
nodes.length + nodes.map(({children = []}) => countKids(children)).reduce((a, b) => a + b, 0)
const makeForest = (id, xs) =>
xs .filter (({parentId}) => parentId == id)
.map (({id, parentId, ...rest}) => {
const kids = makeForest (id, xs)
return {id, ...rest, ...(kids .length ? {count: countKids (kids), children: kids} : {})}
})
const nest = (flat) =>
makeForest (null, flat)
.map ((node) => ({...node, root: true}))
const flat = [{id: "a", name: "Root 1", parentId: null}, {id: "b", name: "Root 2", parentId: null}, {id: "c", name: "Root 3", parentId: null}, {id: "a1", name: "Item 1", parentId: "a"}, {id: "a2", name: "Item 1", parentId: "a"}, {id: "b1", name: "Item 1", parentId: "b"}, {id: "b2", name: "Item 2", parentId: "b"}, {id: "b2-1", name: "Item 2-1", parentId: "b2"}, {id: "b2-2", name: "Item 2-2", parentId: "b2"}, {id: "b3", name: "Item 3", parentId: "b"}, {id: "c1", name: "Item 1", parentId: "c"}, {id: "c2", name: "Item 2", parentId: "c"}]
console .log (nest (flat))
La fonction principale ( makeForest ) trouve tous les enfants dont les identifiants correspondent à la cible (initialement null ) puis fait de manière récursive les identifiants de ces enfants .
La seule complexité ici est de ne pas inclure count ou children si les enfants d'un nœud sont vides. Si leur inclusion ne pose pas de problème, cela peut être simplifié.