Samouczek struktury danych drzewa dla początkujących

Wstęp

Drzewo w oprogramowaniu jest jak drzewo biologiczne, ale z następującymi różnicami:

• Jest wyciągany do góry nogami.
• Ma tylko jeden korzeń i nie ma łodygi.
• Gałęzie wyłaniają się z korzenia.
• Punkt, w którym gałąź startuje z innej gałęzi lub korzeń nazywa się węzłem.
• Każdy węzeł ma wartość.

Gałęzie drzewa oprogramowania są reprezentowane przez linie proste. Dobrym przykładem drzewa oprogramowania, które mogłeś użyć, jest drzewo katalogowe dysku twardego komputera.

Istnieją różne rodzaje drzew. Istnieje ogólne drzewo, z którego pochodzą inne drzewa. Inne drzewa pochodzą przez wprowadzenie ograniczeń do drzewa ogólnego. Na przykład możesz chcieć drzewa, w którym nie więcej niż dwie gałęzie emanują z węzła; Takie drzewo byłoby nazywane drzewem binarnym. W tym artykule opisano ogólne drzewo i jak uzyskać dostęp do wszystkich jego węzłów.

Hiperłącze do pobrania kodu jest podane na dole tego artykułu.

Aby zrozumieć próbki kodu w tym artykule, musisz mieć podstawową wiedzę w JavaScript (EcMascript). Jeśli nie masz tej wiedzy, możesz ją uzyskać z http: // www.szeroka sieć.COM/CHRYSANTHUSFORCHA-1/ECMASCRIPT-2015-Course.HTM

Ogólny schemat drzewa

„A” jest węzłem głównym; jest to węzeł pierwszego poziomu. B, C, D są na drugiej linii; To są węzły drugiego poziomu. E, f, g, h, i, j, k są na trzeciej linii i są węzłami trzeciego poziomu. Czwarta linia wytworzyłaby węzły na czwartym poziomie i tak dalej.

Właściwości drzewa

- Wszystkie gałęzie dla wszystkich poziomów węzłów mają jedno źródło, które jest węzłem głównym.

- Drzewo ma n - 1 gałęzie, gdzie n jest całkowitą liczbą węzłów. Powyższy schemat dla ogólnego drzewa ma 11 węzłów i 10 gałęzi.

- W przeciwieństwie do ludzi, gdzie każde dziecko ma dwoje rodziców, z drzewem oprogramowania, każde dziecko ma tylko jednego rodzica. Węzeł główny jest największym rodzicem przodków. Rodzic może mieć więcej niż jedno dziecko. Każdy węzeł, z wyjątkiem węzła głównego, jest dzieckiem.

Słownictwo drzewne

• Węzeł główny: To najwyższy węzeł na drzewie i nie ma rodzica. Każdy inny węzeł ma rodzica.
• Węzły liściowe: Węzeł liściowy to węzeł, który nie ma dziecka. Zwykle znajdują się na dnie drzewa, a czasem znajdują się po lewej i/lub prawej stronie drzewa.
• Klucz: To jest wartość drzewa. Może to być liczba; może to być ciąg; Może to być nawet operator taki jak + lub - lub x.
• Poziomy: Węzeł główny jest na pierwszym poziomie. Jego dzieci są na drugim poziomie; Dzieci węzłów drugiego poziomu są na trzecim poziomie i tak dalej.
• Węzeł nadrzędny: Każdy węzeł, z wyjątkiem węzła głównego, ma podłączony do niego węzeł nadrzędny. Każdy węzeł, z wyjątkiem węzła głównego, jest węzłem dziecięcym.
• Węzły rodzeństwa: Węzły rodzeńskie to węzły, które mają tego samego rodzica.
• Ścieżka: Gałęzie (linie proste), które łączą jeden węzeł do drugiego, przez inne węzły, tworzą ścieżkę. Gałęzie mogą, ale nie muszą być strzałkami.
• Węzeł przodka: Wszystkie wyższe węzły połączone z dzieckiem, w tym rodzic i węzeł główny, są węzłami przodków.
• Węzeł potomków: Wszystkie dolne węzły podłączone do węzła, w prawo do podłączonych liści, są potomkami. Węzeł, o którym mowa, nie jest częścią potomków. Węzeł, o którym mowa, nie musi być węzłem głównym.
• Przejście: Węzeł plus wszystkich jego potomkowie aż do powiązanych liści. Węzeł początkowy jest uwzględniony i nie musi to być root; W przeciwnym razie byłoby to całe drzewo.
• Stopień: Liczba dzieci, jaką ma węzeł, nazywa się stopniem węzła.

