1d array into binary tree

Question

 nodeArray = [  3,  3,  7,   6,   6,   7,    15,    10,   10,    14,    13,    13,    14,    15,    23,    18,    18,    22,    21,    21,    22,    23,    0  ];

nodes = [];
links = [];

function  left(i) {
  return 2*i + 1;
}
function  right(i) {
  return 2*i + 2;
}
function  parent(i) {
  console.log("Parent =" + (i-1)/2);
  return (i-1)/2;
}

var index = 0;
do{
  if (index === 0) {
    var node = {
      'value': nodeArray[index],
      'child1_index': left(index),
      'child1_value': nodeArray[left(index)],
      'child2_index': right(index),
      'child2_value': nodeArray[right(index)],
      'parent_index' : 'null',
      'parent_value' : 'null'
    };
  } else {
    var node = {
      'value': nodeArray[index],
      'child1_index': left(index),
      'child1_value': nodeArray[left(index)],
      'child2_index': right(index),
      'child2_value': nodeArray[right(index)],
      'parent_index' :parent(index),
      'parent_value' : nodeArray[parent(index)],
      'index' : index
    };
  }
  nodes.push(node);
  index++;
} while (index != nodeArray.length)
console.log(nodes);

I have written the above code for future turning it into a binary tree with d3.js library, unfortunately all my parent node values (which are apparently given by any nodes (index -1 )/ 2. give numbers like 5.5 etc being half the index or something. which obviously wont work. Some nodes give full integers then some do not.

example console output for one of my node objects. which looks right

Node1:
parent_index:0
parent_value:3

example of other node objects. which dont look right are

Node2:
parent_index:0.5
parent_value:undefined

Here is a jsfiddle if anyone's interested http://jsfiddle.net/mryfw095/5/

I don't able to to understand what exactly you want as your result but for getting whole number use Math.floor() or Math.ceil() function. — Abdul Rehman
– Abdul Rehman, Commented Nov 20, 2015 at 12:41
im trying to create a binary tree from a 1d array and the theory says the parent of a node is its index (value - 1) / 2. which for me ends with a lot of non-integers. so ill try that approach and see what happens — Spungey
– Spungey, Commented Nov 20, 2015 at 14:07

Matt · Accepted Answer · 2015-11-20 12:58:08Z

1

I think you just want your parent function to round down.

function  parent(i) {
  console.log("Parent =" + Math.floor((i-1)/2));
  return Math.floor((i-1)/2);
}

answered Nov 20, 2015 at 12:58

Matt

1,03611 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Spungey Over a year ago

yes thats all i was thinking, as the theory i read always says to use (i-1)/2 for the parent index but they never discuss non-integers. Ill give your idea a try and see what becomes of my tree. thanks

Spungey Over a year ago

hmm i end up with a lot of undefined child nodes with this. hmm

Spungey Over a year ago

as well they end up with indices that dont exist

Collectives™ on Stack Overflow

1d array into binary tree

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related