У меня есть решение этой проблемы.Я написал свое решение на C #, потому что это мой самый сильный язык, но я надеюсь, что вы поймете основную идею.Предположим, что у каждого узла дерева есть 3 ссылки: на левый, правый и родительский узлы.
Итак, у нас есть BinaryTree.Как мы могли бы напечатать это?Очевидно:
this._tree.Print();
Это было не очень сложно.Но как мы могли бы построить метод Print, если нам следует избегать рекурсии (поскольку последний использует память O (log (n)))?Вы когда-нибудь читали о ленивых списках (или потоках)?Ленивый список не хранит весь список в памяти, но знает , как рассчитать следующий элемент на основе текущего элемента .В каждый момент ленивый список выделяет О (1) памяти.Итак, предположим, нам удалось описать ленивый список для дерева.Тогда метод Print очень прост:
public static void Print<T>(this BinaryTree<T> tree)
where T : IComparable<T>
{
var node = new TreeNodeWalker<T>(tree.Root, WalkerState.FromParent);
while (node != null)
{
node = node.WalkNext();
}
}
Во время этого фрагмента кода вы можете обнаружить одну незнакомую сущность: TreeNodeWalker.Этот объект содержит узел дерева , который должен быть пройден, состояние , который сигнализирует, в какой момент обхода был создан этот ходок, и метод , который дает следующий ходок.Короче говоря, Walker выполняет следующие действия:
- Если мы добавляем любое поддерево из родительского узла, мы должны пройти левое поддерево.
- Если мы вышли из левого поддерева, мы должны вывести значение узла и пройти правое поддерево.
- Если мы вышли из правого поддерева, мы должны пройти родительский.
Это может быть представлено в коде следующим образом:
public class TreeNodeWalker<T>
where T:IComparable<T>
{
// Tree node, for which walker is created.
private readonly BinaryTreeNode<T> _node;
// State of walker.
private readonly WalkerState _state;
public TreeNodeWalker(BinaryTreeNode<T> node, WalkerState state)
{
this._node = node;
this._state = state;
}
public TreeNodeWalker<T> WalkNext()
{
if (this._state == WalkerState.FromParent)
{
// If we come to this node from parent
// we should walk left subtree first.
if (this._node.Left != null)
{
return new TreeNodeWalker<T>(this._node.Left, WalkerState.FromParent);
}
else
{
// If left subtree doesn't exist - return this node but with changed state (as if we have already walked left subtree).
return new TreeNodeWalker<T>(this._node, WalkerState.FromLeftSubTree);
}
}
else if (this._state == WalkerState.FromLeftSubTree)
{
// If we have returned from left subtree - current node is smallest in the tree
// so we should print it.
Console.WriteLine(this._node.Data.ToString());
// And walk right subtree...
if (this._node.Right != null)
{
//... if it exists
return new TreeNodeWalker<T>(this._node.Right, WalkerState.FromParent);
}
else
{
// ... or return current node as if we have returned from right subtree.
return new TreeNodeWalker<T>(this._node, WalkerState.FromRightSubTree);
}
}
else if (this._state == WalkerState.FromRightSubTree)
{
// If we have returned from right subtree, then we should move up.
if (this._node.Parent != null)
{
// If parent exists - we compare current node with left parent's node
// in order to say parent's walker which state is correct.
return new TreeNodeWalker<T>(this._node.Parent, this._node.Parent.Left == this._node ? WalkerState.FromLeftSubTree : WalkerState.FromRightSubTree);
}
else
{
// If there is no parent... Hooray, we have achieved root, which means end of walk.
return null;
}
}
else
{
return null;
}
}
}
Вы можете увидеть много места в коде и принять решение, что O (1) требуется памятьне выполнено.Но после получения следующего элемента ходунка нам больше не нужен предыдущий.Если вы пишете код на C ++, не забудьте освободить память.В качестве альтернативы, вы могли бы вообще избежать выделения экземпляра нового Walker, изменив внутренние переменные state и node (вы всегда должны возвращать эту ссылку в соответствующих местах).
Что касается сложности времени - это O (n).На самом деле O (3 * n), потому что мы посещаем каждый узел максимум три раза.
Удачи.