Unterschied zwischen "Vollständiger Binärbaum", "Strenger Binärbaum", "Vollständiger Binärbaum"?

80

Ich bin verwirrt über die Terminologie der folgenden Bäume, habe den Baum studiert und kann nicht zwischen diesen Bäumen unterscheiden:

a) Vervollständigen Sie den Binärbaum

b) Strenger Binärbaum

c) Vollständiger Binärbaum

Bitte helfen Sie mir, zwischen diesen Bäumen zu unterscheiden. Wann und wo werden diese Bäume in der Datenstruktur verwendet?

kTiwari
quelle
2
Hat en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees Ihre Frage nicht beantworten?
Rodion
6
Nein, es ist nicht, viel Verwirrung unter diesen
kTiwari
1
Strenger Binärbaum: Jeder Knoten kann 2
untergeordnete

Antworten:

73

Wikipedia gab nach

Ein vollständiger Binärbaum (manchmal richtiger Binärbaum oder 2-Baum oder streng binärer Baum) ist ein Baum, in dem jeder Knoten außer den Blättern zwei Kinder hat.

Sie haben also keine Knoten mit nur 1 Kind. Scheint mit einem strengen Binärbaum identisch zu sein.

Hier ist ein Bild eines vollständigen / strengen Binärbaums von Google:

Geben Sie hier die Bildbeschreibung ein

Ein vollständiger Binärbaum ist ein Binärbaum, in dem jede Ebene, außer möglicherweise die letzte, vollständig gefüllt ist und alle Knoten so weit wie möglich links liegen.

Es scheint einen ausgeglichenen Baum zu bedeuten.

Hier ist ein Bild eines vollständigen Binärbaums von Google. Ein vollständiger Baumteil des Bildes ist ein Bonus.

Geben Sie hier die Bildbeschreibung ein

Sam, ich bin, sagt Reinstate Monica
quelle
34
Ihr vollständiges Baumbeispiel erfüllt auch die Kriterien, ein vollständiger Binärbaum zu sein, sodass der Unterschied anscheinend unscharf ist. Meiner Meinung nach möchten Sie vielleicht ein Beispiel für einen vollständigen Baum geben, der kein vollständiger Binärbaum ist, und umgekehrt Antwort vollständig :)
0decimal0
1
Es gibt einen Unterschied zwischen einem vollständigen Binärbaum und einem streng binären Baum. Siehe die Antwort: stackoverflow.com/a/32064101/5237727
Saurabh Bhatia
2
Während alle vollständigen Bäume ausgeglichene Bäume sind, sind alle ausgeglichenen Bäume nicht unbedingt vollständige Bäume.
Sfarbota
1
Was bedeutet es, dass jedes Level vollständig gefüllt ist?
lolololol ol
2
@lololololol bedeutet, dass alle Knoten vorhanden sind, die sich möglicherweise in dieser Ebene befinden können.
Sam ich bin sagt Reinstate Monica
86

Perfekter Baum:

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

Kompletter Baum:

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

Strenger / voller Baum:

       x
     /   \
    /     \
   x       x
  / \ 
 x   x 
    / \
    x x 
Japreiss
quelle
4
Mit perfektem Binärbaum meinen Sie den vollständigen Binärbaum, auf den sich das OP bezieht?
RBT
3
Der perfekte Binärbaum ist sowohl ein strikter / vollständiger Binärbaum als auch ein vollständiger Binärbaum, aber umgekehrt ist dies möglicherweise nicht immer der Fall.
Neo
51

Es gibt einen Unterschied zwischen einem strengen und einem vollständigen binären Baum.

1) VOLLSTÄNDIGER BINÄRBAUM: Ein Binärbaum der Höhe h, der genau (2 ^ h) -1 Elemente enthält, wird als vollständiger Binärbaum bezeichnet . (Ref: S. 427, Datenstrukturen, Algorithmen und Anwendungen in C ++ [University Press], 2. Auflage von Sartaj Sahni).

oder mit anderen Worten

In einem FULL BINARY TREE hat jeder Knoten genau 0 oder 2 untergeordnete Knoten und alle Blattknoten befinden sich auf derselben Ebene.

Zum Beispiel: Das Folgende ist ein VOLLSTÄNDIGER BINÄRBAUM:

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

