如何获取未知JSON层次结构的总深度？

Question

我一直在努力寻找/构建一个递归函数来解析这个JSON文件并获取其子元素的总深度。

该文件大致如下：

var input = {
    "name": "positive",
    "children": [{
        "name": "product service",
        "children": [{
            "name": "price",
            "children": [{
                "name": "cost",
                "size": 8
            }]
        }, {
            "name": "quality",
            "children": [{
                "name": "messaging",
                "size": 4
            }]
        }]
    }, {
        "name": "customer service",
        "children": [{
            "name": "Personnel",
            "children": [{
                "name": "CEO",
                "size": 7
            }]
        }]
    }, {
        "name": "product",
        "children": [{
            "name": "Apple",
            "children": [{
                "name": "iPhone 4",
                "size": 10
            }]
        }]
    }] 
}

- jfk83

---

您希望结果以什么形式呈现？ - minikomi

Answer 1

你可以使用递归函数遍历整个树：

getDepth = function (obj) {
    var depth = 0;
    if (obj.children) {
        obj.children.forEach(function (d) {
            var tmpDepth = getDepth(d)
            if (tmpDepth > depth) {
                depth = tmpDepth
            }
        })
    }
    return 1 + depth
}

该函数的工作方式如下：

• 如果对象不是叶子节点（即对象具有子属性），则：
  • 计算每个子节点的深度，保存最大值
  • 返回最深子节点的深度加上1
• 否则，返回1

jsFiddle：http://jsfiddle.net/chrisJamesC/hFTN8/

编辑 使用现代JavaScript，该函数可能会像这样：

const getDepth = ({ children }) => 1 +
    (children ? Math.max(...children.map(getDepth)) : 0)

jsFiddle：http://jsfiddle.net/chrisJamesC/hFTN8/59/

- Christopher Chiche

---

如何利用这个方法获取一个完全未知的JSON数据的深度，或使其可重复使用于任何类型的JSON数据？我猜测这需要将JSON元素命名为“children”，如果它们被命名为例如“cars”而不是“children”，或者当一个JSON数据中有“flies”而另一个JSON数据中有“birds”时，该方法将无法正常工作。 - Juha Untinen

const 给我 TypeError: 无法匹配 'undefined' 或 'null'。 - Ali Bahrami

这是因为您的JavaScript引擎不支持JavaScript语言的新版本（ES6+）。因此，您可以使用我编写的第一个版本的脚本，它具有相同的功能。 - Christopher Chiche

感谢您分享解决方案，@ChristopherChiche。我很想知道编写该函数的思路，因为我很难理解它是如何工作的，特别是如果我尝试考虑每次递归返回的值。然而，如果我从叶子节点/最深层开始计算每个级别的返回值并向外计算，那么最终值4就有意义了。您也是这样考虑的吗？ - user51462

@user51462 很高兴你愿意学习更多！这是一种尾递归，当处理树/图或其他数据结构时非常强大。 - Christopher Chiche

@ChristopherChiche，我以前没听说过尾递归，在递归的兔子洞里掉进去了，哈哈，谢谢您的帮助:) - user51462

Answer 2

这将会计算一棵树中“叶子”的数量：

var treeCount = function (branch) {
    if (!branch.children) {
        return 1;
    }
    return branch.children.reduce(function (c, b) {
        return c + treeCount(b);
    }, 0)
}

另一种获取深度的方法：

var depthCount = function (branch) {
    if (!branch.children) {
        return 1;
    }
    return 1 + d3.max(branch.children.map(depthCount));
 }

- minikomi

---

你的意思是if(!branch.children)吗？ - Christopher Chiche