Arbre de construction de tableau de tableau plat en javascript
J'ai un complexe fichier json que j'ai à gérer avec javascript pour le faire hiérarchique, pour ensuite construire un arbre.
Chaque entrée du json a :
id : un identifiant unique,
parentId : l'id du nœud parent (qui est 0 si le nœud est une racine de l'arbre)
niveau : le niveau de profondeur dans l'arbre
Les données json est déjà "ordonné". Je veux dire que l'entrée sera au-dessus de lui-même un nœud parent, frère ou nœud, et en vertu de lui-même un nœud enfant ou un frère nœud.
D'entrée :
{
"People": [
{
"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
}
],
"Animals": [
{
"id": "5",
"parentId": "0",
"text": "Dog",
"level": "1",
"children": null
},
{
"id": "8",
"parentId": "5",
"text": "Puppy",
"level": "2",
"children": null
},
{
"id": "10",
"parentId": "13",
"text": "Cat",
"level": "1",
"children": null
},
{
"id": "14",
"parentId": "13",
"text": "Kitten",
"level": "2",
"children": null
},
]
}
Résultat attendu :
{
"People": [
{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": [
{
"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":
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
}
],
"Animals": [
{
"id": "5",
"parentId": "0",
"text": "Dog",
"level": "1",
"children":
{
"id": "8",
"parentId": "5",
"text": "Puppy",
"level": "2",
"children": null
}
},
{
"id": "10",
"parentId": "13",
"text": "Cat",
"level": "1",
"children":
{
"id": "14",
"parentId": "13",
"text": "Kitten",
"level": "2",
"children": null
}
}
]
}
- Il y a plusieurs façons de le faire, avez-vous essayer quelque chose encore?
- Je suppose qu'un
parentId
de0
signifie que l'on n'est pas parent de l'id et devrait être le sommet de la couche. - Habituellement, ce genre de tâches requises connaissance approfondie des objets. Bonne question
InformationsquelleAutor Franck | 2013-08-02
Vous devez vous connecter pour publier un commentaire.
Il y a une solution efficace si vous utilisez une carte de la recherche. Si les parents viennent toujours avant que leurs enfants vous pouvez fusionner les deux pour des boucles. Il prend en charge de multiples racines. Il donne une erreur sur balançant les branches, mais peut être modifié pour les ignorer. On n'a pas besoin de la 3e partie de la bibliothèque. C'est, autant que je puisse en dire, la solution la plus rapide.
Si vous êtes dans la théorie de la complexité de cette solution est en Θ(n log(n)). Le récursive-filtrer la solution est en Θ(n^2), qui peut être un problème pour de grands ensembles de données.
map
qui (en théorie) est O(log n).Comme mentionné par @Sander, @Heureux de la réponse de suppose un pré-tableau trié, le suivant ne l'est pas. (Ce n'est cependant que vous ayez chargé underscore.js - si elle peut être écrite en javascript natif):
Code
JS:
HTML:
Exigences
Il suppose que les propriétés 'id' et 'parentid' indiquer l'ID et l'ID parent, respectivement. Il doit y avoir des éléments avec un parent dont l'ID est 0, sinon vous obtiendrez un tableau vide à l'arrière. Éléments orphelins et de leurs descendants sont "perdus"
http://jsfiddle.net/LkkwH/1/
else { parent['children'] = []; }
après le premier si la clause de sauvegarde pour s'assurer que chaque nœud possède un attributchildren
(ça va être vide si le nœud est un nœud feuille)tree
n'est jamais passé comme argument lors de l'appel de la fonction récursive, donc je pense que la lignetree = typeof tree !== 'undefined' ? tree : [];
peut être remplacé parlet tree = [];
null
parent_ids au lieu de 0? Edit: tant pis, j'ai eu de travail en modifiant laid: 0
àid: null
.tree
est qu'une seule fois au départ, et rien n'est fait avecparent
tree = children
, cela vous donne un tableau de tous les nœuds avecparentid = 0
. Chacun de ces nœuds est passé dans le prochain appel àunflatten
et que cette instance est modifié pour inclure ses enfants:parent['children'] = children
.Eu le même problème, mais je ne pouvais pas être certain que les données ont été triés ou non. Je ne pouvais pas utiliser un 3ème partie de la bibliothèque donc, c'est juste de la vanille Js; les données d'Entrée peuvent être prises à partir de @Etienne exemple;
JS:
JS Fiddle
Tableau plat de l'Arbre
mappedArr[mappedElem['parentid']]['children']
n'était pas comme ne pouvez pas accéder àchildren
de undefined.Manière très simple à réaliser est
( BONUS1 : les NŒUDS peuvent ou ne PEUVENT PAS ÊTRE COMMANDÉS )
( BONUS2 : PAS DE 3ÈME PARTIE DE LA BIBLIOTHÈQUE DE BESOIN, PLAINE JS )
( BONUS3 : l'Utilisateur "Elias Rabl" dit que c'est la solution la plus rapide, voir sa réponse ci-dessous )
Ici est un test, il peut vous aider à comprendre comment fonctionne la solution :
childNodes
uniquement lorsque cela est nécessaire? En supprimant la premièreforEach
et en les déplaçant à l'intérieur de la seconde?Utiliser cette ES6 approche. Fonctionne comme un charme
JS:
plus simple de la fonction liste-de-tree-lite
npm install list-to-tree-lite
listToTree(list)
source:
jsfiddle
Vous pouvez gérer cette question avec seulement deux lignes de code:
Test En Ligne (voir le navigateur de la console pour créé arbre)
Exigences:
1 - Installer lodash 4 (une bibliothèque Javascript permettant de manipuler des objets et des collections avec des méthodes performantes => comme le Linq en c#) Lodash
2 - Un flatArray comme ci-dessous:
Remercier M. Bakhshabadi
Bonne chance
Il peut être utile de package liste-de-l'arbre
Installer:
ou
Par exemple, ont de la liste:
Utilisation de la liste de paquets à l'arbre:
Résultat:
LTT
à la portée globale. 2: La mise en œuvre est sujette à caution. Je suis sûr que c'est correct mais en interne, il trie la liste (je ne pense pas nécessaire), il est inefficace dans la construction de la carte (pluck
+unique
), et il utilise des appels de fonction en interne, ce qui le rend lent pour la grande entrée.J'ai écrit un script de test pour évaluer les performances des deux plus générale solutions (ce qui signifie que l'entrée ne doit pas être triées à l'avance et que le code ne dépend pas de bibliothèques tierces), proposées par des utilisateurs shekhardtu (voir la réponse) et FurkanO (voir la réponse).
http://playcode.io/316025?tabs=console&script.js&sortie
FurkanO la solution semble être la plus rapide.
C'est une proposition de non ordonnée d'éléments. Cette fonction fonctionne avec une seule boucle et avec une table de hachage et recueille tous les éléments avec leur
id
. Si un nœud racine est trouvé, alors l'objet est ajouté à la matrice de résultats.JS:
CSS:
Voici une simple fonction d'assistance que j'ai créé modélisé d'après les réponses ci-dessus, qui sont adaptés à une Babel de l'environnement:
aussi le faire avec lodashjs(v4.x)
J'aime @WilliamLeung du pur JavaScript solution, mais parfois vous avez besoin de faire des changements dans le tableau existant pour garder une référence à l'objet.
Exapmle:
https://jsfiddle.net/kqw1qsf0/17/
JS:
Vous pourriez avoir un coup d'oeil au mnp paquet arbre-util
Il peut également être très pratique si vous voulez charger les données à partir de SQL DB tableau de données.
Vous pouvez également facilement ajouter des données supplémentaires pour les nœuds dans la création de l'arbre.
Avertissement, j'ai fait ce package.
Vous pouvez utiliser ce "treeify" paquet de Github ici ou NPM.
Installation:
$ npm install --save-dev treeify-js
J'ai eu le même problème il ya quelques jours quand ont pour afficher l'arborescence des dossiers de tableau plat. Je ne vois pas de solution à la Machine ici, donc j'espère que ce sera utile.
Dans mon cas principal parent seul, aussi rawData tableau n'avez pas à être triés. Des Solutions sur la base de préparer temp objet comme
{parentId: [child1, child2, ...] }
exemple de données brutes
def de Dossier
SOLUTION: Fonction qui retourne l'arbre de structure pour le plat argument
Ici est une version modifiée de Steven Harris qui est clair ES5, et retourne un objet à la clé sur l'id plutôt que de retourner un tableau de nœuds à la fois le haut niveau et pour les enfants.
Ceci est une version modifiée de la version ci-dessus qui fonctionne avec de multiples éléments racine, j'utilise le Guid pour mon id et parentIds donc dans l'INTERFACE utilisateur qui crée entre eux, je les coder en dur les éléments racine à quelque chose comme 0000000-00000-00000-ARBRE-RACINE-ÉLÉMENT
var arbre = unflatten(enregistrements, "l'ARBRE-RACINE-ÉLÉMENT");
Copié à partir de l'Internet
http://jsfiddle.net/stywell/k9x2a3g6/
Vous pouvez utiliser npm package array-à-arbre https://github.com/alferov/array-to-tree.
C'est de convertir un simple tableau de nœuds (avec des pointeurs vers les nœuds parents) à un ensemble de données de la structure.
Résout un problème avec la conversion de récupéré à partir d'une base de données des ensembles de données à un ensemble de structure de données (c'est à dire arborescence de navigation).
Utilisation:
C'est un vieux thread mais j'ai pensé à une mise à jour ne fait jamais de mal, avec ES6 que vous pouvez faire:
espère que cela aide quelqu'un
c'est ce que j'ai utilisé dans un projet react
utilisation:
de sortie:
Essayer cette
Tester sur Jsfiddle