recursion - Javascript: Recursively count number of children in a tree - Stack Overflow

admin管理员组

文章数量:1401509

We have a JSON tree structure which maintains the children of a specific node. This children parameter is either Undefined (no children) or an array.

I want to pute the score of a node, which is the sum of the scores of the children nodes. And a node without children has a score of one.

This seemed pretty straightforward to me, however only the last node from the leaf-nodes are updated correctly, the rest show as NaN. I'm not sure where Undefined/NaN is being introduced, I suspect it might be due to how JS handles references within recursion?

function updateScore(n) {
  if (n.children == undefined) return 1;
  n.children.forEach(function(c){
    var r = updateScore(c);  
    //if (!r) console.log(n);
    n.score += r;
  });
}
updateScore(sparent);

The data is as follows:

var sparent = {"id":"src","score":0,"children":[{"id":0,"score":0,"children":[{"id":14,"score":0}]},{"id":2,"score":0},{"id":4,"score":0},{"id":11,"score":0},{"id":17,"score":0,"children":[{"id":31,"score":0}]},{"id":18,"score":0},{"id":23,"score":0,"children":[{"id":13,"score":0,"children":[{"id":10,"score":0},{"id":21,"score":0,"children":[{"id":16,"score":0}]},{"id":82,"score":0,"children":[{"id":22,"score":0},{"id":75,"score":0}]},{"id":91,"score":0}]},{"id":48,"score":0,"children":[{"id":70,"score":0,"children":[{"id":46,"score":0},{"id":74,"score":0}]},{"id":97,"score":0,"children":[{"id":25,"score":0}]}]}]},{"id":28,"score":0,"children":[{"id":85,"score":0}]},{"id":30,"score":0,"children":[{"id":24,"score":0,"children":[{"id":26,"score":0},{"id":53,"score":0,"children":[{"id":45,"score":0}]},{"id":76,"score":0,"children":[{"id":38,"score":0},{"id":62,"score":0},{"id":66,"score":0}]},{"id":93,"score":0,"children":[{"id":1,"score":0},{"id":56,"score":0}]}]},{"id":78,"score":0,"children":[{"id":50,"score":0,"children":[{"id":15,"score":0},{"id":67,"score":0}]}]},{"id":94,"score":0}]},{"id":36,"score":0},{"id":39,"score":0,"children":[{"id":35,"score":0,"children":[{"id":73,"score":0},{"id":83,"score":0,"children":[{"id":3,"score":0}]}]}]},{"id":41,"score":0,"children":[{"id":5,"score":0},{"id":32,"score":0}]},{"id":43,"score":0,"children":[{"id":20,"score":0,"children":[{"id":89,"score":0,"children":[{"id":52,"score":0}]}]},{"id":27,"score":0},{"id":86,"score":0,"children":[{"id":6,"score":0}]},{"id":98,"score":0,"children":[{"id":54,"score":0},{"id":59,"score":0},{"id":65,"score":0,"children":[{"id":8,"score":0},{"id":47,"score":0}]},{"id":79,"score":0}]}]},{"id":64,"score":0},{"id":71,"score":0,"children":[{"id":19,"score":0},{"id":51,"score":0,"children":[{"id":57,"score":0,"children":[{"id":29,"score":0,"children":[{"id":49,"score":0}]},{"id":60,"score":0,"children":[{"id":34,"score":0}]}]},{"id":61,"score":0,"children":[{"id":63,"score":0},{"id":72,"score":0,"children":[{"id":9,"score":0},{"id":37,"score":0}]}]},{"id":90,"score":0}]},{"id":92,"score":0,"children":[{"id":96,"score":0,"children":[{"id":55,"score":0,"children":[{"id":12,"score":0},{"id":69,"score":0}]},{"id":80,"score":0}]}]}]},{"id":77,"score":0,"children":[{"id":81,"score":0,"children":[{"id":40,"score":0}]}]},{"id":84,"score":0,"children":[{"id":7,"score":0,"children":[{"id":33,"score":0,"children":[{"id":42,"score":0},{"id":95,"score":0}]}]},{"id":44,"score":0,"children":[{"id":58,"score":0}]}]},{"id":87,"score":0,"children":[{"id":68,"score":0}]},{"id":88,"score":0},{"id":99,"score":0}]};

We have a JSON tree structure which maintains the children of a specific node. This children parameter is either Undefined (no children) or an array.

I want to pute the score of a node, which is the sum of the scores of the children nodes. And a node without children has a score of one.