Przemierzanie wszystkich węzłów drzewa

Wszystkie węzły drzewa można uzyskać do odczytu lub zmiany dowolnej wartości węzła. Nie jest to jednak arbitralnie. Istnieją trzy sposoby na to, z których wszystkie obejmują przejście do głębokości, w następujący sposób:

1) W rzędu: Mówiąc wprost, w tym schemacie lewy poddrzewa jest najpierw przemierzana; Następnie dostęp jest dostępny do węzła głównego; Następnie prawy poddrzewa jest przemierzana. Ten schemat jest symbolizowany jako lewy-> root-> prawy. Ryc. 1 jest tutaj ponownie obchodzony w celu łatwego odniesienia:

Zakładając, że na węzeł jest dwa rodzeństwo; następnie lewy-> root-> prawy oznacza, że ​​najpierw uzyskujesz dostęp do najniższego i najwcześniejszego węzła, a następnie nadrzędnego węzła, a następnie prawego rodzeństwa. Gdy jest więcej niż dwa rodzeństwo, weź pierwszy jako lewy i reszta prawych węzłów, jako prawą. W przypadku ogólnego drzewa powyżej dostęp do dolnego lewego poddrzecza, aby mieć [EBF]. To jest poddrzewa. Rodzicem tego poddrzewa jest; Tak więc jest następny dostęp do [EBF]. Następnie dostęp jest dostępny w poddrzew [Gchi], aby mieć większy poddrzewa, [[EBF] A [Gchi]]. Możesz zobaczyć lewy-> root-> prawy profil przedstawiający sam. W tym wielkim lewym poddrzewaniu będzie miał poddanie, [JDK] po prawej stronie do ukończenia przejścia do uzyskania, [[ebf] A [gchi]] [jdk].

2) zamówienie w przedsprzedaży: Mówiąc wprost, na tym schemacie najpierw dostęp do węzła głównego, wówczas lewe poddrzewa jest przecinane następne, a następnie prawe poddrzewa jest przemierzane. Ten schemat jest symbolizowany jako root-> lewy-> prawy. Ryc. 1 jest tutaj ponownie przesyłany dla łatwego odniesienia.

Zakładając, że na węzeł jest dwa rodzeństwo; Następnie root-> lewy-> prawy oznacza, że ​​najpierw uzyskujesz dostęp do korzenia, a następnie lewe natychmiastowe dziecko, a następnie prawe natychmiastowe dziecko. Gdy jest więcej niż dwa rodzeństwo, weź pierwszy jako lewy i reszta prawych węzłów, jako prawą. Najbardziej lewe dziecko lewego dziecka jest następnym, do którego można uzyskać dostęp. Dla ogólnego drzewa powyżej poddrzewa korzeni to [ABCD]. Po lewej stronie tego poddani masz poddrzewa, [EF], podając sekwencję dostępu, [ABCD] [EF]. Po prawej stronie tego większego poddrzew, masz dwa poddrzewa, [GHI] i [JK], podając pełną sekwencję, [ABCD] [EF] [GHI] [JK]. Możesz zobaczyć root-> lewy-> prawy profil przedstawiający sam.

