如何对该 Javascript/JSON 树进行递归搜索? [英] How to do a recursive search of this Javascript/JSON tree?

问题描述

我正在编写一些 Javascript 代码.我有一个看起来像这样的 JSON 对象(为了可读性而修改了间距):

I'm writing some Javascript code. I have a JSON object that looks like this (spacing modified for readability):

var myNodes = [
    {
        id: 4, 
        children: [
            {
                id: 1, 
                children: [
                ]
            },
            {
                id: 3, 
                children: [
                ]
            }
        ]
    },
    {
        id: 2, 
        children: [
        ]
    },
    {
        id: 6, 
        children: [
            {
                id: 5, 
                children: [
                ]
            }
        ]
    }
]

这个数据结构中每个节点的id都是唯一的.但是，除此之外，ID 号之间根本没有固定或已知的关系.而且每个级别的孩子数量没有限制.

Each node's id in this data structure is unique. However, other than that, there is no fixed or known relationship amongst the ID numbers at all. And there is no limit to the number of children at each level.

如果我想搜索这棵树并返回 id == 6 的节点.我该怎么做?我编写了以下代码，但是在遇到第一个叶节点后，整个算法返回 false，这显然是不对的.我只是想进行基本的深度优先搜索.但我不想像我在网络上的一些 DFS 实现中看到的那样，向这些数据添加额外的字段并标记"节点.

If I want search this tree and return the node with id == 6. How can I do it? I have written the following code, however after it encounters the first leaf node the entire algorithm returns false, which is clearly not right. I'm just trying to do a basic depth-first-search. But I don't want to add extra fields to this data and "mark" the nodes as I have seen in some DFS implementations on the web.

myClass.prototype.nodeSearch = function nodeSearch(treeNodes, searchID){
    for (var nodeIdx = 0; nodeIdx <= treeNodes.length-1; nodeIdx++)
    {
        console.log("Comparing treeNodes element with ID==" + treeNodes[nodeIdx].id + " to SearchID==" + searchID);
        if (treeNodes[nodeIdx].id == searchID)
        {    
            console.log("Match!");
            return treeNodes[nodeIdx];
        }
        else
        {
            console.log("No Match! Trying " + treeNodes[nodeIdx].children.length + " Children of Node ID#" + treeNodes[nodeIdx].id);
            return this.nodeSearch(treeNodes[nodeIdx].children, searchID); 
        }
    }
    console.log("Done trying " + treeNodes.length + " children. Returning False");
    return false;
};

推荐答案

你的算法有问题.你的 if 和你的 else 都无条件返回，这意味着 return 将不可避免地发生在每个循环的第一次迭代中，算法将只检查它的每个后代中的第一个(在这种情况下只检查节点 4 和 1，没有其他).您需要检查递归调用是否返回了找到的值，如果是，则仅将其向上传递到递归树.我认为这应该为您提供一个固定的解决方案:

There's a problem with your algorithm. Both your if and your else return unconditionally, which means that a return will inevitably occur on the first iteration through each loop, and the algorithm will only check the first of each of its descendants (in this case just nodes 4 and 1 and nothing else). You need to check whether the recursive call returned a found value, and only pass that up the recursive tree if so. I think this should provide you a fixed solution:

myClass.prototype.nodeSearch = function nodeSearch(treeNodes, searchID){
    for (var nodeIdx = 0; nodeIdx <= treeNodes.length-1; nodeIdx++) {
        var currentNode = treeNodes[nodeIdx],
            currentId = currentNode.id,
            currentChildren = currentNode.children;
        console.log("Comparing treeNodes element with ID==" + 
                    currentId + " to SearchID==" + searchID);
        if (currentId == searchID) {    
            console.log("Match!");
            return currentNode;
        }
        else {
            console.log("No Match! Trying " + currentChildren.length + 
                        " Children of Node ID#" + currentId);
            var foundDescendant = this.nodeSearch(currentChildren, searchID); 
            if (foundDescendant) {
                return foundDescendant;
            }
        }
    }
    console.log("Done trying " + treeNodes.length + " children. Returning False");
    return false;
};

我还添加了一些变量来帮助使代码变得DRYer并有助于防止前面提到的一些错误.

I've also added some variables to help make the code a bit DRYer and help prevent some of the bugs mentioned earlier.

这篇关于如何对该 Javascript/JSON 树进行递归搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！