This seemed pretty straightforward to me, however only the last node from the leaf-nodes are updated correctly, the rest show as NaN. I'm not sure where Undefined/NaN is being introduced, I suspect it might be due to how JS handles references within recursion?

function updateScore(n) {
  if (n.children == undefined) return 1;
  n.children.forEach(function(c){
    var r = updateScore(c);  
    //if (!r) console.log(n);
    n.score += r;
  });
}
updateScore(sparent);

The data is as follows:

var sparent = {"id":"src","score":0,"children":[{"id":0,"score":0,"children":[{"id":14,"score":0}]},{"id":2,"score":0},{"id":4,"score":0},{"id":11,"score":0},{"id":17,"score":0,"children":[{"id":31,"score":0}]},{"id":18,"score":0},{"id":23,"score":0,"children":[{"id":13,"score":0,"children":[{"id":10,"score":0},{"id":21,"score":0,"children":[{"id":16,"score":0}]},{"id":82,"score":0,"children":[{"id":22,"score":0},{"id":75,"score":0}]},{"id":91,"score":0}]},{"id":48,"score":0,"children":[{"id":70,"score":0,"children":[{"id":46,"score":0},{"id":74,"score":0}]},{"id":97,"score":0,"children":[{"id":25,"score":0}]}]}]},{"id":28,"score":0,"children":[{"id":85,"score":0}]},{"id":30,"score":0,"children":[{"id":24,"score":0,"children":[{"id":26,"score":0},{"id":53,"score":0,"children":[{"id":45,"score":0}]},{"id":76,"score":0,"children":[{"id":38,"score":0},{"id":62,"score":0},{"id":66,"score":0}]},{"id":93,"score":0,"children":[{"id":1,"score":0},{"id":56,"score":0}]}]},{"id":78,"score":0,"children":[{"id":50,"score":0,"children":[{"id":15,"score":0},{"id":67,"score":0}]}]},{"id":94,"score":0}]},{"id":36,"score":0},{"id":39,"score":0,"children":[{"id":35,"score":0,"children":[{"id":73,"score":0},{"id":83,"score":0,"children":[{"id":3,"score":0}]}]}]},{"id":41,"score":0,"children":[{"id":5,"score":0},{"id":32,"score":0}]},{"id":43,"score":0,"children":[{"id":20,"score":0,"children":[{"id":89,"score":0,"children":[{"id":52,"score":0}]}]},{"id":27,"score":0},{"id":86,"score":0,"children":[{"id":6,"score":0}]},{"id":98,"score":0,"children":[{"id":54,"score":0},{"id":59,"score":0},{"id":65,"score":0,"children":[{"id":8,"score":0},{"id":47,"score":0}]},{"id":79,"score":0}]}]},{"id":64,"score":0},{"id":71,"score":0,"children":[{"id":19,"score":0},{"id":51,"score":0,"children":[{"id":57,"score":0,"children":[{"id":29,"score":0,"children":[{"id":49,"score":0}]},{"id":60,"score":0,"children":[{"id":34,"score":0}]}]},{"id":61,"score":0,"children":[{"id":63,"score":0},{"id":72,"score":0,"children":[{"id":9,"score":0},{"id":37,"score":0}]}]},{"id":90,"score":0}]},{"id":92,"score":0,"children":[{"id":96,"score":0,"children":[{"id":55,"score":0,"children":[{"id":12,"score":0},{"id":69,"score":0}]},{"id":80,"score":0}]}]}]},{"id":77,"score":0,"children":[{"id":81,"score":0,"children":[{"id":40,"score":0}]}]},{"id":84,"score":0,"children":[{"id":7,"score":0,"children":[{"id":33,"score":0,"children":[{"id":42,"score":0},{"id":95,"score":0}]}]},{"id":44,"score":0,"children":[{"id":58,"score":0}]}]},{"id":87,"score":0,"children":[{"id":68,"score":0}]},{"id":88,"score":0},{"id":99,"score":0}]};

• javascript
• recursion

Share Improve this question Follow asked Mar 11, 2014 at 6:03 SidSid 12911 silver badge1010 bronze badges

Add a ment  | 

1 Answer 1

Sorted by: Reset to default 6

you forgot to return the score if the element has children. try this one:

function updateScore(n) {
  if (n.children == undefined) return 1;
  n.children.forEach(function(c){
    var r = updateScore(c);  
    //if (!r) console.log(n);
    n.score += r;
  });
  return n.score;
}

本文标签： recursionJavascript Recursively count number of children in a treeStack Overflow