I am fairly new to Javascript, I've had some classes, but I am still learning about it and I was working on making a tree from a JSON. I looked at other answers over here, but I just can't seem to understand that reduce, recursion and jquery thingys. So I made my own functions.
But first, my JSON looks like this:
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
}];
And these functions process the JSON object:
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;
}
Then I call the function: createTree(data);
So after much debugging trying to make the functions and the like I finally realized that I may be making a mistake somewhere because right now the parents for nodes for 54 and 53 are not showing and I just can't wrap my head around what I am doing wrong and how can I fix it? Can somebody help me please?
Any suggestions are very much appreciated.
What is jsTree? jsTree is jquery plugin, that provides interactive trees. It is absolutely free, open source and distributed under the MIT license. jsTree is easily extendable, themable and configurable, it supports HTML & JSON data sources and AJAX loading.
Use your JSON REST URL to visualize. Click on the Load URL button, Enter URL and Submit. Users can also visualize JSON in graph by uploading the JSON file. JSON Visualizer works well on Windows, MAC, Linux, Chrome, Firefox, Edge, and Safari.
JSON structure As described above, JSON is a string whose format very much resembles JavaScript object literal format. You can include the same basic data types inside JSON as you can in a standard JavaScript object — strings, numbers, arrays, booleans, and other object literals.
Your code looks good in general. The problem is algorithmical.
It is directly related to the order of inserting nodes.
You have an empty tree.
First, you insert node #51. Now, you have a tree with single node #51.
And then you try to insert node #54 with parentNode #53...which doesn't exist.
Here
var parentNode = inputNode.parentId ? tree.findNodeById(inputNode.parentId) : null;
you call tree.findNodeById
, which iterates through your tree, cannot find node 53 (it is not in a tree yet), and returns null
.
Thus, your second node gets parentNode
set to null
, instead of node #53.
The basic idea is that you always need to ensure that for every node being inserted its parent node is already in the tree.
The easiest solution for your input data which comes to my mind is to sort your array on parentNode
in ascending order before inserting.
It will guarantee that you always insert child nodes after parent node, but it only works if nodes are numbered in topological order.
It means that parentId
is always less than id
. For instance, node 5 cannot have a parent with ID 7.
Here, it works properly for your input data:
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));
However, if your nodes are numbered randomly, then you will need to implement topological sorting instead of simple sorting by parentId
.
By the way, you may want to use object map instead of array in order to not iterate through it every time. It will give O(n)
times improvement - O(1)
instead of 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;
}
};
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With