Szukałem struktury danych drzewa lub wykresu w języku C #, ale chyba nie ma takiej. Wyczerpujące badanie struktur danych za pomocą C # 2.0 wyjaśnia nieco dlaczego. Czy istnieje wygodna biblioteka, która jest powszechnie używana do zapewnienia tej funkcjonalności? Być może poprzez strategię rozwiązywania problemów przedstawionych w artykule.
Czuję się trochę głupio, wdrażając własne drzewo, podobnie jak implementuję własną ArrayList.
Chcę tylko ogólne drzewo, które może być niezrównoważone. Pomyśl o drzewie katalogów. C5 wygląda sprytnie, ale ich struktury drzew wydają się być zaimplementowane jako zrównoważone czerwono-czarne drzewa lepiej nadające się do wyszukiwania niż reprezentujące hierarchię węzłów.
c#
data-structures
stymuluje
źródło
źródło
Odpowiedzi:
Moja najlepsza rada byłaby taka, że nie ma standardowej struktury danych drzewa, ponieważ istnieje tak wiele sposobów jej implementacji, że niemożliwe byłoby objęcie wszystkich baz jednym rozwiązaniem. Im bardziej konkretne rozwiązanie, tym mniej prawdopodobne, że będzie ono miało zastosowanie do danego problemu. Denerwuje mnie nawet LinkedList - co jeśli chcę okrągłej listy łączy?
Podstawową strukturą, którą musisz zaimplementować, będzie kolekcja węzłów, a oto kilka opcji na dobry początek. Załóżmy, że węzeł klasy jest klasą bazową całego rozwiązania.
Jeśli potrzebujesz tylko nawigować w dół drzewa, klasa Node potrzebuje listy dzieci.
Jeśli potrzebujesz nawigować w górę drzewa, klasa Node potrzebuje łącza do swojego węzła nadrzędnego.
Zbuduj metodę AddChild, która zajmie się wszystkimi szczegółami tych dwóch punktów i wszelkimi innymi logikami biznesowymi, które muszą zostać zaimplementowane (limity potomne, sortowanie dzieci itp.)
źródło
Prosta rekurencyjna implementacja ... <40 linii kodu ... Musisz tylko zachować odniesienie do katalogu głównego drzewa poza klasą lub zawinąć w inną klasę, może zmienić nazwę na TreeNode?
źródło
Action<T>
delegata:public void traverse(NTree<T> node, Action<T> visitor)
. Akcja <> 's podpis jest:void Action<T>( T obj )
. Istnieją również wersje od 0 do 4 różnych parametrów. Istnieje również analogiczny delegat dla wywoływanych funkcjiFunc<>
.--i == 0
zadziała tylko w jednym przypadku? Czy to prawda. To mnie pomieszałoOto moja, bardzo podobna do Aarona Gage'a , moim zdaniem nieco bardziej konwencjonalna. Dla moich celów nie napotkałem żadnych problemów z wydajnością
List<T>
. W razie potrzeby przejście do LinkedList byłoby łatwe.źródło
public TreeNode<T> InsertChild(TreeNode<T> parent, T value) { var node = new TreeNode<T>(value) { Parent = parent }; parent._children.Add(node); return node; }
var five = myTree.AddChild(5); myTree.InsertChild(five, 55);
Jeszcze inna struktura drzewa:
Przykładowe użycie:
BONUS
Zobacz pełne drzewo z:
https://github.com/gt4dev/yet-another-tree-structure
źródło
node
pochodzi? Czy to oznacza, że muszę iterować po drzewie, aby użyć kodu wyszukiwania?IEnumerable<>
członków, więc się nie kompiluje.Ogólnie doskonała ogólna biblioteka kolekcji C5 ma kilka różnych struktur danych opartych na drzewach, w tym zestawy, torby i słowniki. Kod źródłowy jest dostępny, jeśli chcesz przestudiować szczegóły jego implementacji. (Użyłem kolekcji C5 w kodzie produkcyjnym z dobrymi wynikami, chociaż nie użyłem żadnej konkretnej struktury drzewa).
źródło
Zobacz http://quickgraph.codeplex.com/
QuickGraph zapewnia ogólne struktury danych i algorytmy ukierunkowanych / niekierowanych grafów dla .Net 2.0 i wyższych. QuickGraph jest wyposażony w algorytmy, takie jak głębokość pierwszego wyszukiwania, pierwsze wyszukiwanie oddechu, wyszukiwanie A *, najkrótsza ścieżka, k-najkrótsza ścieżka, maksymalny przepływ, minimalne drzewo opinające, najmniej powszechni przodkowie itp. QuickGraph obsługuje MSAGL, GLEE i Graphviz do renderuj wykresy, serializację do GraphML itp.
źródło
Jeśli chcesz napisać własny, możesz zacząć od tego sześcioczęściowego dokumentu szczegółowo opisującego efektywne wykorzystanie struktur danych C # 2.0 i jak zacząć analizować implementację struktur danych w C #. Każdy artykuł zawiera przykłady i instalatora z przykładami, które możesz śledzić.
„Wszechstronne badanie struktur danych za pomocą C # 2.0” Scott Mitchell
źródło
Mam małe rozszerzenie do rozwiązań.
Korzystając z rekurencyjnej deklaracji ogólnej i pochodnej podklasy, możesz lepiej skoncentrować się na rzeczywistym celu.
Zauważ, że różni się od implementacji innej niż ogólna, nie musisz rzutować „node” w „NodeWorker”.
Oto mój przykład:
źródło
Oto moje własne:
Wynik:
źródło
Wypróbuj tę prostą próbkę.
źródło
Tworzę klasę Node, która może być pomocna dla innych osób. Klasa ma właściwości takie jak:
Istnieje również możliwość przekonwertowania płaskiej listy elementów o Id i ParentId na drzewo. Węzły zawierają odniesienie zarówno do dzieci, jak i rodzica, dzięki czemu iteracja węzłów jest dość szybka.
źródło
Ponieważ nie wspomniano o tym, chciałbym zwrócić uwagę na uwolnioną teraz bazę kodu .net: w szczególności kod dla
SortedSet
implementacji Red-Black-Tree:https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/sortedset.cs
Jest to jednak zrównoważona struktura drzewa. Więc moja odpowiedź jest bardziej odniesieniem do tego, co uważam za jedyną natywną strukturę drzewa w bibliotece rdzenia .net.
źródło
Ukończyłem kod udostępniony przez @Berezh.
źródło
Oto drzewo
Możesz nawet użyć inicjatorów:
źródło
Większość drzew składa się z przetwarzanych danych.
Innym przykładem jest parsowanie drzewa w kompilatorze…
Oba te przykłady pokazują, że koncepcja drzewa jest częścią domeny danych, a użycie osobnego drzewa ogólnego przeznaczenia co najmniej podwaja liczbę tworzonych obiektów, a także utrudnia programowanie interfejsu API.
Chcemy sposobu ponownego wykorzystania standardowych operacji na drzewach, bez konieczności ich ponownego wdrażania dla wszystkich drzew, przy jednoczesnym braku konieczności używania standardowej klasy drzewa. Boost próbował rozwiązać ten problem w C ++, ale jeszcze nie widziałem żadnego efektu dla .NET.
źródło
Dodałem kompletne rozwiązanie i przykład, używając klasy NTree powyżej, dodałem również metodę „AddChild” ...
za pomocą
źródło
Oto moja implementacja BST
źródło
Jeśli zamierzasz wyświetlić to drzewo w GUI, możesz użyć TreeView i TreeNode . (Podejrzewam, że technicznie można utworzyć TreeNode bez nakładania go na GUI, ale ma on większy narzut niż prosta implementacja TreeNode u siebie).
źródło
Jeśli potrzebujesz implementacji struktury danych zrootowanych drzew, która zużywa mniej pamięci, możesz napisać klasę Node w następujący sposób (implementacja C ++):
źródło