Drzewo binarne



Informacje, które udało nam się zgromadzić na temat Drzewo binarne, zostały starannie sprawdzone i uporządkowane, aby były jak najbardziej przydatne. Prawdopodobnie trafiłeś tutaj, aby dowiedzieć się więcej na temat Drzewo binarne. W Internecie łatwo zgubić się w gąszczu stron, które mówią o Drzewo binarne, a jednocześnie nie podają tego, co chcemy wiedzieć o Drzewo binarne. Mamy nadzieję, że dasz nam znać w komentarzach, czy podoba Ci się to, co przeczytałeś o Drzewo binarne poniżej. Jeśli informacje o Drzewo binarne, które podajemy, nie są tym, czego szukałeś, daj nam znać, abyśmy mogli codziennie ulepszać tę stronę.

.

W informatyce , o drzewo binarne jest struktur danych , które mona przedstawi w formie hierarchii z których kady element nazywa si wze pocztkowy wze miano korze . W drzewie binarnym kady element ma najwyej dwa elementy potomne na niszym poziomie, zwykle nazywane left i right . Z punktu widzenia tych elementów potomnych, element, z którego wywodz si one na wyszy poziom, nazywany jest ojcem .

Na najwyszym poziomie, poziomie 0, znajduje si wze gówny. Na poziomie bezporednio poniej znajduj si co najwyej dwa wzy podrzdne. Kontynuujc schodzenie na nisze poziomy, mona mie cztery, potem osiem, szesnacie itd. to znaczy kolejno potg dwójki . Wze bez dzieci nazywamy liciem .

Poziom wza, innymi sowy odlego midzy tym wzem a korzeniem, nazywana jest gbokoci . Wysoko drzewa jest maksymalna gboko wza. Drzewo zredukowane do pojedynczego wza ma wysoko 1.

Drzewa binarne mog w szczególnoci by uywane jako drzewo wyszukiwania binarnego lub jako sterta binarna .

Definicja w teorii grafów

Teorii wykres stosuje nastpujc definicj: drzewo binarne jest poczony wykres acykliczne , takie jak stopie kadego wza (lub wierzchoek) wynosi co najwyej 3.

Korze drzewa binarnego jest wzem grafu o maksymalnym stopniu 2. Przy tak wybranym korzeniu, kady wze bdzie mia unikalnego, zdefiniowanego rodzica i dwoje dzieci; jednak ta informacja jest niewystarczajca, aby odróni prawego syna od lewego syna. Jeli zaniedbamy ten warunek poczenia, a istnieje wiele poczonych elementów, nazwiemy t struktur lasem.

Rodzaje drzew binarnych

  • Binarny (lub binarnie jednoskadnikowa) drzewo to drzewo z korzeniem w którym kady wze ma co najwyej dwoje dzieci.
  • Surowe lub lokalnie kompletne drzewo binarne to drzewo, w którym wszystkie wzy maj zero lub dwoje dzieci.
  • Zdegenerowane drzewo binarne to drzewo, w którym wszystkie wewntrzne wzy maj tylko jedno dziecko. Ten typ drzewa ma tylko jeden li i moe by widziany jako lista poczona.
  • Idealne drzewo binarne jest surowe drzewo binarne, w którym wszystkie licie (wzy bez dzieci) s w takiej samej odlegoci od korzenia (czyli tej samej gbokoci). Jest to drzewo z wypenionymi wszystkimi poziomami: gdzie wszystkie wzy wewntrzne maj dwoje dzieci i gdzie wszystkie wzy zewntrzne maj t sam wysoko.
  • Kompletne lub prawie kompletne drzewo binarne , którego nie naley myli z lokalnie kompletnym (powyej), to drzewo, w którym wszystkie poziomy s wypenione z moliwym wyjtkiem ostatniego, w którym licie s wyrównane do lewej. Widzimy w nim doskonae drzewo, którego ostatni poziom zostaby pozbawiony niektórych lici, zaczynajc od najbardziej prawego. Innym sposobem spojrzenia na to byoby cise drzewo binarne, w którym licie maj gboko n lub n-1 dla danego n . Ewentualno jest wana: doskonae drzewo jest z koniecznoci prawie kompletne, podczas gdy prawie kompletne drzewo moe by doskonae.

