Как адаптировать итеративный алгоритм обхода бинарного дерева к обходу сильноветвящегося дерева?

Question

Мне необходимо реализовать итеративный обход сильноветвящегося дерева в глубину, в порядке "вершина – левое поддерево – правое поддерево". Как сделать это для бинарного дерева, используя стек, понятно, но как сделать для сильноветвящегося не очень ясно. Прошу ссылку на литературу или на реализацию на любом языке.

Пример итеративного обхода на языке C#:

var stack = new Stack<Node<int>>();
var top = root;

while (top != null || stack.Count != 0)
{
    if (stack.Count != 0)
    {
        top = stack.Pop();
    }

    while (top != null)
    {
        if (top.Right != null)
        {
            stack.Push(top.Right);
        }

        var value = top.Value; // Обработка значения.

        top = top.Left;
    }
}

Answer 1

Рекурсивно:

function go(v) {
  handle(v)

  for (var x of v.children) {
    go(x)
  }
}

Нерекурсивно:

function go(v) {
  var st = [v]

  while (st.length) {
    var x = st.pop()

    handle(x)

    for (var q=x.children.length; --q!==-1; ) {
      st.push(x.children[q])
    }
  }
}

Answer 2

Аналогичный код для дерева с неограниченным числом детей в узле:

var stack = new Stack<Node<int>>();
var top = root;

while (top != null || stack.Count != 0)
{
    if (stack.Count != 0)
    {
        top = stack.Pop();
    }

    while (top != null)
    {
        for (var i = top.Children.Length - 1; i > 0; --i)
        {
            stack.Push(top.Children[i]);
        }

        var value = top.Value; // Обработка значения.

        top = top.Children[0];
    }
}

Ваш код не самый простой: два цикла, видимо сделана оптимизация для левых ветвей. Всё можно сделать проще:

var stack = new Stack<Node<int>>();

stack.Push(root);
while (stack.Count > 0)
{
    var top = stack.Pop();
    if (top != null)
    {
        var value = top.Value; // Обработка значения.
        stack.Push(top.Right);
        stack.Push(top.Left);
    }
}

Аналог для массива детей:

var stack = new Stack<Node<int>>();

stack.Push(root);
while (stack.Count > 0)
{
    var top = stack.Pop();
    if (top != null)
    {
        var value = top.Value; // Обработка значения.
        for (var i = top.Children.Length - 1; i >= 0; --i)
        {
            stack.Push(top.Children[i]);
        }
    }
}

БЛОГ НА HUSL

Как адаптировать итеративный алгоритм обхода бинарного дерева к обходу сильноветвящегося дерева?

Ответы (2 шт):