2) STRICT BINARY TREE: Jeder Knoten hat genau 0 oder 2 Kinder.

Zum Beispiel: Das Folgende ist ein STRICT BINARY TREE:

         18
       /     \   
     15       30    
    /  \          
  40    50

Ich denke, es gibt keine Verwirrung in der Definition eines vollständigen Binärbaums, dennoch möchte ich zur Vollständigkeit des Beitrags sagen, was ein vollständiger Binärbaum ist.

3) VOLLSTÄNDIGER BINÄRBAUM: Ein Binärbaum ist vollständig Binärbaum, wenn alle Ebenen vollständig gefüllt sind, außer möglicherweise die letzte Ebene und die letzte Ebene hat alle Schlüssel so weit wie möglich übrig.

Zum Beispiel: Das Folgende ist ein KOMPLETTER BINÄRBAUM:

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

Hinweis: Das Folgende ist auch ein vollständiger Binärbaum:

         18
       /     \   
     15       30    
    /  \     /   \   
  40    50  100  40 
Saurabh Bhatia
quelle
Können Sie eine Quelle für die vollständige Definition des Binärbaums angeben? Es widerspricht dem auf Wikipedia , das vom NIST bezogen wird .
Calvin Li
@CalvinLi Die Quelle wird in der Definition von FULL BINARY TREE erwähnt. Hier ist ein Link des PDF (S. 447 des PDF) - o6ucs.files.wordpress.com/2012/10/…
Saurabh Bhatia
@SaurabhBhatia, die letzte Darstellung gilt auch für den vollständigen Binärbaum. Korrigiere mich, wenn ich falsch liege. Wie kann eine Darstellung für verschiedene Sorten gelten?
Rose
10

Haftungsausschluss - Die Hauptquelle einiger Definitionen ist Wikipedia. Jeder Vorschlag zur Verbesserung meiner Antwort ist willkommen.

Obwohl dieser Beitrag eine akzeptierte und gute Antwort hat, war ich immer noch verwirrt und möchte weitere Erläuterungen zum Unterschied zwischen diesen Begriffen hinzufügen.

(1) VOLLSTÄNDIGER BINÄRBAUM - Ein vollständiger Binärbaum ist ein Binärbaum, in dem jeder Knoten außer den Blättern zwei Kinder hat. Dies wird auch als streng binärer Baum bezeichnet .

Geben Sie hier die Bildbeschreibung ein Geben Sie hier die Bildbeschreibung ein

Die beiden oben genannten sind Beispiele für einen vollständigen oder streng binären Baum.

(2) VOLLSTÄNDIGER BINÄRBAUM - Nun ist die Definition des vollständigen Binärbaums ziemlich mehrdeutig und besagt: - Ein vollständiger Binärbaum ist ein Binärbaum, in dem jede Ebene, außer möglicherweise die letzte , vollständig gefüllt ist und alle Knoten wie sind ganz links wie möglich. Es kann auf der letzten Ebene h so weit wie möglich zwischen 1 und 2 Stunden Knoten haben

Beachten Sie die kursiven Zeilen.

Die Mehrdeutigkeit liegt in den kursiven Zeilen "außer möglicherweise der letzten", was bedeutet, dass die letzte Ebene auch vollständig ausgefüllt sein kann, dh diese Ausnahme muss nicht immer erfüllt sein. Wenn die Ausnahme nicht zutrifft, entspricht sie genau dem zweiten Bild, das ich gepostet habe und das auch als perfekter Binärbaum bezeichnet werden kann . Ein perfekter Binärbaum ist also auch vollständig und vollständig, aber nicht umgekehrt, was durch eine weitere Definition deutlich wird, die ich angeben muss:

FAST VOLLSTÄNDIGER BINÄRBAUM - Wenn die Ausnahme in der Definition des vollständigen Binärbaums gilt, wird sie als fast vollständiger Binärbaum oder nahezu vollständiger Binärbaum bezeichnet. Es ist nur eine Art vollständiger Binärbaum selbst, aber eine separate Definition ist erforderlich, um ihn eindeutiger zu machen.

Ein fast vollständiger Binärbaum sieht also so aus. Sie können im Bild sehen, dass die Knoten so weit wie möglich links liegen. Es handelt sich also eher um eine Teilmenge eines vollständigen Binärbaums, genauer gesagt, jeder fast vollständige Binärbaum ist eine vollständige Binärdatei Baum, aber nicht umgekehrt. ::

