Tree Co prawda kiedyś dawno temu (w 2011 roku) zrobiłem wpis z implementacją drzewa binarnego. Znając jednak siebie z 2011 roku nie zaszkodzi zrobić takie szybkie przypomnieje i użyć wzorca iterator.

Zaczynamy od tworzenia gałęzi i liści drzewa binarnego. Każda gałąź ma wartość  i może, ale nie musi mieć następne gałęzi.

W konstruktorze przekazuje dalsze instancje tej samej klasy. Co oznacza, że możemy stworzyć prawdziwy łańcuch łączący te klasy, a raczej drzewo. 

public class Node<T>
{
    public T Value;
    public Node<T> Left, Right;
    public Node<T> Parent;
    public Node(T value)
    {
        Value = value;
    }
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
        left.Parent = right.Parent = this;
    }
}

Mam więc drzewo binarne. Teraz jak po tym drzewie chodzić.

//   3
//  / \
// 2   1
var root = new Node<int>(3,
    new Node<int>(2),
    new Node<int>(1));

Można przejść po drzewie na trzy sposoby. Umieszczę fragment wikipedi by nie popełnić błędu nazewnictwa metody.

My zrobimy przejście in-order.

public class IteratorInOrder<T>
{
    public Node<T> Current { get; set; }
    private readonly Node<T> root;
    private bool yieldedStart;

    public IteratorInOrder(Node<T> root)
    {
        this.root = Current = root;
        while (Current.Left != null)
            Current = Current.Left;
    }
    public bool MoveNext()
    {
        throw new NotImplementedException();
    }
}

Wygląda to całkiem nieźle i co najważniejsze korzystamy ze wzorca Iterator w jakiś sensowny sposób. Poziom skomplikowania tego kodu wzrośnie wraz z stworzeniem metody MoveNexr().

public bool MoveNext()
{
    if (!yieldedStart)
    {
        yieldedStart = true;
        return true;
    }
    if (Current.Right != null)
    {
        Current = Current.Right;
        while (Current.Left != null)
            Current = Current.Left;
        return true;
    }
    else
    {
        var p = Current.Parent;
        while (p != null && Current == p.Right)
        {
            Current = p;
            p = p.Parent;
        }
        Current = p;
        return Current != null;
    }
}

Logika szukania następnego element w drzewie  na pewno nie może być napisana krócej. Eee tylko Ciebie podpuszczam można tą logikę sprawdzania gałęzi drzewa napisać lepiej, ale o tym później.

Najpierw ustawiamy flagę, że zaczynamy spacer po kolekcji. Później będziemy sprawdzać gałęzi drzewa zaczynając od prawej stony.

Wygląda to dziwnie wiem, ale z drugiej strony całkiem nie dawno pisałem listy jednokierunkowe w JavaScript i wiesz mi pisanie algorytmów od zera jakby to był C++ zawsze wygląda dziwnie. 

Mamy więc iteratora. Jak on działa?

var root = new Node<int>(-1, new Node<int>(-2),
    new Node<int>(4,
    new Node<int>(2, new Node<int>(1), new Node<int>(3)),
    new Node<int>(5))
);
//    0
//   / \
//  -1  4
//     / \
//    2   5
//   / \
//  1   3

var it = new IteratorInOrder<int>(root);
while (it.MoveNext())
{
    Console.WriteLine(it.Current.Value);
}

Aplikacja wyświetli wartości w następującej kolejności : -1,0,1,2,3,4,5

Zbudujmy też klasę, która zadeklaruję ten domyślny iterator w sobie.

public class BinaryTree<T>
{
    private Node<T> root;
    public BinaryTree(Node<T> root)
    {
        this.root = root;
    }
    public IteratorInOrder<T> GetEnumerator()
    {
        return new IteratorInOrder<T>(root);
    }
}

