mostrar - recorrer json javascript

Crea un árbol desde JSON

Question

Soy bastante nuevo en Javascript, he tenido algunas clases, pero todavía estoy aprendiendo sobre esto y estaba trabajando en crear un árbol a partir de un JSON. Miré otras respuestas por aquí, pero parece que no puedo entender esa reducción, recursión y jquery. Así que hice mis propias funciones.

Pero primero, mi JSON se ve así:

var data = [{
"id": 51,
"name": "root"
}, {
"id": 54,
"name": "app",
"parentId": 53
}, {
"id": 55,
"name": "text.txt",
"parentId": 54
}, {
"id": 53,
"name": "share",
"parentId": 52
}, {
"id": 52,
"name": "local",
"parentId": 51
}];

Y estas funciones procesan el objeto JSON:

var treeNode = function(nodeId, name) {
var children = [];
this.nodeId = nodeId;
this.name = name;
this.parentNode = null;
this.setParent = function(parentNode) {
this.parentNode = parentNode;
};
this.addChild = function(node){
children.push(node);
node.setParent(this);
};
};
var Tree = function() {
this.nodes = [];
this.findNodeById = function(nodeId) {
for (var i=0; i<this.nodes.length; i++) {
if (this.nodes[i].nodeId === nodeId) {
return this.nodes[i];
}
}
return null;
};
this.createNode = function(nodeId, name, parentNode) {
var node = new treeNode(nodeId, name);
if (parentNode) {
parentNode.addChild(node);
}
this.nodes.push(node);
}
};
function createTree(data) {
var tree = new Tree();
var temp = [];
for (var i=0; i<data.length; i++) {
var inputNode = data[i];
var parentNode = inputNode.parentId ? tree.findNodeById(inputNode.parentId) : null;
tree.createNode(inputNode.id, inputNode.name, parentNode);
}
return tree.nodes;
}

Luego llamo a la función: createTree (data);

Así que después de mucha depuración tratando de hacer las funciones y similares finalmente me di cuenta de que podría estar cometiendo un error en alguna parte porque ahora los padres de los nodos de 54 y 53 no se muestran y no puedo entender lo que soy haciendo mal y como puedo arreglarlo? ¿Puede alguien ayudarme por favor?

Cualquier sugerencia es muy apreciada.

Answer 1

Tu código se ve bien en general. El problema es algorítmico.
Está directamente relacionado con el orden de insertar nodos.

Porque

Tienes un árbol vacío.
Primero, insertas el nodo # 51. Ahora, tienes un árbol con nodo único # 51.
Y luego intenta insertar el nodo # 54 con parentNode # 53 ... que no existe.

aquí

var parentNode = inputNode.parentId ? tree.findNodeById(inputNode.parentId) : null;

llama a tree.findNodeById , que itera a través de su árbol, no puede encontrar el nodo 53 (todavía no está en un árbol) y devuelve null .

Por lo tanto, su segundo nodo obtiene parentNode establecido en null , en lugar del nodo # 53.

Solución

La idea básica es que siempre debe asegurarse de que, para cada nodo que se inserta, su nodo primario ya se encuentre en el árbol.

¿Cómo lograr esto?

La solución más fácil para sus datos de entrada que se me ocurre es ordenar su matriz en parentNode en orden ascendente antes de insertarla.
Garantizará que siempre inserte nodos secundarios después del nodo primario, pero solo funciona si los nodos están numerados en orden topológico .
Significa que parentId siempre es menos que id . Por ejemplo, el nodo 5 no puede tener un padre con ID 7.

Aquí, funciona correctamente para sus datos de entrada:

var data = [{
"id": 51,
"name": "root"
}, {
"id": 54,
"name": "app",
"parentId": 53
}, {
"id": 55,
"name": "text.txt",
"parentId": 54
}, {
"id": 53,
"name": "share",
"parentId": 52
}, {
"id": 52,
"name": "local",
"parentId": 51
}];
var treeNode = function(nodeId, name) {
var children = [];
this.nodeId = nodeId;
this.name = name;
this.parentNode = null;
this.setParent = function(parentNode) {
this.parentNode = parentNode;
};
this.addChild = function(node){
children.push(node);
node.setParent(this);
};
};
var Tree = function() {
this.nodes = [];
this.findNodeById = function(nodeId) {
for (var i=0; i<this.nodes.length; i++) {
if (this.nodes[i].nodeId === nodeId) {
return this.nodes[i];
}
}
return null;
};
this.createNode = function(nodeId, name, parentNode) {
var node = new treeNode(nodeId, name);
if (parentNode) {
parentNode.addChild(node);
}
this.nodes.push(node);
}
};
function createTree(data) {
// HERE, you sort your array by parentId ASC:
data = data.sort(function(a, b) {
return a.parentId - b.parentId;
});
var tree = new Tree();
var temp = [];
for (var i=0; i<data.length; i++) {
var inputNode = data[i];
var parentNode = inputNode.parentId ? tree.findNodeById(inputNode.parentId) : null;
tree.createNode(inputNode.id, inputNode.name, parentNode);
}
return tree.nodes;
}
console.log(createTree(data));

Sin embargo, si sus nodos están numerados al azar, entonces deberá implementar la clasificación topológica en lugar de la clasificación simple por parentId .

PD

Por cierto, es posible que desee utilizar el mapa de objetos en lugar de la matriz para no repetirlo en todo momento. Le dará O(n) veces la mejora - O(1) lugar de O(n) :

var Tree = function() {
this.nodes = {};
this.findNodeById = function(nodeId) {
return nodes[nodeId];
};
this.createNode = function(nodeId, name, parentNode) {
var node = new treeNode(nodeId, name);
if (parentNode) {
parentNode.addChild(node);
}
if (this.nodes[nodeId]) {
throw new Error("There is already node with ID " + nodeId + " in the tree.");
}
this.nodes[nodeId] = node;
}
};