Prawie każdy projekt, który ma jakiś edytowalny model lub dokument, będzie miał strukturę hierarchiczną. Przydaje się zaimplementowanie „węzła hierarchicznego” jako klasy podstawowej dla różnych podmiotów. Często lista połączona (rodzeństwo dziecka, drugi model) jest naturalnym sposobem rozwoju wielu bibliotek klas, jednak dzieci mogą być różnego typu, a prawdopodobnie „ model obiektowy ” nie jest tym, co rozważamy, mówiąc ogólnie o drzewach.
Moja ulubiona implementacja drzewa (węzła) twojego pierwszego modelu to jednowierszowa (w C #):
public class node : List<node> { /* props go here */ }
Dziedzicz z ogólnej listy własnego typu (lub dziedzicz z dowolnej innej ogólnej kolekcji własnego typu). Chodzenie jest możliwe w jednym kierunku: uformuj korzeń w dół (przedmioty nie znają swoich rodziców).
Rodzic tylko drzewa
Innym modelem, o którym nie wspomniałeś, jest ten, w którym każde dziecko ma odniesienie do swojego rodzica:
null
|
+---------+---------------------------------+
| parent |
| root |
+-------------------------------------------+
| | |
+---------+------+ +-------+--------+ +--+-------------+
| parent | | parent | | parent |
| node 1 | | node 2 | | node 3 |
+----------------+ +----------------+ +----------------+
Zwiedzanie tego drzewa jest możliwe tylko na odwrót, zwykle wszystkie te węzły będą przechowywane w kolekcji (tablica, tablica mieszająca, słownik itp.), A węzeł zostanie zlokalizowany poprzez przeszukanie kolekcji według kryteriów innych niż pozycja hierarchiczna w drzewo, które zwykle nie miałoby podstawowego znaczenia.
Te drzewa tylko dla rodziców są zwykle widoczne w aplikacjach bazodanowych. Łatwo jest znaleźć dzieci węzła za pomocą instrukcji „SELECT * WHERE ParentId = x”. Jednak rzadko zdarza się, że są one przekształcane w obiekty klasy węzłów drzewnych jako takie. W aplikacjach stanowych (stacjonarnych) mogą być zawinięte w istniejące kontrolki węzłów drzewa. W aplikacjach bezstanowych (internetowych) nawet to może być mało prawdopodobne. Widziałem narzędzia do generowania klas mapujące ORM generujące błędy przepełnienia stosu podczas generowania klas dla tabel, które mają relację ze sobą (chichot), więc może te drzewa nie są wcale takie powszechne.
dwukierunkowe drzewa żeglowne
Jednak w większości praktycznych przypadków wygodnie jest mieć to, co najlepsze z obu światów. Węzły, które mają listę dzieci, a ponadto znają swojego rodzica: dwukierunkowe drzewa nawigacyjne.
null
|
+--------------------+--------------------+
| parent |
| root |
| child1 child2 child3 |
+--+------------------+----------------+--+
| | |
+---------+-----+ +-------+-------+ +---+-----------+
| parent | | parent | | parent |
| node1 | | node2 | | node3 |
| child1 child2 | | child1 child2 | | child1 child2 |
+--+---------+--+ +--+---------+--+ +--+---------+--+
| | | | | |
Przynosi to wiele innych aspektów do rozważenia:
- Gdzie wdrożyć łączenie i rozłączanie rodzica?
- pozwól zająć się logiką biznesową i pozostaw aspekt poza węzłem (zapomną!)
- węzły mają metody tworzenia potomków (nie zezwalają na zmianę kolejności) (wybór Microsoftu w ich implementacji DOM System.Xml.XmlDocument, co prawie doprowadziło mnie do szału, gdy pierwszy raz go spotkałem)
- Węzły przyjmują element nadrzędny w swoim konstruktorze (nie zezwala na zmianę kolejności)
- we wszystkich metodach add (), insert () i remove () oraz ich przeciążeniach węzłów (zazwyczaj mój wybór)
- Wytrwałość
- Jak chodzić po drzewie podczas utrwalania (pomiń na przykład linki rodzica)
- Jak odbudować dwukierunkowe połączenie po usunięciu serializacji (ponowne ustawienie wszystkich rodziców jako działanie po deserializacji)
- Powiadomienia
- Mechanizmy statyczne (flaga IsDirty), obsługują rekurencyjnie we właściwościach?
- Zdarzenia, bańka w górę przez rodziców, w dół przez dzieci lub w obie strony (na przykład pompa komunikatów systemu Windows).
Teraz, aby odpowiedzieć na pytanie , dwukierunkowe drzewa żeglowne są (w mojej dotychczasowej karierze i dziedzinie) najczęściej używane. Przykładami są implementacja Microsofts System.Windows.Forms.Control lub System.Web.UI.Control w .NET, ale także każda implementacja DOM (Document Object Model) będzie miała węzły, które znają ich element nadrzędny, a także wyliczenie ich dzieci. Powód: łatwość użycia zamiast łatwości implementacji. Są to zwykle klasy podstawowe dla bardziej szczegółowych klas (XmlNode może być podstawą klas Tag, Attribute i Text), a te klasy podstawowe są naturalnymi miejscami do umieszczenia ogólnej architektury serializacji i obsługi zdarzeń.
Tree leży w sercu wielu architektur, a swobodne poruszanie się oznacza szybsze wdrażanie rozwiązań.