Binärbäume

[Trouble_Maker]

Hallo zusammen,
und zwar suche ich allgemeine Informationen zu Binärbäumen! Haben dies im Informatikunterricht durchgenommen und schreiben nun eine Klausur darüber! Leider war ich länger Zeit krank, habe mir aber von anderen sagen lassen, dass wir stets nur allgemeines und nichts in Delphi oder am PC gemacht haben.
Es wäre wirklich sehr hilfreich für mich, wenn hier jemand interessante Links zum Thema posten könnte!
Die Suche und google habe ich schon benutzt, finde aber irgendwie nur Müll ^^

also schonmal danke im voraus
Trouble_Maker

[marabu]

Zitat:

Zitat von Trouble_Maker

Die Suche und google habe ich schon benutzt, finde aber irgendwie nur Müll

Mein Google ist besser als dein Google.

Gymnasium Odenthal

Sogar Wikipedia hat einen passenden Artikel.

[Alexander]

Ich würde es auch mal bei Wikipedia versuchen.
Aber ansonsten gibt es außer der Implementation nichts wirklich wichtiges. Ist halt eine Art Liste, bloß mit 2 nachfolgenen Kind-Knoten, einen linken und einen rechten.
Der Baum wird linksseitig zu erst ausgewerten, danach rechts. Sonst gibt es eigentlich nicht viel zu wissen :stupid:

Zur Implementation wirst du sicherlich was mit Google finden

[Binärbaum]

Zitat:

Zitat von Alexander

Der Baum wird linksseitig zu erst ausgewerten, danach rechts. Sonst gibt es eigentlich nicht viel zu wissen :stupid:

Das muss nicht unbedingt sein. Man kann auch erst den rechten und dann den linken Knoten auswerten. Aber das im Prinzip egal (wenn es nicht gerade ein Suchbaum oder AVL-Baum ist).

[Trouble_Maker]

Hi, vielen Dank erstmal für die Antworten!

Kann mir vielleicht jemand erklären, was der Unterschied zwischen einem vollem und einem vollständigem Baum ist?!?

Danke
Trouble_Maker


EDIT: Hmm... hab mal bei Wikipedia folgendes Zitat mir angeschaut:

Code:

Man bezeichnet ihn als voll, wenn jeder Knoten entweder Blatt ist (also kein Kind besitzt), oder aber zwei (also sowohl ein linkes wie ein rechtes) Kinder besitzt. Man bezeichnet ihn als vollständig, wenn alle Blätter die gleiche Tiefe besitzen.

Aber ein Baum, dessen Knoten immer 2 Kinder hat (also voll) und ein Baum, dessen Knoten die gleiche Tiefe besitzen ist doch das gleiche ?!?!?
ODER NICHT?



EDIT2: Hab da noch ne Frage ^^

Code:

Ein Binärbaum ist in der Graphentheorie ein gewurzelter Baum, genauer ein Out-Tree, bei dem jeder Knoten höchstens zwei Kinder besitzt.

Aber hat ein Knoten bei einem Binärbaum nicht genau 2 Kinder und nicht höchstens 2 ?!? Weil höchstens heißt doch 0,1 UND 2 !?
Und ein Binärbaum, kann doch nicht nur 1 Kind haben (also ein Knoten davon!)

Bin am verzweifeln ... :-|

[marabu]

Ein Baum der Ordnung n wird voll genannt, wenn er auf Ebene h eine Knotenzahl (n hoch h) besitzt.

Mit "vollständiger Baum" meinst du vielleicht "vollständig ausgeglicher Baum"? Vollständig ausgeglichene Bäume zeichnen sich dadurch aus, dass der Abstand der Ebenen ihrer Blätter höchstens 1 ist.

Wenn du mit diesen Definitionen Schwierigkeiten hast, dann hilft dir vielleicht die Betrachtung von Bildern. Dass Google nur Müll liefert kann ich nicht glauben.

Viel Erfolg bei der Klausur!

[marabu]

Zitat:

Zitat von Trouble_Maker

Aber ein Baum, dessen Knoten immer 2 Kinder hat (also voll) und ein Baum, dessen Knoten die gleiche Tiefe besitzen ist doch das gleiche ?!?!?
ODER NICHT?

Genau nicht - nimm einen Stammbaum. Links immer zwei Kinder, rechts plotzlich keine Nachkommen mehr. Ich hoffe du kannst dir das bildlich vorstellen - habe keine Lust hier "ascii art" zu produzieren.

[Alexander]

Zitat:

Zitat von Binärbaum

Zitat:

Zitat von Alexander

Der Baum wird linksseitig zu erst ausgewerten, danach rechts. Sonst gibt es eigentlich nicht viel zu wissen :stupid:

Das muss nicht unbedingt sein. Man kann auch erst den rechten und dann den linken Knoten auswerten. Aber das im Prinzip egal (wenn es nicht gerade ein Suchbaum oder AVL-Baum ist).

Da haben wir ja den Spezialisten :P
Sicherlich kann man es machen wie man will, aber eigentlich ist es standard den linksseitig zuerst auszuwerten. So kenne ich das zumindest...

[Trouble_Maker]

Zitat:

Zitat von marabu

Genau nicht - nimm einen Stammbaum. Links immer zwei Kinder, rechts plotzlich keine Nachkommen mehr. Ich hoffe du kannst dir das bildlich vorstellen - habe keine Lust hier "ascii art" zu produzieren.

meinst du sowas: ?

also vollständiger Baum ?!?

Delphi-Quellcode:

   
     
               1
          2         3
       4     5    6    7

voller Baum ?!?

Delphi-Quellcode:

  

               1
           2        3
        4     5

hm die 1er sind verschoben, ka wieso, sollen aber in der mitte sein zw. 2 und 3! (denke das ist klar!)


Weil hier beim vollen beim die 6 und 7 als kinder der 3 fehlen ?!?
Hoffe das ist so korrekt!

ciao
Trouble_Maker

[marabu]

OK - bleiben wir beim Binärbaum. Dein erstes Beispiel ist ein voller Baum, weil alle Blattknoten auf der letzten Ebene sind und kein Blattknoten auf dieser Ebene fehlt. Es ist Ebene 2 und du hast 2**2 = 4 Blattknoten.

Dein zweites Beispiel ist ein ausgeglichener Baum, weil sich alle Blattknoten entweder auf Ebene 1 oder 2 befinden. Vergleiche das mal mit den Definitionen die ich dir gegeben habe.