将二进制树编码为Json

Question

I've stored a bunch of data in my database to draw a binary tree in a html canvas

---

Idx / Name

1 Apple

2 Bee

3 Cafe

4 Diamond

8 East

9 Game

16 Hobby

---

Here, idx represents the location of items in a binary tree. So the data above looks something like this in a tree

---

               1.Apple
               /     \
            2.Bee    3.Cafe
             /
      4.Diamond
       /      \
  8.East    9.Game
     /
16.Hobby

Now, I need to encode that database rows into a json format:

{
    id: "1",
    name: "Apple",
    data: {},
    children: [{
                   id: "2",
                   name: "Bee",
                   data: {},
                   children: [{
                       id: "4",
                       name: "Diamond",
                       data: {},
                       children: [{
                         // East/Game/Hobby comes here in the same manner...
                       }]
                   }]
               },
               {
                   id: "3",
                   name: "Cafe",
                   data: {},
                   children: [] // has no children
               }]
}

What I've tried was creating an array of arrays and going through all the values descending order by grab a vale and put it into its parent array and remove it from the array. So, my pseudo code was something like this...

nodeArray = [1,2,3,4,8,9,16];  <-each node is an object with needed data contained.
treeArray = [........]  <- arrays with key=>each index / value=>empty
while(nodeArray size is larger than 1) // 1 = the top most value 
{
    grab the last node from nodeArray
    parent_idx = (int)(last one id / 2)
    push the last node into the treeArray[parent_idx]
    pop the used index
}

Then, I will have treeArray something like this

treeArray = [
  1:[2,3]
  2:[4]
  4:[8,9]
  8:[16]
]

...this is not the array-converted binary tree I was looking for.

So, I need to go through treeArray in desc order and relocate them... Yup. I know I'm getting messed up here :( It's getting more complicated and harder to understand.

Would be there more elegant and simpler way to do it? :(

Answer 1

I ended up using javascript and loop through each node and calling the following function

var objlist = {};
function buildTree(id, parent_id, data)
{
   if(id in objlist) alert("It already exists!");
   objlist[id] = { id: id, data: data, children: [] };
   if (parent_id in objlist)
   {
      objlist[parent_id].children.push(objlist[id]);
   }
}

where parent_id is id/2.