Reputation: 131
I need some help with code in JavaScript. My goal is to write a program which will allow generating a huge binary tree.
Before compilation I specify how many levels of the tree I want, assuming that every object has two children (except the last level).
Simple visualization for levels=3:
Every object has:
-Name - The first field from the shema. Also it should include information about object number,
-Type - The second field from the shema. Information about the depth of the object,
-Properties - Some static information about an object. In my situation it is the same and it is presented below,
-Children.
I wrote some code which accurately reproduces the tree form the schema:
var levels = 3; //2^0, 2^1, 2^2
var level_description = [];
for (var i = 0; i < levels; i++) {
obj = {};
obj.level = i;
obj.amount = Math.pow(2, i);
obj.indexes = [];
if (i === 0) {
obj.indexes[0] = 0;
level_description.push(obj);
} else {
for (var j = 0; j < obj.amount; j++) {
obj.indexes[j] = obj.amount + j - 1;
}
level_description.push(obj);
}
}
console.log(level_description);
var properties = [{
"name": "trend",
"value": "true"
}, {
"name": "unit",
"value": "g"
}];
var jsonString = JSON.stringify([{
"name": "Object_" + level_description[0].indexes[0].toString(), //Object_0
"type": "level_" + level_description[0].level.toString(), //level_0,
"properties": properties,
"children": [{
"name": "Object_" + level_description[1].indexes[0].toString(), //Object_1
"type": "level_" + level_description[1].level.toString(), //level_1,
"properties": properties,
"children": [{
"name": "Object_" + level_description[2].indexes[0].toString(), //Object_3
"type": "level_" + level_description[2].level.toString(), //level_2,
"properties": properties,
"children": []
}, {
"name": "Object_" + level_description[2].indexes[1].toString(), //Object_4
"type": "level_" + level_description[2].level.toString(), //level_2,
"properties": properties,
"children": []
}]
}, {
"name": "Object_" + level_description[1].indexes[1].toString(), //Object_2
"type": "level_" + level_description[1].level.toString(), //level_1,
"properties": properties,
"children": [{
"name": "Object_" + level_description[2].indexes[2].toString(), //Object_5
"type": "level_" + level_description[2].level.toString(), //level_2,
"properties": properties,
"children": []
}, {
"name": "Object_" + level_description[2].indexes[3].toString(), //Object_6
"type": "level_" + level_description[2].level.toString(), //level_2,
"properties": properties,
"children": []
}]
}]
}]);
pm.globals.set('jsonString', jsonString);
But now I am stuck. I have trouble with making it recursive and flexible.
I uploaded an output (json tree) on my google disc: https://drive.google.com/drive/folders/1__nR-AXK7uKRBT4hZtiSWetyaobk72CX?usp=sharing
Thanks for any kind of help.
Upvotes: 3
Views: 2216
Reputation: 1402
I would suggest this solution:
var cnt = -1;
var properties = {"prop1":"a","prop2":"b"};
var MAX_LEVELS = 3;
function addNode(parent, level){
cnt = cnt + 1;
var node = {
"name": "Object_" + cnt,
"type": "level_" + level,
"properties": properties,
"children": []
};
if (level < MAX_LEVELS){
addNode(node, level + 1);
addNode(node, level + 1);
}
if (parent){
parent.children.push(node);
}
else {
return node;
}
}
let result = addNode(null, 0);
console.log(JSON.stringify(result, null, 4))
Upvotes: 1
Reputation: 622
I'm not particularly fond of this implementation as it does not maintain your TreeNode numbering system (Breadth-first) as recursive functions are by nature Depth-first so a simpler and probably better implementation would be to run a couple of for
loops, one for iterating every level and another for the level's required nodes. Nonetheless here's the recursive code:
function TreeNode(name, level, properties, children) {
this.name = name;
this.level = level;
this.properties = properties;
this.children = children;
}
var levels = 3; //2^0, 2^1, 2^2
var tree = new TreeNode("root", 0, {}, []);
var tempIndex = 0;
function generateArbitraryLevels(parent, levelsRemaining) {
// last level
if(levelsRemaining == 0) return;
var currentLevel = parent.level + 1;
parent.children.push(
new TreeNode("Object_" + tempIndex++, currentLevel, {}, [])
);
generateArbitraryLevels(parent.children[0], levelsRemaining - 1);
parent.children.push(
new TreeNode("Object_" + tempIndex++, currentLevel, {}, [])
);
generateArbitraryLevels(parent.children[1], levelsRemaining - 1);
}
generateArbitraryLevels(tree, levels);
console.log(tree);
So my approach for this kind of problems is to instantiate every node in the tree individually, and after that relate them to each other.
Check out this example:
function TreeNode(name, type, properties, children) {
this.name = name;
this.type = type;
this.properties = properties;
this.children = children;
}
var obj1 = new TreeNode("Object_1", "level_0", {a: 1}, []);
var obj2 = new TreeNode("Object_2", "level_1", {a: 1}, []);
var obj3 = new TreeNode("Object_3", "level_1", {a: 1}, []);
var obj4 = new TreeNode("Object_4", "level_2", {a: 1}, []);
var obj5 = new TreeNode("Object_5", "level_2", {a: 1}, []);
/* TREE:
1
/ \
2 3
/ \
4 5
*/
// push first level
obj1.children.push(obj2);
obj1.children.push(obj3);
// push second level
obj2.children.push(obj4);
obj2.children.push(obj5);
// Now suppose you want to "make it recursive"
// instead of number 2 having 5 as a child we are going to swap that out for 1
/* NEW TREE:
1
/ \
2 3
/ \
4 1
/ \
.. ..
*/
// remove 5
obj2.children.pop();
// push 1
obj2.children.push(obj1);
Object variables are just references to the actual object in memory so in the code above obj1 === obj2.children[1]
is true
Of course this is just an example, for more dynamism you should store a map (nodeKey -> node) and access the nodes through that.
Hope it helped
Upvotes: 2
Reputation: 382
recursive tree exemple :
function makeTree(niv, max) {
if (max === undefined) {
max = niv;
}
let obj = {
name: `n${max - niv}`,
childrens:[]
};
if (niv < 1) {
return obj;
}
let c1 = makeTree(niv -1, max);
obj.childrens.push(c1);
let c2 = makeTree(niv -1, max);
obj.childrens.push(c2);
return obj;
}
console.log(makeTree(4));
Upvotes: 1