Teraz możemy skorzystać z pętli foreach. Co ciekawe nie musimy implementować interfejsu IEnumerable. Kompilator sam znajduje metodę GetEnumerator(). Magia dynamicznej części C# zapewne na to pozwala.

var root2 = new Node<int>(0,
new Node<int>(-2, new Node<int>(-3), new Node<int>(-1)),
new Node<int>(4,
new Node<int>(2, new Node<int>(1), new Node<int>(3)),
new Node<int>(5))
);

var tree = new BinaryTree<int>(root2);
foreach (var node in tree)
   Console.WriteLine(node.Value);

A jak to można ulepszyć? Po pierwsze ten przykład prosi się o rekurencję, ale metoda MoveNext() nie jest w stanie zapamiętać kontekstu za każdym razem, gdy ją wywołujemy.

Pamiętamy tylko poprzedni element. Teraz sobie myślisz ten styl programowania jest beznadziejny. Nie możliwe, że kolekcję w C# są tak napisane. No cóż te kolekcję korzystają jeszcze z czegoś.

Na pomoc przychodzi wyrażenie yield return.

Dzięki temu mamy prymitywna maszynę stanów. Teraz jak widzisz wszystkie zapytania są rekurencyjne. Tworzymy kolekcję z poleceń yield, a one korzystają z pętli foreach, która wywoła kolekcję z poleceń yield, a one skorzysta z pętli foreach...

..i tak dalej...i tak dalej, aż znajdziemy węzeł, który nie ma ani gałęzi po prawej, ani po lewej.

A potem wracamy do poprzedniego węzła i sprawdzamy wartość prawej gałęzi. Jak już to zrobimy to wracamy do tego wężła jeszcze raz i cofamy się do poprzedniej gałęzi.

public class BinaryTree<T>
{
    public IEnumerable<Node<T>> NaturalInOrder
    {
        get
        {
            IEnumerable<Node<T>> TraverseInOrder(Node<T> current)
            {
                if (current.Left != null)
                {
                    foreach (var left in TraverseInOrder(current.Left))
                        yield return left;
                }
                yield return current;
                if (current.Right != null)
                {
                    foreach (var right in TraverseInOrder(current.Right))
                        yield return right;
                }
            }
            foreach (var node in TraverseInOrder(root))
                yield return node;
        }
    }

    private Node<T> root;
    public BinaryTree(Node<T> root)
    {
        this.root = root;
    }

}

Na koniec użyjmy LINQ aby scalić wartości zwrócone przez drzewo.

var root3 = new Node<int>(0,
    new Node<int>(-2, new Node<int>(-3), new Node<int>(-1)),
    new Node<int>(4,
    new Node<int>(2, new Node<int>(1), new Node<int>(3)),
    new Node<int>(6, new Node<int>(5), new Node<int>(7)))
);
var tree = new BinaryTree<int>(root3);
Console.WriteLine(string.Join(",",
    tree.NaturalInOrder.Select(x =>
x.Value)));

Wynik to : -3,-2,-1,0,1,2,3,4,5,6,7

Podsumowanie:

Wzorzec projektowy iterator w C# jest bardzo ukryty . Zauważ, że nie wspieramy iteracji, w której moglibyśmy się cofać . Nie mamy metody MoveBack().

Słowo kluczowe yield na pewno bardzo uproszcza kod. Dla kogoś to wygląda jak kolekcja, a dla Ciebie może jest to tylko maszyna stanów, która wypluwa wartości według określonego algorytmu.

Pamiętaj zawsze może napisać taki kod w C#.

public IEnumerable<int> RandomNumbers
{
    get
    {

        Random random = new Random();
        for (int i = 0; i < 1000; i++)
        {
            yield return
                random.Next(int.MinValue, int.MaxValue);
        }

    }
}

A dla kodu z tego poziomu dalej wygląda to, jak kolekcja z 1000 elementami. 

Console.WriteLine(string.Join(",", tree2.RandomNumbers.Take(10)));