Рекурсивная функция для поиска всех подгрупп

Question

У меня возникла проблема с созданием рекурсивной функции в JavaScript. У меня есть массив с группами, где каждая группа имеет уникальный идентификатор, имя и «родительский» (ссылки на идентификатор группы).

Точкой моей рекурсивной функции будет список всех подгрупп, начиная с одной точки. Это как организационная диаграмма, где, когда вы начинаете с вершины и перечисляете каждую подгруппу со своими детьми.

Массив группы состоит из следующих данных:

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); 

Таким образом, в следующей ситуации, где переменная группа будет "Directie", я хотел бы получить следующие результаты: - Directie (корень) - Маркетинг - Человеческие ресурсы

Но это не углубляясь в следующие уровни. Результат я хочу это: - Directie (корень) - Маркетинг - Financieel - Человеческие ресурсы - Verkoop

Сам порядок не имеет значения, я просто хочу, чтобы перечислить все группы, которые подгруппы «Директ».

ПРИМЕЧАНИЕ: Я также сделал fiddle с текущим кодом. Чтобы проверить это, просто нажмите кнопку «Поиск» и выберите группу «root» из выпадающего списка.

Answer 1

Для того, чтобы ваша функция была рекурсивной, ее нужно вызвать. Поскольку вы ищете родительские отношения с родителями, вам придется начать с родителя, а затем использовать функцию для поиска каждого ребенка. Внутри вашего цикла снова вызовите свою функцию, но передайте текущему ребенку в функцию, чтобы найти дочерние элементы этого элемента. Я не уверен точно, как вы хотите выводить данные, но эта функция получает порядок, описанный в вашем вопросе.

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

Answer 2

Вам не нужна рекурсивная функция для извлечения всех детей в наиболее узкие узлы и листья. Эта функция будет делать то, что вы хотите:

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, пока вы не смогли найти ни одного узла, связанного с поддеревом.