javascript - 遍历树并获取每个对象的深度

Question

我有一个 JavaScript 对象，我们称它为“obj”。我想遍历这个对象及其后代，找出每个对象有多少个后代，并将这个数字保存在对象的一个​​属性上，比如obj.numOfDescendants或者其他的东西。如何递归完成？

我尝试了以下方法，但没有用:

var traversTree = function(obj) {
    for (let k in obj) {
        if (typeof obj[k] === "object") {
            if (!obj["numOfDescendants"])
                obj["numOfDescendants"] = 0;
            obj.numOfDescendants += traversTree(obj[k]); // Here is where I'm stuck.
                                                         // What do I return here
                                                         // in order to sum the
                                                         // depth?
            return 1;
        }
    }
}

谁能指出我错在哪里？

Answer 1

几个问题:

• 您期望 traversTree 返回一个值:

  obj.numOfDescendants += traversTree(obj[k]);
  

  ...但您并非在所有情况下都从它返回值，仅在某些 情况下。您会希望该函数始终返回一个值。

• 在循环结束之前，您返回得太早了。您需要将对对象的所有 对象子对象调用traversTree 的结果相加。

• (与上一点相关。)您正在循环中更新 obj.numOfDescendants，但在循环完成之前您实际上并不知道该数字。

• 我们需要统计刚刚进入的那个，所以在添加后代的时候，我们需要在上面调用traversTree的结果和1 .

所以类似的东西:

var traversTree = function(obj) {
    var descendants = 0;
    for (let k in obj) {
        if (typeof obj[k] === "object") {
            descendants += traversTree(obj[k]) + 1;
        }
    }
    obj.numOfDescendants = descendants;
    return descendants;
};

例子:

var traversTree = function(obj) {
  var descendants = 0;
  for (let k in obj) {
    if (typeof obj[k] === "object") {
      descendants += traversTree(obj[k]) + 1;
    }
  }
  obj.numOfDescendants = descendants;
  return descendants;
};

console.log("Example 1:");
var o1 = {
  test: {}
};
traversTree(o1);
console.log(o1);

console.log("Example 2:");
var o2 = {
  a: {},
  b: {
    c: {}
  }
};
traversTree(o2);
console.log(o2);

console.log("Example 3:");
var o3 = {
  a: {},
  b: {
    c: [{}, {x:{z:"y"}}, {}]
  }
};
traversTree(o3);
console.log(o3);

.as-console-wrapper {
  max-height: 100% !important;
}

---

旁注:您在代码中同时使用了 var 和 let。 let 是 ES2015 的新关键字。如果您正在使用 ES2015 或更高版本并切换到使用 let，那么最好始终如一地执行此操作，而不是有时使用 var。还请尽可能使用 const 和箭头函数，例如:

const traversTree = obj => {
    let descendants = 0;
    for (const k in obj) {
        if (typeof obj[k] === "object") {
            descendants += traversTree(obj[k]) + 1;
        }
    }
    obj.numOfDescendants = descendants;
    return descendants;
};

在上面看到 const for k 可能看起来很奇怪，但是当您在初始化器是这样的，你实际上为每个循环迭代得到一个新的 k，并且 k 的值在循环体期间永远不会改变，所以 const 实际上在那里工作。不过，诚然，它看起来确实有点奇怪。