Różnica między "Complete binary tree", "strict binary tree", "full binary Tree"?

Doskonały:

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ / \ / \ / \
x x x x x x x x

Complete:

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ /
x x x

Ścisły:

       x
     /   \
    /     \
   x       x
  / \ 
 x   x 
    / \
    x x 

Istnieje różnica między ścisłym i pełnym drzewem binarnym.

1) pełne drzewo binarne: drzewo binarne o wysokości h, które zawiera dokładnie (2^h)-1 elementów nazywa się pełnym drzewem binarnym . (Ref: Pg 427, Data Structures, Algorithms and Applications in C++ [University Press], Second Edition by Sartaj Sahni).

Lub innymi słowy

W pełnym drzewie binarnym każdy węzeł ma dokładnie 0 lub 2 dzieci i wszystkie węzły liści są na tym samym poziom.

Na przykład: Poniżej znajduje się pełne drzewo binarne:

          18
       /      \   
     15       30    
    /  \     /   \   
  40    50  100  40 

2) STRICT BINARY TREE: każdy węzeł ma dokładnie 0 lub 2 dzieci.

Na przykład: Poniżej znajduje się ścisłe drzewo binarne:

         18
       /     \   
     15       30    
    /  \          
  40    50

Myślę, że nie ma żadnego zamieszania w definicji kompletnego drzewa binarnego, ale dla kompletności postu chciałbym powiedzieć, czym jest kompletne drzewo binarne.

3) kompletne drzewo binarne: drzewo binarne jest kompletne Drzewo binarne, jeśli wszystkie poziomy są całkowicie wypełnione, z wyjątkiem ostatniego poziomu, a ostatni poziom ma wszystkie klawisze w lewo, jak to możliwe.

Na przykład: Poniżej znajduje się pełne drzewo binarne:

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9 

Uwaga: Poniżej znajduje się również pełne drzewo binarne:

         18
       /     \   
     15       30    
    /  \     /   \   
  40    50  100  40 

Disclaimer - głównym źródłem niektórych definicji jest wikipedia, wszelkie sugestie poprawy mojej odpowiedzi są mile widziane.

Chociaż ten post ma akceptowaną odpowiedź i jest dobry, nadal byłem w zamieszaniu i chciałbym dodać kilka wyjaśnień dotyczących różnicy między tymi terminami.

(1)pełne drzewo binarne - pełne drzewo binarne jest drzewem binarnym, w którym każdy węzeł inny niż liście ma dwoje dzieci.Jest to również nazywane ściśle drzewo binarne.

Powyższe dwa są przykładami pełnego lub ściśle binarnego drzewa.

(2)COMPLETE BINARY TREE - Teraz definicja complete binary tree jest dość niejednoznaczna, stwierdza: - complete binary tree to drzewo binarne, w którym każdy poziom, z wyjątkiem prawdopodobnie ostatniego , jest całkowicie wypełniony, a wszystkie węzły są tak daleko, jak to możliwe. może mieć od 1 do 2 węzłów, tak daleko jak to możliwe, na ostatnim poziomie h

Zwróć uwagę na linie kursywą.

Dwuznaczność leży w wierszach kursywą, "z wyjątkiem ewentualnie ostatniego", co oznacza, że ostatni poziom może być również całkowicie wypełniony, tzn. ten wyjątek nie zawsze musi być spełniony. Jeśli wyjątek się nie utrzyma, to jest dokładnie taki sam jak drugi obrazek, który opublikowałem, który można również nazwać perfect binary tree . Tak więc doskonałe drzewo binarne jest również pełne i kompletne, ale nie odwrotnie, co będzie jasne przez jeszcze jedną definicję Muszę podać:

Prawie kompletne drzewo binarne - gdy wyjątek w definicji pełnego drzewa binarnego posiada to nazywa się prawie kompletne drzewo binarne lub prawie kompletne drzewo binarne . Jest to po prostu rodzaj kompletnego drzewa binarnego, ale aby uczynić go bardziej jednoznacznym, konieczna jest osobna definicja.

Więc prawie kompletne drzewo binarne będzie wyglądać tak, widać na obrazku węzły są jak najdalej w lewo, więc jest to bardziej podzbiór kompletne drzewo binarne, mówiąc bardziej rygorystycznie każde prawie kompletne drzewo binarne jest kompletnym drzewem binarnym, ale nie odwrotnie . :

Podsumowując z powyższych odpowiedzi, oto dokładna różnica między drzewami binarnymi pełnymi/ściśle, kompletnymi i doskonałymi

1. Pełne / ściśle binarne drzewo : - każdy węzeł z wyjątkiem węzłów liściowych ma dwoje dzieci

2. Complete binary tree: - Każdy poziom oprócz ostatniego poziomu jest całkowicie wypełniony i wszystkie węzły są usprawiedliwione.

3. Perfect binary tree: - każdy węzeł z wyjątkiem węzłów liściowych ma dwoje dzieci i każdy poziom (ostatni poziom też) jest całkowicie wypełniony.

Rozważ drzewo binarne, którego węzły są rysowane w sposób drzewa. Teraz zacznij numerować węzły od góry do dołu i od lewej do prawej. Pełne drzewo ma takie właściwości:

Jeśli n ma dzieci, to wszystkie węzły numerowane mniej niż n mają dwoje dzieci.

Jeśli n ma jedno dziecko, to musi to być lewe dziecko, a wszystkie węzły mniejsze od n mają dwoje dzieci. Ponadto żaden węzeł o numerze większym niż n nie ma dzieci.

Jeśli n nie ma dzieci, to żaden węzeł o numerze większym niż n nie ma dzieci.

Pełne drzewo binarne może być użyte do reprezentowania sterty. Można ją łatwo reprezentować w sąsiedniej pamięci bez przerw(tzn. wszystkie elementy tablicy są używane z wyjątkiem dowolnej przestrzeni, która może istnieć na końcu).

Pełne drzewo binarne są kompletnym drzewem binarnym, ale odwrócenie nie jest możliwe, a jeśli głębokość binarna wynosi n, to nie. z węzłów w pełnym drzewie binarnym jest (2^n-1). W drzewie binarnym nie jest konieczne, aby miało dwoje potomków, ale w pełnym drzewie binarnym każdy węzeł nie ma lub nie ma dwóch Potomków.

Aby zacząć od podstaw, bardzo ważne jest zrozumienie samego drzewa binarnego, aby zrozumieć różne jego typy.

Drzewo jest drzewem binarnym wtedy i tylko wtedy, gdy:-

– posiada węzeł korzeniowy, który może nie mieć żadnych węzłów potomnych (0 childnodes, NULL tree)

- węzeł Root może mieć 1 lub 2 węzły potomne . Każdy taki węzeł tworzy samo drzewo abinarne

- Liczba węzłów potomnych może wynosić 0, 1, 2.......nie więcej niż 2

Przykład:

        X
      /    \
     X      X
          /   \
         X     X

Przychodząc do zapytanych terminologii:

Drzewo binarne jest kompletnym drzewem binarnym (o wysokości h , przyjmujemy węzeł korzeniowy jako 0 ) wtedy i tylko wtedy, gdy: -

Poziom 0 do h-1 reprezentują pełne drzewo binarne wysokości h-1

Jeśli j, k są węzłami na poziomie h-1, to j ma więcej węzłów potomnych niż k wtedy i tylko wtedy, gdy j znajduje się na lewo od k, tzn. na ostatnim poziomie (h) może zabraknąć liścia węzły, jednak obecne muszą być przesunięte w lewo

Przykład:

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 

Drzewo binarne jest ściśle binarnym drzewem wtedy i tylko wtedy, gdy:-

Każdy węzeł ma dokładnie dwa węzły potomne lub nie ma węzłów

Przykład:

         X
       /   \
      X     X 
          /   \
         X      X
        / \    / \ 
       X   X  X   X 

Drzewo binarne jest pełnym drzewem binarnym wtedy i tylko wtedy, gdy:-

Każdy węzeł bez liści ma dokładnie dwa węzły potomne

Wszystkie węzły liści są na tym samym poziomie

Przykład:

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X 

Powinieneś też wiedzieć, jaki idealny binarny drzewo jest?

Drzewo binarne jest doskonałym drzewem binarnym wtedy i tylko wtedy, gdy:-

Przykład:

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X 

Cóż, przykro mi, że nie mogę publikować zdjęć, ponieważ nie mam reputacji 10. Mam nadzieję, że to pomoże Tobie i innym!

W moim ograniczonym doświadczeniu z binary tree myślę:

1. Strictly Binary Tree : każdy węzeł z wyjątkiem węzłów liściowych ma dwoje dzieci lub tylko węzeł korzeniowy.
2. pełne drzewo binarne : drzewo binarne H ściśle (lub dokładnie) zawierające 2^węzły H -1 , to jasne, że każdy poziom ma najwięcej węzłów.
3. Complete binary Tree : jest to drzewo binarne, w którym każdy poziom, z wyjątkiem prawdopodobnie ostatniego, jest całkowicie wypełniony, i wszystkie węzły są tak daleko w lewo, jak to możliwe.

Pełne drzewo binarne jest drzewem binarnym, w którym każdy węzeł ma albo 0, albo dwoje dzieci. Innymi słowy, każdy węzeł w drzewie oprócz liści ma dokładnie dwoje dzieci.

A Complete binary tree to drzewo binarne, w którym każdy poziom drzewa jest całkowicie wypełniony z wyjątkiem ostatniego poziomu. Ponadto, na ostatnim poziomie, węzły powinny być dołączone począwszy od lewej-najbardziej pozycji. pełne drzewo binarne musi spełniać następujące warunki:

• Jeśli A, b są dwoma węzłami na poziomie powyżej ostatniego poziomu, to a ma więcej dzieci niż b wtedy i tylko wtedy, gdy a znajduje się po lewej stronie b.
• z węzła korzeniowego, poziom powyżej ostatniego poziomu reprezentuje pełne drzewo binarne wysokości h-1.
• jeden lub więcej węzłów na ostatnim poziomie może mieć 0 LUB 1 dzieci.