3) Po zamówieniu: Po prostu umieszczaj, w tym schemacie lewe poddrzewa jest najpierw przecinane, a następnie prawe poddrzewa jest przemierzane, a następnie dostęp do korzenia jest dostępny. Ten schemat jest symbolizowany jako lewy-> prawy-> root. Ryc. 1 jest tutaj ponownie przesyłany dla łatwego odniesienia.

W przypadku tego drzewa poddani są [EFB], [ghic], [jkd] i [a], które tworzą sekwencję, [efb], [ghic], [jkd] [a]. Możesz zobaczyć lewy-> prawy-> Profil korzeniowy przedstawiający sam.

Tworzenie drzewa

Powyższe drzewo zostanie utworzone za pomocą EcMascript, które jest jak najnowsza wersja JavaScript. Każdy węzeł jest tablicą. Pierwszym elementem każdej tablicy węzłów jest nadrzędny węzeł, inna tablica. Reszta elementów węzła to dzieci węzła, zaczynając od lewej strony. Istnieje mapa ECMAScript, która odnosi każdą tablicę z odpowiednim ciągiem (litera). Pierwszy segment kodu to:

O = nowa tablica ();
A = nowa tablica ();
B = nowa tablica ();
C = nowa tablica ();
D = nowa tablica ();
//liście
E = nowa tablica (b); F = nowa tablica (b); G = nowa tablica (c); H = nowa tablica (c);
I = nowa tablica (c); J = nowa tablica (d); K = nowa tablica (d);
// Dodanie treści
O [0] = niezdefiniowany; O [1] = a;
A [0] = o; A [1] = b; A [2] = c; A [3] = d;
B [0] = a; B [1] = e; B [2] = f;
C [0] = a; C [1] = g; C [2] = h; C [3] = i;
D [0] = a; D [1] = j; D [2] = k;
// Mapowanie obiektów na litery
pary = [[a, 'a'], [b, 'b'], [c, 'c'], [d, 'd'], [e, 'e'], [f, 'f'] , [G, „g”],
[H, 'h'], [i, 'i'], [j, 'j'], [k, 'k']];
mapobj = nowa mapa (pary);

W ECMAScript możesz uzyskać dostęp do funkcji zdefiniowanej niżej w programie. Jednak ze zmiennymi nie możesz tego zrobić. Nie możesz uzyskać dostępu do zmiennej zdefiniowanej dolnej w dół w programie. To jest powód, dla którego powyższe zmienne zostały opracowane, jak pokazano.

Należy również zauważyć, że powyżej węzła głównego A jest inny węzeł O (nie zero). Pierwszy element tej tablicy (węzeł) jest niezdefiniowany, co oznacza, że ​​jego własny rodzic jest niezdefiniowany. Dodano dodatkowy węzeł o, aby ułatwić kod przemieszczania.

Jest też mapa. Mapa dotyczy każdej tablicy nazw jednej liter, do odpowiedniej nazwy ciągu jednej litery.

Funkcja rekurencyjna

Aby uzyskać dostęp do wszystkich elementów drzewa, potrzebujesz funkcji rekurencyjnej. Funkcja rekurencyjna jest funkcją, która wciąż się wywołuje, aż do spełnienia stanu.

Odwiedzanie węzła niekoniecznie oznacza dostęp do węzła. Aby uzyskać dostęp do węzła, oznacza, że ​​jego wartość jest odczytana lub zmieniona. W próbkach kodu tego artykułu dostęp do węzła oznacza odczyt i wyświetlanie wartości (klucza) węzła. W próbkach kodu węzeł można odwiedzić więcej niż raz, ale jego wartość jest dostępna tylko raz.

Algorytm i programowanie

Istnieje jeden program dla każdej z trzech technik przemieszczania.

Algorytm i programowanie na zamówienie

Tutaj najniższy i najbardziej lewy węzeł jest odwiedzany najpierw. [EBF], [[EBF] A [Gchi]] i [JDK] opracowano, aby nadać pełną sekwencję, [[EBF] A [Gchi]] [JDK].

