Путаница относительно рекурсии BFS или DFS в виде дерева

Question

Я выполняю некоторую обработку в виде дерева, я не использую ни стек, ни очередь для обработки всех узлов, я просто делаю это:

void somemethod(TreeNode root){
    foreach(TreeNode item in root.Nodes)
    {
        //doSomething on item
        somemethod(item);
    }
 }

Знаю, я маленький блок (не могу понять с ясностью) и не могу понять, какую обработку дерева я делаю. Это BFS или DFS или ни один из них?

Моя подсказка была DFS, но я не был уверен. CLR не делает ничего странного, например, обрабатывает двух братьев и сестер, прежде чем отказаться от использования многопроцессорности? Эта странная мысль приходит мне в голову и омрачает мое суждение

Answer 1

Вы выполняете DFS (поиск / обход в глубину) прямо сейчас, используя рекурсию.

Сначала глубина , потому что рекурсия работает так же, как стек - вы обрабатываете дочерние элементытекущего узла, прежде чем обрабатывать следующий узел, поэтому сначала вы выбираете глубину вместо ширины.

Редактировать:

В ответ на ваш комментарий / обновленный вопрос:Ваш код будет обрабатываться последовательно элемент за элементом, параллельной обработки не будет, никакой «магии» не будет.Обход с использованием рекурсии эквивалентен использованию стека (LIFO = last in, first out) - он просто неявный.Таким образом, ваш метод также мог бы быть написан следующим образом, который производит тот же порядок обхода:

public void SomeMethod(TreeNode root)
{
    Stack<TreeNode> nodeStack = new Stack<TreeNode>();
    nodeStack.Push(root);

    while (nodeStack.Count > 0)
    {
        TreeNode node = nodeStack.Pop();
        //do something on item
        //need to push children in reverse order, so first child is pushed last
        foreach (TreeNode item in node.Nodes.Reverse())
            nodeStack.Push(item);
    }
}

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

(Также и рекурсивный метод, и метод, использующий стек, предполагают, что цикла нет, и не проверяют его- таким образом, предполагается, что это дерево, а не какой-либо граф. Для более поздней DFS введен флаг visited, чтобы отметить уже увиденные узлы)

Answer 2

Я почти уверен, что ваш пример соответствует "Первому поиску по глубине", потому что узлы, на которых вы что-то делаете, увеличиваются по глубине до ширины.