如何从树对象获取给定路径的子树？

Question

我有一个树形对象：

var data = [{
    "root": true,
    "label": null,
    "question": "What product category?",
    "nodes": [{
        "label": "Clothes",
        "question": "What type of clothing?",
        "nodes": [{
            "label": "Jeans",
            "question": "Color of jeans?",
            "nodes": [{
                    "label": "Blue",
                    "question": null,
                    "nodes": null
                },

            ]
        }]
    }]
}];

我试图返回给定数组 [0,0,0] 路径的子树，该路径将返回data[0].nodes[0].nodes[0]. 我正在尝试一种迭代方法，可以用递归方法来实现吗？

Answer 1

这是递归函数：

function subTree(arr, indexes) {
    var a = arr[indexes[0]];
    return indexes.length > 1 ? subTree(a.nodes, indexes.slice(1)) : a;
}

var data = [{
    "root": true,
    "label": null,
    "question": "What product category?",
    "nodes": [{
        "label": "Clothes",
        "question": "What type of clothing?",
        "nodes": [{
            "label": "Jeans",
            "question": "Color of jeans?",
            "nodes": [{
                "label": "Blue",
                "question": null,
                "nodes": null
              }]  
        }]
    }]
}];

console.log(subTree(data, [0,0,0]));

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

得出此解决方案的思考过程

正如您在评论中提出的问题，以下是我在解决此问题时所经历的过程：

我想到的第一件事：我可能需要通过对象属性来找到有孩子的那个。

第二件事：不，我不知道——它始终是nodes财产。

然后：但是等等——第一个索引不是从nodes属性中获取的，而所有其他索引都是。这是获得通用解决方案的问题吗？

然后，我意识到它不是，因为第一次调用从一个数组开始——我不需要知道它是作为nodes属性值给出的数组还是只是初始数据数组。数组就是数组。只有在第一次递归调用（以及所有更深层次的调用）时，我才需要nodes按名称提及该属性，并且始终是该属性名称。

似乎合乎逻辑，在每个递归你会通过的阵列nodes特性和其余的指数的阵列，所以没有一个已经处理的指标。后一个数组将减少为一个空数组，这将是递归的终点。

然后我开始编写代码来处理递归结束的情况，即索引用完的情况。首先我想写

function subTree(arr, indexes) {
    if (!indexes.length) return arr;
    // ...
}

但这是不对的，因为返回值不应该是数组，而是具有该数组的对象——所以实际上这段代码会递归得太深！

所以第二次尝试变成了：

function subTree(arr, indexes) {
    var index = indexes.shift();
    if (indexes.length == 0) return arr[index];
    // ...
}

该shift调用似乎是删除第一个索引并将其保存在单独变量中的好方法，因此它可以用于返回正确的对象。

这看起来很好：如果调用是subTree(data, [0])我确实会得到想要的结果。

然后我继续写递归案例：

function subTree(arr, indexes) {
    var index = indexes.shift();
    if (indexes.length == 0) return arr[index];
    return subTree(arr[index].nodes, indexes);
}

这看起来也不错。有效。

但是看到两个return只用一个 隔开的语句if需要一个三元运算符，所以我把它改成了：

function subTree(arr, indexes) {
    var index = indexes.shift();
    return indexes.length ? subTree(arr[index].nodes, indexes) : arr[index];
}

我发布了这个，然后意识到使用它不是一个好主意shift：它修改传递给函数的参数，这对调用者不是很好：这是一个意想不到的副作用。所以我应该创建数组的新实例，而不是修改给定的索引数组：

function subTree(arr, indexes) {
    var index = indexes[0];
    return indexes.length > 1 ? subTree(arr[index].nodes, indexes.slice(1)) : arr[index];
}

slice是一种获取给定数组一部分的浅拷贝的方法，因此使用1as 唯一参数创建一个新数组，该数组不再具有第一个索引。有了这种工作方式，条件当然必须从简单indexes.length变为indexes.length > 1。

最后，我觉得有点愚蠢，我创建了一个index避免重复的变量[0]，但并没有避免使用arr[index]两次。于是最终的解决方案浮出水面。

希望这可以帮助。