Istnieją dwie funkcje rekurencyjne dla tego programu, w których każda z nich wywołuje drugą. Główny nazywa się FN (węzeł). Program (kod) jest krótki. Pobierz połączony plik poniżej, aby uzyskać szczegółowe kodowanie.

Trzy programy mają tę samą konfigurację drzewa tablicy (węzeł).

Algorytm i programowanie w przedsprzedaży

Tutaj jest tylko jedna funkcja rekurencyjna. Nazywa się, fn (węzeł). Tutaj opracowano [ABCD], [EF], [GHI] i [JK], aby podać pełną sekwencję, [ABCD] [EF] [GHI] [JK]. Program tego jest również krótki.

Trzy programy mają tę samą konfigurację drzewa tablicy (węzeł).

Algorytm i programowanie po zamówieniu

Tutaj najniższy i najbardziej lewy węzeł jest odwiedzany najpierw. [EFB], [Ghic], [jkd] i [a] są opracowywane w celu podania pełnej sekwencji, [efb], [ghic], [jkd] [a] .

Istnieją dwie funkcje rekurencyjne dla tego programu, w których każda z nich wywołuje drugą. Główny nazywa się FN (węzeł). Program tego jest również krótki. Pobierz połączony plik poniżej, aby uzyskać szczegółowe kodowanie.

Trzy programy mają tę samą konfigurację drzewa tablicy (węzeł).

Rodzaje drzew

Komputerowe drzewa są w rzeczywistości nieliniowe struktury danych. Liniowe struktury danych to listy, tablice, stosy, kolejki, stosy itp. Drzewo z n węzłami ma gałęzie N-1. Gdy liczba gałęzi jest równa lub większa niż liczba węzłów, uzyskuje się wykres. Wykres nie jest tak naprawdę drzewem.

Istnieją drzewa oprogramowania, które opisują układy, takie jak drzewo katalogowe na dysku twardym komputera. Wiele drzew w ogóle nie opisuje istniejących układów. W rzeczywistości opisują algorytmy. Na przykład algorytm matematyczny (x + y) x (x -y) jest opisany przez drzewo, w którym x jest węzłem korzeniowym, a następnie + i - są bezpośrednimi węzłami dziecięcymi korzenia. x i y są węzłami dziecięcymi +. x i y są znowu węzłami dziecięcymi -. Takie drzewo jest znane jako drzewo ekspresowe.

Wiele różnych rodzajów drzew można podzielić na różne nagłówki; takie jak drzewo binarne, drzewo B, drzewo ekspresowe itp. Wszystkie z nich pochodzą z ogólnego drzewa.

Niektóre kategorie drzew są podzielone na kolejne kategorie. Na przykład drzewo binarne ma przynajmniej binarne drzewo wyszukiwania, drzewo avl i drzewo kartezjańskie.

Ściąganie

W tym artykule przewidziano trzy programy. Istnieje jeden program dla techniki na zamówieniu (algorytm), inny dla techniki w przedsprzedaży, a jeszcze jeden dla techniki po zamówieniu. Wszystkie zostały umieszczone w jednym pliku zip, zwanym traversing. Plik zip można pobrać na: github.

Wniosek

Drzewo oprogramowania jest jak normalne drzewo w parku lub lesie. Jednak drzewo programowania komputerowego jest odwrócone. Istnieją różne rodzaje drzew. Inne drzewa pochodzą przez wprowadzenie ograniczeń do drzewa ogólnego. Do wszystkich węzłów drzewa można uzyskać za pomocą algorytmu w przedsprzedaży, w przedsprzedaży lub po zamówieniu. Drzewo oprogramowania może być wytwarzane przez dowolny język komputerowy. EcMascript został tutaj wybrany, ponieważ jest to najprostszy język komputerowy. Kolejnym typem drzewa, które powinieneś się uczyć, jest drzewo binarne, ponieważ jest to najpopularniejsza struktura danych drzew.