Обход произвольно большого бинарного дерева

Question

Я застрял в поиске решения. C #, .NET 4.0, VS2010

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

Это вопрос бинарного дерева, и я пытаюсь написать

public IEnumerable<T> Values()

способ.

Вот полный код на случай, если вы заинтересованы: http://pastebin.com/xr2f3y7g

Очевидно, что текущая версия не работает. Я, наверное, должен упомянуть, что я новичок в C #, переходя с C ++.

Answer 1

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

public IEnumerable<T> Values()
{
    Stack<Node> stack = new Stack<Node>();
    Node current = this.root;
    while(current != null)
    {
        while(current.leftChild != null)
        {
            stack.Push(current);
            current = current.leftChild;
        }
        yield return current.data;
        while(current.rightChild == null && stack.Count > 0)
        {
            current = stack.Pop();
            yield return current.data;
        }
        current = current.rightChild;
    }

}

Если вы не можете использовать стек и ваши узлы имеют родительские указатели, вы можете попробовать решения из этого вопроса

Answer 2

Если предположить, что дерево почти сбалансировано, его максимальная глубина равна log2 (n), поэтому вам потребуется огромное дерево для переполнения стека.

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

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