Istniej sprzeczne zastosowania terminów kompletny i doskonay , które mog by uywane w sposób opisany powyej, ale czasami mog by zamieniane. Moe to powodowa zamieszanie lub nieporozumienia, dlatego moemy uy terminu prawie kompletne w odniesieniu do drzewa na ostatnim, prawdopodobnie niewypenionym poziomie. Mog równie istnie pomyki midzy francuskim a angielskim, w których znajdujemy terminy doskonay i kompletny , ponownie z rónymi zastosowaniami w zalenoci od osoby.

Sposób przechowywania drzew binarnych

Drzewa binarne mog by konstruowane z prymitywów jzyka programowania na róne sposoby. W jzyku ze strukturami i wskanikami (lub referencjami ) drzewa binarne mona zaprojektowa, majc struktur trójwzow, która zawiera pewne dane i wskaniki do swojego prawego i lewego dziecka. Kolejno, któr to narzuca wzom podrzdnym, jest czasami przydatna, w szczególnoci w przypadku tras infix. Czasami zawiera równie wskanik do swojego jedynego rodzica. Jeli wze ma mniej ni dwoje dzieci, jednemu z dwóch wskaników mona przypisa specjaln warto zero; moe równie wskazywa na wze wartowniczy.

Drzewa binarne mona równie ukada w tablice, a jeli drzewo jest kompletnym drzewem binarnym, ta metoda nie marnuje miejsca, a wynikowe dane strukturalne s nazywane stert . W tym zwartym ukadzie wze ma indeks i , a (tablica oparta na zerach) jego dzieci maj indeksy 2 i +1 oraz 2 i +2, natomiast jego ojciec (jeli istnieje) ma indeks podogi ( i-1) / 2) . Ta metoda umoliwia korzystanie z mniejszej powierzchni i lepszej referencji, w szczególnoci podczas skanowania prefiksów. Wymaga jednak cigej pamici, jest to kosztowne, jeli chodzi o rozszerzenie drzewa, a utracona przestrze (w przypadku niepenego drzewa binarnego) jest proporcjonalna do 2 h - n dla drzewa o gbokoci h z n wzami .

Mae kompletne drzewo binarne zawarte w tablicy.

W jzykach unii oznaczonych jako ML , wze jest czsto otagowan uni dwóch typów wzów, z których jeden jest trypletem zawierajcym dane i jego prawe i lewe dzieci, a drugi jest pustym wzem, który nie zawiera danych ani funkcji, przypominajc warto null jzyków ze wskanikami.

Metoda iteracji drzewa binarnego

Czsto podane jest odwiedzenie kadego z wzów w drzewie i zbadanie tam wartoci. Istnieje kilka porzdków, w których mona odwiedza wzy, a kady z nich ma przydatne waciwoci, które s wykorzystywane przez algorytmy oparte na drzewie bitowym.

cieka przedrostka, wrostka i przyrostka

(czasami nazywane preorder , inorder i postorder )

Rozwamy drzewo Atypu Arbre, root racine(A)i jego dwoje dzieci gauche(A)oraz droite(A). Moemy napisa nastpujce funkcje (zwró uwag na pozycj linii visiter (A)):

Prefiks trasy

visiterPréfixe(Arbre A) :
    visiter (A)
    Si nonVide (gauche(A))
          visiterPréfixe(gauche(A))
    Si nonVide (droite(A))
          visiterPréfixe(droite(A))

Spowoduje to wywietlenie wartoci drzewa w kolejnoci prefiksów. W tej kolejnoci odwiedzany jest kady wze, a nastpnie kady z jego dzieci.

cieka przyrostka lub sufiksu

visiterPostfixe(Arbre A) :
    Si nonVide(gauche(A))
       visiterPostfixe(gauche(A))
    Si nonVide(droite(A))
       visiterPostfixe(droite(A))
    visiter(A)

W ciece przyrostka lub przyrostka wywietlamy kady wze po wywietleniu kadego z jego dzieci.

Kurs infiksowy

visiterInfixe(Arbre A) :
    Si nonVide(gauche(A))
       visiterInfixe(gauche(A))
    visiter(A)
    Si nonVide(droite(A))
       visiterInfixe(droite(A))

Spacer infix, jak powyej, odwiedza kady wze midzy wzami jego lewego poddrzewa a wzami jego prawego poddrzewa. Jest to do powszechny sposób na iteracj w drzewie wyszukiwania binarnego, poniewa zwraca wartoci w kolejnoci rosncej.

