Przechodzenie drzewa w C#

Bazowa struktura i interfejs

Niedawno pisałem o różnych sposobach pozyskiwania drzew z płaskich struktur danych, między innymi z relacyjnych baz danych. Cały wpis można zobaczyć tutaj: Budowanie drzew w C#. Struktura drzewa, do którego dążyliśmy w tamtych przykładach, reprezentowana była przez pewną ogólną klasę. Przypomnijmy sobie strukturę:

public class TreeNode<T>
{
    public TreeNode()
    {
        Items = new List<TreeNode<T>>();
    }
 
    public List<TreeNode<T>> Items { get; set; }
}

Struktura jest na tyle ogólna, że pozwala w klasach pochodnych definiować dowolne właściwości i przechowywać większość drzew. Zostało to pokazane we wspomnianym już wpisie. Tym razem kierunek konwersji będzie odwrotny. Zamiast konwertować listę na drzewo, skonwertujemy drzewo na listę.

Warto w tym momencie wspomnieć, że struktura drzewiasta pozwala nam przechodzić przez kolejne węzły drzewa w konkretnym porządku. Te algorytmy noszą znane powszechnie nazwy: Preorder i PostorderIstnieje jeszcze jedna metoda - Inorder. Jest ona stosowana tylko w szczególnym rodzaju drzew. Są to takie drzewa, których węzły potomne są podzielone na dwie grupy. Algorytm przegląda najpierw lewe dzieci, następnie węzeł rodzica, a w końcu prawe dzieci. Szczególnym przypadkiem takiego drzewa jest drzewo binarne.. Ta pierwsza metoda najpierw pobiera węzeł rodzica, a następnie wszystkie węzły potomne. Ta druga przechodzi najpierw przez węzły potomne, a dopiero wtedy, gdy już wszystkie dzieci zostaną przetworzone, przetwarzany jest węzeł rodzica.

Reasumując, naszym zadaniem jest pobranie drzewa i zwrócenie kolekcji elementów w określonym porządku. Ogólna postać może być opisana poprzez klasę abstrakcyjną z jedną metodą. Popatrzmy na listing:

public abstract class TreeEnumerator
{
    public abstract IEnumerable<T> Enumerate<T>(T root)
        where T : TreeNode<T>;
}

Wszystkie, to znaczy obie, implementacje będą zgodne z podanym schematem. Pozwoli to zewnętrznym komponentom stosować te implementacje zamiennie. W wielu przypadkach odpowiedni dobór metody jest kluczowy. Przejdźmy do samej implementacji.

Implementacja metod

W kolejnych podpunktach przedstawione zostały konkretne implementacje. Są one bardzo podobne, prawie identyczne i warto na to zwrócić uwagę.

Preorder

Metoda Preorder zwraca najpierw węzeł rodzica, a dopiero później węzły potomne. Mówiąc inaczej, przechodzi drzewo od korzenia do liści. Taką kolejność przetwarzania należy przyjąć między innymi podczas zapisu rekordów do bazy. Najpierw trzeba zapisać klucz rodzica (najczęściej generowany przez bazę danych), a dopiero później można go wykorzystać w rekordach podrzędnych. Popatrzmy na poniższy listing:

public class PreorderEnumerator : TreeEnumerator
{
    public override IEnumerable<T> Enumerate<T>(T root)
    {
        if (root != null)
        {
            yield return root;

            var children = root.Items;
            if (children != null)
                foreach (var child in children)
                    foreach (var item in Enumerate((T)child))
                        yield return item;
        }
    }
}

Implementacja jest bardzo prosta i chyba nie wymaga wyjaśnień.

Postorder

Metoda Postorder zwraca najpierw węzły dzieci, a dopiero później węzeł rodzica. Inaczej mówiąc przechodzi drzewo od liści do korzenia. Taką kolejność przetwarzania należy przyjąć między innymi podczas usuwania rekordów z bazy. Nie można tego zrobić odwrotnie, bo elementy podrzędne mają klucz obcy, więc próba ich usunięcia spowoduje błąd więzów integralności. Implementacja metody Postorder została pokazana na poniższym listingu:

public class PostorderEnumerator : TreeEnumerator
{
    public override IEnumerable<T> Enumerate<T>(T root)
    {
        if (root != null)
        {
            var children = root.Items;
            if (children != null)
                foreach (var child in children)
                    foreach (var item in Enumerate((T)child))
                        yield return item;

            yield return root;
        }
    }
}

Metody są bardzo proste w obsłudze i w pełni zgodne z zaprezentowanymi wcześniej metodami do konwersji płaskich struktur na drzewa.

Przykładowe użycie metod do przechodzenia drzew:

Popatrzmy na przykład użycia stworzonych metod. Najpierw wykorzystamy klasę regionu geograficznego, który może zawierać podregiony itd:

class GeographyNode: TreeNode<GeographyNode>
{
    public string Name { get; set; }
}

Drzewiaste struktury w większości aplikacji pochodzą z jakiegoś konkretnego źródła. Na potrzeby przykładu drzewo będzie stworzone w kodzie programu. Popatrzmy na kolejny listing:

var earth = new GeographyNode()
{
    Name = "Ziemia",
    Items = new List<TreeNode<GeographyNode>>()
    {
        new GeographyNode(){
            Name = "Europa",
            Items = new List<TreeNode<GeographyNode>>()
            {
                new GeographyNode(){
                    Name = "Polska"
                },
                new GeographyNode(){
                    Name = "Monako"
                }
            }
        },
        new GeographyNode(){
            Name = "Azja"
        }
    }
};

Całe te przygotowania są znacznie bardziej skomplikowane niż przechodzenie drzewa zaimplementowanymi metodami Preorder i Postorder. Popatrzmy na bardzo krótki listing:

Console.WriteLine("Geography:");
foreach (var place in new PostorderEnumerator().Enumerate(earth))
    Console.WriteLine(place.Name);

Wynikiem działania powyższego kodu będzie wypisanie następujących nazw:

Geography:
Polska
Monako
Europa
Azja
Ziemia

Metoda sama rozpoznaje rzeczywisty typ kolekcji i nie trzeba tego nigdzie przekazywać. Wywołanie metody Preorder będzie bardzo podobne. Wystarczy zamienić nazwę klasy.

Wspomniałem wcześniej, że metody są zgodne ze strukturami powstającymi z konwersji płaskiej listy na drzewo pokazanej w atrykule Budowanie drzew w C#. Popatrzmy na drugi przykład, tym razem dwustronnej konwersji:

List<Species> species = new List<Species>()
{
    new Species(){ID = 1, ParentID = 0, Name = "Ssaki"},
    new Species(){ID = 2, ParentID = 1, Name = "Gryzonie"},
    new Species(){ID = 3, ParentID = 1, Name = "Torbacze"},
    new Species(){ID = 4, ParentID = 2, Name = "Kapibary"}
};

var dynamicConverted = Tree.Create(species, a => new SpeciesNode() { ID = a.ID, Name = a.Name });

Console.WriteLine("Preorder:");
foreach (var specie in new PreorderEnumerator().Enumerate(dynamicConverted.First()))
    Console.WriteLine(specie.Name);

W wyniku wykonania pokazanego kodu otrzymamy następującą kolejność:

Preorder:
Ssaki
Gryzonie
Kapibary
Torbacze

Kolejność przekazywanych węzłów w liście nie ma absolutnie żadnego znaczenia dla budowanej hierarchii (układ zmieni się najwyżej w ramach kolekcji dzieci). Struktura zostanie najpierw skonwertowana na drzewo, a dopiero to drzewo zostanie przeglądnięte w pożądanym przez nas porządku.

Zastosowanie algorytmów przechodzenia drzew

Przedstawione w artykule klasy pomocnicze należy traktować w kategoriach cegiełek, klocków, komponentów tworzących bardziej złożone rozwiązania. Kolejność może mieć znaczenie w następujących przypadkach:

• Informacja o działaniach przedsiębiorstwa może przechodzić od stanowisk najwyższych do najniższych (Preorder),
• Liczenie głosów wyborczych może się odbywać od najmniejszych okręgowych komisji, a te wyniki mogą być potem sumowane przez komisje wojewódzkie i centralne (Postorder),
• Wyliczanie wyrażeń matematycznych polega między innymi na priorytetach. Najpierw redukujemy w najbardziej zagnieżdżonych nawiasach, mnożenie wykonujemy przed dodawaniem. Drzewa takich wyrażeń matematycznych liczone są zatem od liści (Postorder).
• Katalogi przeglądane są od najwyżej położonego do najbardziej zagłębionego (Preorder).

Zastosowań jest z pewnością więcej. W najbliższym czasie pokażę jak za pomocą tych operacji wykonać dość powszechny problem scalania drzew w bazie danych. Dane pobierane są w postaci listy i konwertowane na drzewo. Taka drzewiasta postać przesyłana jest do aplikacji klienta. Nie ma znaczenia czy jest to strona Web i WebAPI czy aplikacja WPF i usługa WCF. Drzewo, być może przekształcone, wraca w pewnym momencie na serwer. Tam trzeba te dane jakoś scalić, zachowując istniejące relacje w bazie. Relacje nie tylko pomiędzy węzłami tego samego drzewa, ale także innymi rekordami.

Kategoria:C#