查找所有子组的递归函数

Question

我在 JavaScript 中创建递归函数时遇到问题。我有一个包含组的数组，其中每个组都有一个唯一的 ID、一个名称和一个 "parent"（对组 ID 的引用）。

我的递归函数的要点是列出从一个点开始的所有子群。它就像一个组织结构图，从顶部开始列出每个子组及其子组。

数组组由以下数据组成：

var groups = [{ id: 1, naam: "Directie", parent: 1 },
              { id: 2, naam: "Marketing", parent: 1 },
              { id: 3, naam: "Human Resources", parent: 1 },
              { id: 4, naam: "Financieel", parent: 2 },
              { id: 5, naam: "Verkoop", parent: 3 }];

以下代码仅可用于查找直接子级，但不能更深入地搜索下一级别。

var group = $("#groepen :selected").val();

var output = "";
var hasChildren = false;
var children = 0;

for(var i = 0; i < groups.length; i++)
{
    if(groups[i].parent === parseInt(group))
    {
        children++;
        output += "Group ID: " + groups[i].id + "\nGroup name: " + groups[i].naam + 
             "\nGroup parent: " + groups[i].parent + 
             "\n---------------------------------------------\n";
        hasChildren = true;
    }
}

output = "Children: " + children + 
   "\n---------------------------------------------\n" + output;

if(!hasChildren)
{
    output = "No data found";   
}

$("#groups").html(output);

所以在变量 group 为 "Directie" 的情况下，我会得到以下结果： - Directie（根） - 营销 - 人力资源

但它不会深入到下一个级别。我想要的结果是这样的： - Directie（根） - 营销 - 财务部 - 人力资源 - 维库普

顺序本身并不重要，我只想列出所有 "Directie".

的子组

注意：我还用当前代码做了一个 fiddle。要对此进行测试，只需单击 "search" 按钮和 select 下拉列表中的 "root" 组。

Answer 1

您不需要递归函数来提取尽可能深的节点和叶子中的所有子节点。这个函数会做你想做的事：

function getSubTree(tree, root) {
    var i, j, nextNodes, subtree = [], currentNodes = [root];
    while (currentNodes.length > 0) {
        subtree = subtree.concat(currentNodes);
        nextNodes = [];
        for (i=0; i < currentNodes.length; i++) {
            for (j=0; j < tree.length; j++) {
                if (tree[j].parent == currentNodes[i].id) {
                    if (currentNodes[i].id == tree[j].id) {
                        continue;
                    }
                    nextNodes.push(tree[j]);
                }
            }
        }
        currentNodes = nextNodes;
    }
    return subtree;
}

对于你的情况，你可以运行这样：

var subTree = getSubTree(groups, {
    id: 1,
    naam: "Directie",
    parent: 1
});

tree 或您在 group 中调用的必须是具有 id 和 parent 的对象数组（与此处的数据结构相同）。

一句话算法：尝试从tree到subtree添加节点，直到找不到与子树相关的节点。

Answer 2

为了使您的函数具有递归性，它需要调用自身。由于您要查找 parent child 关系，因此您必须从 parent 开始，然后使用一个函数来查找每个 child。在你的循环中再次调用你的函数，但将当前 child 传递给函数以找到该项目的 children。我不确定您希望如何输出数据，但此函数获取您在问题中描述的顺序。

var groups = [{
    id: 1,
    naam: "Directie",
    parent: 0
}, {
    id: 2,
    naam: "Marketing",
    parent: 1
}, {
    id: 3,
    naam: "Human Resources",
    parent: 1
}, {
    id: 4,
    naam: "Financieel",
    parent: 2
}, {
    id: 5,
    naam: "Verkoop",
    parent: 3
}];

function getChildren( parent ) {

    for(var i = 0; i < groups.length; i++) {

        if (groups[i].parent === parent.id ) {
            var output = "Group ID: " + groups[i].id + "\nGroup name: " + groups[i].naam + "\nGroup parent: " + groups[i].parent + "\n---------------------------------------------\n";

            $('textarea').append( output );
            getChildren( groups[i] );
        }
    }
}

getChildren( groups[0] )

JSFiddle

查找所有子组的递归函数

Recursive function to find all subgroups

javascript

tree

recursion