Aby zrozumie, dlaczego tak jest, jeli n jest wzem w drzewie wyszukiwania binarnego, wszystkie elementy w lewym poddrzewie wza n bd mniejsze ni n, a te w prawym poddrzewie bd wiksze lub równe n . Tak wic, jeli odwiedzimy lewe poddrzewo po kolei, rekursywnie, a nastpnie odwiedzimy n i odwiedzimy prawe poddrzewo, odwiedzimy cae zakorzenione poddrzewo w kolejnoci n .

Prosty przykad drzewa binarnego W tym drzewie binarnym
  • Renderowanie prefiksu trasy: 1, 2, 4, 5, 7, 8, 3, 6, 9
  • Renderuj ciek postfix: 4, 7, 8, 5, 2, 9, 6, 3, 1
  • Renderowanie trasy infiksowej: 4, 2, 7, 5, 8, 1, 3, 9, 6
  • Renderowanie trasy w szerokoci: 1, 2, 3, 4, 5, 6, 7, 8, 9

Moemy wykona te trasy za pomoc funkcjonalnego jzyka, takiego jak Haskell, z nastpujcym kodem:

data Tree a = Leaf | Node(a, Tree a, Tree a)

preorder Leaf = []
preorder (Node (x, left,right)) = [x] ++ (preorder left) ++ (preorder right)

postorder Leaf = []
postorder (Node (x, left,right)) = (postorder left) ++ (postorder right) ++ [x]

inorder Leaf = []
inorder (Node (x, left,right)) = (inorder left) ++ [x] ++ (inorder right)

Wszystkie te algorytmy rekurencyjne wykorzystuj stos pamici proporcjonalny do gbokoci drzew. Jeli dodamy w kadym wle odwoanie do jego rodzica, to moemy zaimplementowa wszystkie te cieki, uywajc tylko staych przestrzeni pamici i algorytmu iteracyjnego. Duo miejsca zajmuje jednak odniesienie do rodzica; jest to naprawd przydatne tylko wtedy, gdy jest to wymagane w inny sposób lub gdy stos pamici jest szczególnie ograniczony. Oto na przykad iteracyjny algorytm cieki infiksowej:

VisiterInfixeIteratif(racine)
    precedent    := null
    actuel       := racine
    suivant      := null

    Tant que (actuel != null) Faire
        Si (precedent == pere(actuel)) Alors
            precedent := actuel
            suivant   := gauche(actuel)
        FinSi
        Si (suivant == null OU precedent == gauche(actuel)) Alors
            Visiter(actuel)
            precedent := actuel
            suivant   := droite(actuel)
        FinSi
        Si (suivant == null OU precedent == droite(actuel)) Alors
            precedent := actuel
            suivant   := pere(actuel)
        FinSi
        actuel := suivant
    FinTantQue

Kurs dogbny

Podczas tego spaceru zawsze staramy si odwiedzi wze znajdujcy si najdalej od roota, jaki moemy, pod warunkiem, e jest to dziecko wza, który ju odwiedzilimy. W przeciwiestwie do dogbnego przegldania wykresów, nie trzeba wiedzie, które wzy zostay ju odwiedzone, poniewa drzewo nie zawiera cykli. Trasy prefiksowe, infiksowe i postfiksowe s szczególnymi przypadkami tego typu trasy.

Aby wykona t podró, konieczne jest prowadzenie listy przedmiotów oczekujcych na przetworzenie. W przypadku przegldania dogbnego lista ta musi mie struktur stosu (typu LIFO, Last In, First Out, czyli ostatnie weszo, pierwsze wyszo). W tej implementacji zdecydujemy si równie doda dzieci wza od prawej do lewej.

ParcoursProfondeur(Arbre A) {
   S = Pilevide
   ajouter(Racine(A), S)
   Tant que (S != Pilevide) {
       nud = premier(S)
       retirer(S)
       Visiter(nud) //On choisit de faire une opération
       Si (droite(nud) != null) Alors
           ajouter(droite(nud), S)
       Si (gauche(nud) != null) Alors
           ajouter(gauche(nud), S)
   }
}

Kurs szerokoci

W przeciwiestwie do poprzedniego, ten lad zawsze próbuje odwiedzi wze najbliej korzenia, który nie zosta jeszcze odwiedzony. Podajc t tras najpierw odwiedzimy root, potem wzy na gbokoci 1, potem 2 itd. Std nazwa kurs na szeroko.