Geben Sie hier die Bildbeschreibung ein

0decimal0
quelle
6

Abschließend aus den obigen Antworten: Hier ist der genaue Unterschied zwischen vollständigen / streng, vollständigen und perfekten Binärbäumen

  1. Vollständiger / streng binärer Baum : - Jeder Knoten außer den Blattknoten hat zwei untergeordnete Knoten

  2. Vollständiger Binärbaum : - Jede Ebene außer der letzten Ebene ist vollständig gefüllt und alle Knoten sind linksbündig.

  3. Perfekter Binärbaum : - Jeder Knoten außer den Blattknoten hat zwei untergeordnete Knoten und jede Ebene (auch die letzte Ebene) ist vollständig gefüllt.

pantech
quelle
2

Stellen Sie sich einen Binärbaum vor, dessen Knoten baumartig gezeichnet sind. Beginnen Sie nun mit der Nummerierung der Knoten von oben nach unten und von links nach rechts. Ein vollständiger Baum hat folgende Eigenschaften:

Wenn n Kinder hat, haben alle Knoten, die kleiner als n sind, zwei Kinder.

Wenn n ein Kind hat, muss es das linke Kind sein und alle Knoten unter n haben zwei Kinder. Außerdem hat kein Knoten, der größer als n ist, untergeordnete Knoten.

Wenn n keine Kinder hat, hat kein Knoten, der größer als n ist, Kinder.

Ein vollständiger Binärbaum kann verwendet werden, um einen Heap darzustellen. Es kann leicht in einem zusammenhängenden Speicher ohne Lücken dargestellt werden (dh alle Array-Elemente werden verwendet, außer für den am Ende vorhandenen Platz).

Craig Wright
quelle
2

Vollständiger Binärbaum ist ein vollständiger Binärbaum, aber eine Umkehrung ist nicht möglich, und wenn die Tiefe der Binärdatei n ist, ist die Nr. Die Anzahl der Knoten im vollständigen Binärbaum beträgt (2 ^ n-1). Im Binärbaum ist es nicht erforderlich, dass er zwei Kinder hat, aber in der vollständigen Binärdatei hat jeder Knoten kein oder zwei Kinder.

Raghvendra Singh Thakur
quelle
1
Sie können nicht streng sagen, dass "Umkehrung nicht möglich ist". Tatsächlich wird Ihre Annahme im Beispiel eines vollständigen Baums in der akzeptierten Antwort
widerlegt.
1
Wenn die Tiefe der Binärdatei n ist, ist die Nr. Die Anzahl der Knoten im vollständigen Binärbaum ist (2 ^ n-1). Eine vollständige Binärbaumdefinition ist jedoch ein Baum, in dem jeder Knoten entweder ein Blatt ist oder zwei untergeordnete Knoten hat. Also die maximal mögliche Nr. von Kindern ist (2 ^ n-1), aber es kann weniger als das sein.
Mrida
2

Um mit den Grundlagen zu beginnen, ist es sehr wichtig, den Binärbaum selbst zu verstehen, um verschiedene Arten davon zu verstehen.

Ein Baum ist genau dann ein Binärbaum, wenn: -

- Es hat einen Stammknoten, der möglicherweise keine untergeordneten Knoten hat (0 untergeordnete Knoten, NULL-Baum).

–Root-Knoten kann 1 oder 2 untergeordnete Knoten haben. Jeder dieser Knoten bildet selbst einen Abinary Tree 

–Die Anzahl der untergeordneten Knoten kann 0, 1, 2 sein ....... nicht mehr als 2

–Es gibt einen eindeutigen Pfad von der Wurzel zu jedem anderen Knoten

Beispiel:

        X
      /    \
     X      X
          /   \
         X     X

Kommen Sie zu Ihren angefragten Terminologien:

Ein Binärbaum ist genau dann ein vollständiger Binärbaum (mit der Höhe h nehmen wir den Wurzelknoten als 0), wenn: -

Die Stufen 0 bis h-1 repräsentieren einen vollständigen binären Baum der Höhe h-1

- Ein oder mehrere Knoten in Ebene h-1 können 0 oder 1 untergeordnete Knoten haben

