Czy jest jakaś standardowa klasa biblioteki Java do reprezentowania drzewa w Javie?
W szczególności muszę przedstawić następujące informacje:
- Pod-drzewo w dowolnym węźle może mieć dowolną liczbę dzieci
- Każdy węzeł (po katalogu głównym) i jego dzieci będą miały wartość ciągu
- Muszę uzyskać wszystkie elementy potomne (jakąś listę lub tablicę ciągów) danego węzła i jego wartość ciągu (tj. Metodę, która pobierze węzeł jako dane wejściowe i zwróci wszystkie wartości ciągu węzła potomnego jako dane wyjściowe)
Czy istnieje jakaś dostępna struktura do tego, czy też muszę utworzyć własną (jeśli tak, sugestie dotyczące implementacji byłyby świetne).
Odpowiedzi:
Tutaj:
Jest to podstawowa struktura drzewa, której można użyć do
String
dowolnego innego obiektu. Łatwo jest wdrożyć proste drzewa, aby zrobić to, czego potrzebujesz.Wszystko, co musisz dodać, to metody dodawania, usuwania, przechodzenia i konstruktorów. Jest
Node
to podstawowy element składowyTree
.źródło
Tree
klasa nie jest konieczna, ponieważ każdyNode
może być postrzegany jako drzewo.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
hasNext()
przed każdym wywołaniem,next()
aby uzyskać prawidłowe wyniki. To nie jest częśćIterator
specyfikacji.W JDK zaimplementowano całkiem dobrą strukturę drzewa.
Spójrz na javax.swing.tree , TreeModel i TreeNode . Zostały zaprojektowane do użytku z
JTreePanel
ale w rzeczywistości są całkiem dobrą implementacją drzewa i nic nie stoi na przeszkodzie, aby używać go bez interfejsu swing.Zwróć uwagę, że od wersji Java 9 możesz nie chcieć korzystać z tych klas, ponieważ nie będą one obecne w „Kompaktowych profilach” .
źródło
A co z tym?
źródło
setAsParent
lubgetHead
zrobić i jest to czas, kiedy naprawdę można uzyskać pomoc na temat struktur danych drzewo. Nawet oryginalne źródło dokumentu nie ma komentarzy.Ja napisałem małą bibliotekę, która obsługuje rodzajowe drzewa. Jest znacznie lżejszy niż huśtawka. Mam też do tego projekt maven .
źródło
Oczywiście możesz dodać metody narzędzi do dodawania / usuwania dzieci.
źródło
Powinieneś zacząć od zdefiniowania, czym jest drzewo (dla domeny), najlepiej to zrobić , najpierw definiując interfejs . Nie wszystkie struktury drzew można modyfikować, ponieważ można je dodawać i usuwać węzłów powinna być funkcją opcjonalną, dlatego tworzymy dodatkowy interfejs do tego.
Nie ma potrzeby tworzenia obiektów węzłów, które przechowują wartości , w rzeczywistości postrzegam to jako poważną wadę projektową i koszty ogólne w większości implementacji drzew. Jeśli spojrzysz na Swinga,
TreeModel
jest on wolny od klas węzłów (DefaultTreeModel
wykorzystuje tylkoTreeNode
), ponieważ nie są one tak naprawdę potrzebne.Zmienna struktura drzewa (pozwala dodawać i usuwać węzły):
Biorąc pod uwagę te interfejsy, kod wykorzystujący drzewa nie musi zbytnio dbać o sposób implementacji drzewa. Pozwala to na korzystanie zarówno z implementacji ogólnych, jak i specjalistycznych , w których drzewo jest realizowane przez delegowanie funkcji do innego interfejsu API.
Przykład: struktura drzewa plików
Przykład: ogólna struktura drzewa (oparta na relacjach rodzic / dziecko):
źródło
W żadnej odpowiedzi nie wspomniano o zbyt uproszczonym, ale działającym kodzie, więc oto:
źródło
Możesz używać dowolnego interfejsu API języka Java w języku Java jako Dokumentu i Węzła. XML jest strukturą drzewa z ciągami
źródło
Jeśli wykonujesz kodowanie tablicy, wywiad, a nawet po prostu planujesz użyć drzewa, wszystko to jest trochę gadatliwe.
Należy ponadto powiedzieć, że powodem, dla którego nie ma tam drzewa, na przykład
Pair
(o którym można powiedzieć to samo), jest to, że powinieneś hermetyzować swoje dane w klasie, używając go, a najprostsza implementacja wygląda następująco:To naprawdę tyle w przypadku drzewa o dowolnej szerokości.
Jeśli chcesz drzewa binarnego, często łatwiej jest używać nazwanych pól:
Lub jeśli chcesz spróbować:
Teraz powiedziałeś, że chcesz
To brzmi jak twoja praca domowa.
Ale ponieważ jestem dość pewien, że minął termin…
Dzięki temu możesz używać:
źródło
Wzdłuż tych samych wierszy, co odpowiedź Garetha, sprawdź DefaultMutableTreeNode . To nie jest ogólne, ale poza tym wydaje się pasować do rachunku. Mimo że znajduje się w pakiecie javax.swing, nie zależy od żadnych klas AWT ani Swing. W rzeczywistości kod źródłowy ma komentarz
// ISSUE: this class depends on nothing in AWT -- move to java.util?
źródło
W Javie istnieje kilka struktur danych drzewa, takich jak DefaultMutableTreeNode w JDK Swing, pakiet parsera Tree w Stanford i inne kody zabawek. Ale żaden z nich nie jest wystarczający, ale wystarczająco mały do ogólnego zastosowania.
Projekt drzewa Java próbuje dostarczyć inną strukturę danych drzewa ogólnego przeznaczenia w Javie. Różnica między tym a innymi jest
źródło
Ponieważ pytanie dotyczy dostępnej struktury danych, drzewo można zbudować z list lub tablic:
instanceof
można użyć do ustalenia, czy element jest poddrzewem, czy węzłem końcowym.źródło
Object
A to być zarówno przedmioty liści (na przykład,String
S) lub oddziałów (reprezentowanych przez macierze). I to działa: ten kod się skompiluje i utworzy małe drzewoString
s.Tak prosty, jak to tylko możliwe i bardzo łatwy w użyciu. Aby go użyć, rozszerz go:
źródło
Na przykład :
źródło
W przeszłości użyłem do tego zagnieżdżonej mapy. Tego właśnie używam, jest to bardzo proste, ale pasuje do moich potrzeb. Może to pomoże kolejnemu.
źródło
Napisałem małą klasę „TreeMap” opartą na „HashMap”, która obsługuje dodawanie ścieżek:
Można go użyć do przechowywania Drzewa rzeczy typu „T” (ogólne), ale nie obsługuje (jeszcze) przechowywania dodatkowych danych w jego węzłach. Jeśli masz taki plik:
Następnie możesz zrobić z niego drzewo, wykonując:
I dostaniesz ładne drzewo. Powinno być łatwo dostosować się do twoich potrzeb.
źródło
Możesz użyć klasy HashTree zawartej w Apache JMeter, który jest częścią projektu Jakarta.
Klasa HashTree znajduje się w pakiecie org.apache.jorphan.collections. Chociaż ten pakiet nie został wydany poza projektem JMeter, możesz go łatwo uzyskać:
1) Pobierz źródła JMeter .
2) Utwórz nowy pakiet.
3) Skopiuj na niego / src / jorphan / org / apache / jorphan / collections /. Wszystkie pliki oprócz Data.java
4) Skopiuj również /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java
5) HashTree jest gotowy do użycia.
źródło
W Javie nie ma określonej struktury danych, która odpowiada Twoim wymaganiom. Twoje wymagania są dość specyficzne i do tego musisz zaprojektować własną strukturę danych. Patrząc na twoje wymagania, każdy może powiedzieć, że potrzebujesz jakiegoś drzewa n-ary z pewną specyficzną funkcjonalnością. Możesz zaprojektować strukturę danych w następujący sposób:
Sugerowałbym, abyś napisał strukturę węzła w jednej klasie, np. Class Node {Wartość ciągu; Lista potomków;} i wszystkie inne metody, takie jak search, insert i getChildren w innej klasie NodeUtils, dzięki czemu można również przekazać katalog główny drzewa, aby wykonać operację na określonym drzewie, na przykład: class NodeUtils {publiczne statyczne wyszukiwanie węzłów (węzeł główny, wartość ciągu) {// wykonaj BFS i zwróć węzeł}
źródło
źródło
Napisałem bibliotekę drzewa, która ładnie gra z Javą 8 i która nie ma innych zależności. Zapewnia również luźną interpretację niektórych pomysłów z programowania funkcjonalnego i pozwala mapować / filtrować / przycinać / przeszukiwać całe drzewo lub poddrzewa.
https://github.com/RutledgePaulV/prune
Implementacja nie robi nic specjalnego z indeksowaniem i nie oddaliłam się od rekurencji, więc możliwe jest, że przy dużych drzewach wydajność spadnie i możesz zdmuchnąć stos. Ale jeśli wszystko, czego potrzebujesz, to proste drzewo o małej do umiarkowanej głębokości, myślę, że działa wystarczająco dobrze. Zapewnia rozsądną (opartą na wartościach) definicję równości, a także implementację toString, która umożliwia wizualizację drzewa!
źródło
Sprawdź poniższy kod, w którym użyłem struktur danych drzewa, bez używania klas Collection. Kod może zawierać błędy / ulepszenia, ale użyj go tylko w celach informacyjnych
źródło
Możesz użyć klasy TreeSet w java.util. *. Działa jak drzewo wyszukiwania binarnego, więc jest już posortowane. Klasa TreeSet implementuje interfejsy Iterable, Collection i Set. Możesz przechodzić przez drzewo z iteratorem jak zestaw.
Możesz sprawdzić, Java Doc i kilka innych .
źródło
Niestandardowe drzewo implementacji Tree bez korzystania z frameworku Collection. Zawiera różne podstawowe operacje potrzebne do implementacji drzewa.
źródło