Implementacja jest prawie identyczna z tras dogbn, z tym wyjtkiem, e tym razem musimy uy struktury kolejki (typ FIFO, First in, first out, innymi sowy pierwsze weszo, pierwsze wyszo) , co oznacza, e kolejno wyjciowa to nie to samo (tj. zamieniamy lew i praw stron w naszym przetwarzaniu).

ParcoursLargeur(Arbre A) {
   f = FileVide
   enfiler(Racine(A), f)
   Tant que (f != FileVide) {
       nud = defiler(f)
       Visiter(nud)                        //On choisit de faire une opération
       Si (gauche(nud) != null) Alors
           enfiler(gauche(nud), f)
       Si (droite(nud) != null) Alors
           enfiler(droite(nud), f)
   }
}

Przeksztacenie dowolnego drzewa w drzewo binarne

Istnieje wstrzyknicie pomidzy ogólnie posortowanymi drzewami a drzewami binarnymi, które jest specjalnie uywane przez Lisp do przedstawiania ogólnie posortowanych drzew jako drzew binarnych. Kady wze N w posortowanym drzewie odpowiada wzowi N ' w drzewie binarnym; syn na lewo od N 'jest wzem dla pierwszego syna N , a syn na prawo od N ' jest wzem dla nastpnego brata N - który jest kolejnym wzem w kolejnoci wród dzieci ojca N .

Jednym ze sposobów na zobrazowanie tego jest mylenie, e kady syn wza na poczonej licie, kady poczony przez swoje obowizki pola , i e wze ma tylko wskanik na pocztek listy, do swojego lewego pola .

Na przykad w drzewie po lewej A ma 6 dzieci: {B, C, D, E, F, G}. Mona go przekonwertowa na drzewo binarne (jak to po prawej).

Przykad przeksztacenia dowolnego drzewa w drzewo binarne

To drzewo binarne mona traktowa jako oryginalne drzewo pochylone na dugo, z czarnymi bokami po lewej stronie przedstawiajcymi pierwszych synów, a niebieskimi po prawej reprezentujcymi kolejnych braci . Cz drzewa po lewej mona zakodowa w Lispie w ten sposób:

(((MN) HI) CD ((O) (P)) F (L))

które mog by zaimplementowane w pamici jako prawe drzewo binarne, bez liter wzów, które maj lewe dziecko.

Zobacz równie

Algorytmy wykorzystujce drzewa binarne

Poszczególne drzewa binarne

Inne rodzaje drzew

Uwagi i referencje

Mamy nadzieję, że informacje, które zgromadziliśmy na temat Drzewo binarne, były dla Ciebie przydatne. Jeśli tak, nie zapomnij polecić nas swoim przyjaciołom i rodzinie oraz pamiętaj, że zawsze możesz się z nami skontaktować, jeśli będziesz nas potrzebować. Jeśli mimo naszych starań uznasz, że informacje podane na temat _title nie są całkowicie poprawne lub że powinniśmy coś dodać lub poprawić, będziemy wdzięczni za poinformowanie nas o tym. Dostarczanie najlepszych i najbardziej wyczerpujących informacji na temat Drzewo binarne i każdego innego tematu jest istotą tej strony internetowej; kierujemy się tym samym duchem, który inspirował twórców Encyclopedia Project, i z tego powodu mamy nadzieję, że to, co znalazłeś o Drzewo binarne na tej stronie pomogło Ci poszerzyć swoją wiedzę.

Opiniones de nuestros usuarios

Igor Maciejewski

Ładny artykuł z _zmienna.

Thomas Mazurek

To dobry artykuł dotyczący Drzewo binarne. Podaje niezbędne informacje, bez ekscesów.

Wiktor Ostrowski

Artykuł o Drzewo binarne jest kompletny i dobrze wyjaśniony. Nie dodawałbym ani nie usuwał przecinka.

Eugeniusz Godlewski

Uważam, że ten wpis o zmiennej Drzewo binarne jest sformułowany bardzo ciekawie, przypomina mi lata szkolne. Jakie piękne czasy, dzięki za sprowadzenie mnie do nich.

Sonia Nowakowski

Informacje o zmiennej Drzewo binarne są bardzo ciekawe i rzetelne, podobnie jak pozostałe artykuły, które przeczytałem do tej pory, a jest ich już wiele, bo na randkę na Tinderze czekam prawie godzinę i się nie pojawia, więc daje mi to, że mnie to wystawiło. Korzystam z okazji, aby zostawić kilka gwiazdek dla firmy i srać na moje pieprzone życie.