BInary Search Tree iterator c # без родительского свойства

Question

Я недавно начал создавать дерево бинарного поиска в C # для практики.После выполнения этой задачи я решил реализовать ICollection<T>, чтобы мое дерево можно было использовать с foreach и просто для того, чтобы я смог попрактиковаться.

Я построил свои классы таким образомчто у меня есть класс Node<T> и класс BinarySearchTree<T>, который содержит Node<T> a Count целое число и IsReadOnly логическое значение.Это мой класс узла:

    internal class Node<T>: INode<T> where T: IComparable<T>
  {
    public Node<T> RightChildNode { get; set; }
    public Node<T> LeftChildNode { get; set; }
    public T Key { get; set; }

    //some methods go here
  }

, а это мой класс BST:

    public class BinarySearchTree<T>: ICollection<T> where T: IComparable<T>
{
    internal Node<T> Root { get; set; }
    public int Count { get; private set; }
    public bool IsReadOnly => false;

    //some methods go here
}

Теперь для реализации ICollection<T> мне, очевидно, нужен перечислитель, который у меня есть (частично)реализован так:

    internal class BinarySearchTreeEnumerator<T> : IEnumerator<T> where T: IComparable<T>
{
    private BinarySearchTree<T> _parentTree;
    private BinarySearchTree<T> _currentTree;
    private Node<T> _currentNode => _currentTree.Root;
    private T _currentKey;

    public T Current => _currentNode.Key;

    /// <summary>
    /// generic constructor
    /// </summary>
    /// <param name="tree"></param>
    public BinarySearchTreeEnumerator(BinarySearchTree<T> tree)
    {
        this._parentTree = tree;
    }

    object IEnumerator.Current => Current;

    void IDisposable.Dispose(){}

    //pls
    public bool MoveNext()
    {
        if (_currentTree is null)
        {
            _currentTree = _parentTree;
        }
        var leftSubtree = this._currentTree.GetLeftSubtree();
        var rightSubtree = this._currentTree.GetRightSubtree();

        if (!(leftSubtree is null))
        {
            this._currentTree = leftSubtree;

        }
        else if (!(rightSubtree is null))
        {
            this._currentTree = rightSubtree;

        }
        else
        {

        }

    }

    public void Reset()
    {
        _currentTree = _parentTree;
    }
}

Теперь моя проблема вполне очевидна при использовании метода MoveNext().Теперь он не работает, потому что он просто спускается по дереву на крайнем левом пути, а затем застревает, когда добирается до конца этого пути.Я знаю, что могу решить эту проблему, добавив свойство Parent в мой класс Node<T>, а затем, когда я достигну конца пути в моем дереве, я могу просто подняться на один узел и проверить, есть ли другой путь ...Однако это означало бы полное изменение моего исходного класса, и я предпочел бы не делать этого.

Это просто неизбежно?Есть ли способ решить эту проблему без изменения моего класса Node<T> таким способом?

Редактировать: Я сделал вещь, но она не работает: /

      public bool MoveNext()
    {
        if (_currentNode is null)
        {
            this._currentNode = _parentTree.Root;
            this._nodeStack.Push(_currentNode);
            return true;
        }
        var leftNode = this._currentNode.LeftChildNode;
        var rightNode = this._currentNode.RightChildNode;

        if (!(leftNode is null))
        {
            this._currentNode = leftNode;
            this._nodeStack.Push(_currentNode);
            return true;
        }
        else if (!(rightNode is null))
        {
            this._currentNode = rightNode;
            this._nodeStack.Push(_currentNode);
            return true;
        }
        else
        {
            //current node does not have children
            var parent = this._nodeStack.Pop();
            do
            {

                if (parent is null)
                {
                    return false;
                }

            } while (!(parent.RightChildNode is null));

            this._currentNode = parent.RightChildNode;
            this._nodeStack.Push(_currentNode);
            return true;
        }

    }

Answer 1

Для реализации этого может быть проще использовать рекурсию;например:

Рекурсивная версия (только для сбалансированных деревьев)

public IEnumerator<T> GetEnumerator()
{
    return enumerate(Root).GetEnumerator();
}

IEnumerable<T> enumerate(Node<T> root)
{
    if (root == null)
        yield break;

    yield return root.Key;

    foreach (var value in enumerate(root.LeftChildNode))
        yield return value;

    foreach (var value in enumerate(root.RightChildNode))
        yield return value;
}

Это члены BinarySearchTree<T>.

Учитывая приведенную выше реализацию, затем следующий код:

BinarySearchTree<double> tree = new BinarySearchTree<double>();

tree.Root = new Node<double> {Key = 1.1};

tree.Root.LeftChildNode  = new Node<double> {Key = 2.1};
tree.Root.RightChildNode = new Node<double> {Key = 2.2};

tree.Root.LeftChildNode.LeftChildNode   = new Node<double> { Key = 3.1 };
tree.Root.LeftChildNode.RightChildNode  = new Node<double> { Key = 3.2 };
tree.Root.RightChildNode.LeftChildNode  = new Node<double> { Key = 3.3 };
tree.Root.RightChildNode.RightChildNode = new Node<double> { Key = 3.4 };

foreach (var value in tree)
{
    Console.WriteLine(value);
}

производит этот вывод:

1.1
2.1
3.1
3.2
2.2
3.3
3.4

ПРЕДУПРЕЖДЕНИЕ: пространство стека ограничено 1 МБ для 32-разрядного процесса и 4 МБ для 64-разрядного процессапоэтому при использовании рекурсии может не хватить места в стеке, если дерево является вырожденным (плохо несбалансированным).

нерекурсивная версия

Вы можете реализовать нерекурсивная версия довольно просто, например, так:

IEnumerable<T> enumerate(Node<T> root)
{
    var stack = new Stack<Node<T>>();
    stack.Push(root);

    while (stack.Count > 0)
    {
        var node = stack.Pop();

        if (node == null)
            continue;

        yield return node.Key;
        stack.Push(node.RightChildNode);
        stack.Push(node.LeftChildNode);
    }
}

Возвращает элементы в том же порядке, что и рекурсивная версия.

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

Answer 2

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

Возможно, рассмотрим подход с широким первым поиском (BFS), который является итеративным.Вам нужны только currentNode и Queue.

Правило будет

current = Queue.poll();
For child in current
     Queue.offer(child);

При инициализации вы должны сделать

Queue.offer(rootNode);

Я извиняюсь за плохое форматированиеи синтаксис, мобильный пользователь здесь.Andres

Answer 3

Если вы добавите в свой перечислитель

private List<Node<T>> _currentParentNodes = new List<Node<T>>();

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