Wenn j, k Knoten in der Ebene h-1 sind, dann hat j genau dann mehr untergeordnete Knoten als k, wenn j links von k liegt, dh der letzten Ebene (h) können Blattknoten fehlen, jedoch müssen die vorhandenen vorhanden sein nach links verschoben werden

Beispiel:

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

Ein Binärbaum ist genau dann ein rein binärer Baum, wenn: -

Jeder Knoten hat genau zwei untergeordnete Knoten oder keine Knoten

Beispiel:

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

Ein Binärbaum ist genau dann ein vollständiger Binärbaum, wenn: -

Jeder Nicht-Blattknoten hat genau zwei untergeordnete Knoten

Alle Blattknoten befinden sich auf derselben Ebene

Beispiel:

                          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 

Sie sollten auch wissen, was ein perfekter Binärbaum ist?

Ein Binärbaum ist genau dann ein perfekter Binärbaum, wenn: -

- ist ein vollständiger Binärbaum

- Alle Blattknoten befinden sich auf derselben Ebene

Beispiel:

                          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 

Nun, es tut mir leid, dass ich keine Bilder posten kann, da ich keinen Ruf habe. Hoffe das hilft dir und anderen!

user2376267
quelle
2

In meiner begrenzten Erfahrung mit Binärbaum denke ich:

  1. Streng binärer Baum : Jeder Knoten außer den Blattknoten hat zwei untergeordnete Knoten oder nur einen Wurzelknoten.
  2. Vollständiger Binärbaum : Ein Binärbaum von H, der streng (oder genau) 2 ^ H -1 Knoten enthält . Es ist klar, dass jede Ebene die meisten Knoten hat.
  3. Vollständiger Binärbaum : Dies ist ein Binärbaum, in dem jede Ebene, außer möglicherweise die letzte, vollständig gefüllt ist und alle Knoten so weit wie möglich links liegen.
BertKing
quelle
1
Ihre Definition für einen vollständigen Binärbaum ist falsch, dh die Definition eines perfekten Binärbaums. Ein vollständiger Binärbaum ist gleichbedeutend mit einem streng binären Baum. (Quelle: siehe streng binären Baum: Fakultät.cs.niu.edu / ~mcmahon / CS241 / Notes / bintree.html ) (Quelle: siehe perfekter binärer Baum: slidehare.net/ajaykumarc137151/… )
Keego
1
Oh mein Gott, ich bin gerade verwirrt, ich werde dafür sorgen. Danke vielmals.
BertKing
1
Kein Problem :) Siehe die Antwort von @Lotus unten , er hat es geschafft. Ich habe nur Änderungen für Ihre Antwort empfohlen, um dies widerzuspiegeln.
Keego
1

Betrachten wir einen binären Baum der Höhe 'h'. Ein Binärbaum wird als vollständiger Binärbaum bezeichnet, wenn alle Blätter in der Höhe 'h' oder 'h-1' vorhanden sind, ohne dass Zahlen in der Sequenz fehlen.

                   1
                 /   \
              2       3
            /    \         
         4        5

Es ist ein vollständiger Binärbaum.

                   1
                 /   \
              2       3
            /        /    
         4         6    

Es ist kein vollständiger Binärbaum, da der Knoten mit der Nummer 5 in der Sequenz fehlt

Ravi Varma Indukuri
quelle
0

Der vollständige Binärbaum ist voll, wenn jeder Knoten 0 oder 2 untergeordnete Elemente hat. in der vollen Binärzahl der Blattknoten ist die Anzahl der internen Knoten plus 1 L = l + 1

Harpreet Kaur Banga
quelle
0

Vollständiger Binärbaum: Alle Ebenen sind vollständig gefüllt, mit Ausnahme der untersten Ebene und einer Hauptsache, bei der alle Blattelemente ein Kind hinterlassen haben müssen. Strenger Binärbaum: In diesem Baum hat jeder Nicht-Blatt-Knoten kein Kind, dh weder links noch rechts. Vollständiger Binärbaum: Jeder Knoten hat entweder kein Kind oder zwei Kinder (niemals ein einziges Kind).

Rohit RK
quelle
> In diesem Baum hat jeder Nicht-Blatt-Knoten kein Kind, dh weder links noch rechts. Nicht-Blatt-Knoten muss mindestens ein Kind haben, sonst ist es Blattknoten
nkrivenko