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.

[dizzy]

Zitat:

Zitat von Alexander

aber eigentlich ist es standard den linksseitig zuerst auszuwerten. So kenne ich das zumindest...

Da gibt es keinen Standard. Die Art und Weise wie der Baum traversiert wird hängt einzig und allein von der Problemstellung ab.
Die 3 häufigsten Verfahren: Pre-Order, Post-Order, In-Order.

Ein Baum ist definitionsgemäß auch DANN noch binär, wenn nicht jeder Knoten genau 2 Kinder hat. 0 Kinder MÜSSEN schon mal möglich sein, sonst wäre er unendlich ;). Und die Ordnung des Baumes bestimmt sich nach der höchsten vorkommenden Kindanzahl. Alles darunter ist genau so zulässig.

[Trouble_Maker]

Zitat:

Zitat von dizzy

Ein Baum ist definitionsgemäß auch DANN noch binär, wenn nicht jeder Knoten genau 2 Kinder hat. 0 Kinder MÜSSEN schon mal möglich sein, sonst wäre er unendlich ;). Und die Ordnung des Baumes bestimmt sich nach der höchsten vorkommenden Kindanzahl. Alles darunter ist genau so zulässig.

Hä aber wenn ein Baum bzw, ein Knoten nur 1 Kind hat, dann ist er doch nicht mehr binär oder doch?!?

Hoffe mir kann noch ganz schnell jemand helfen! Schreibe nachher die Klausur!

UNd noch eine Frage: Ist Root also die Wurzel auch ein Knoten oder nicht?! Eigentlich ja oder? Aber dann kann man doch nicht sagen, dass jeder Knoten einen Vater hat oder!??

DANKE in der hoffnung, dass noch jemand was in den nächsten 20 mins schreibt :-D


ciao
Trouble_Maker

[Binärbaum]

Zitat:

Zitat von Trouble_Maker

Hä aber wenn ein Baum bzw, ein Knoten nur 1 Kind hat, dann ist er doch nicht mehr binär oder doch?!?

Ein Baum ist binär, wenn jeder Knoten maximal zwei Nachfolger hat.

Zitat:

Zitat von Trouble_Maker

UNd noch eine Frage: Ist Root also die Wurzel auch ein Knoten oder nicht?! Eigentlich ja oder? Aber dann kann man doch nicht sagen, dass jeder Knoten einen Vater hat oder!??

Die Wurzel ist im Prinzip auch "nur" ein Knoten, aber dieser Knoten ist nicht Nachfolger eines andern Knotens. irgendwo muss ein Binärbaum ja mal anfangen. :wink:

[Trouble_Maker]

Zitat:

Zitat von Binärbaum

Ein Baum ist binär, wenn jeder Knoten maximal zwei Nachfolger hat.

Achsoooo... wieso sagt mir das denn nicht gleich einer ;-) Jetzt raff ichs :-)

Also ist die Aussage "Ein Binärbaum hat immer den Grad 2" Falsch und "Ein Binärbaum hat höchstens den Grad 2" Richtig ?!?!?

Zitat:

Zitat von Binärbaum

Die Wurzel ist im Prinzip auch "nur" ein Knoten, aber dieser Knoten ist nicht Nachfolger eines andern Knotens. irgendwo muss ein Binärbaum ja mal anfangen. :wink:

Ja genau: daher ist die Aussage "Jeder Knoten hat in einem Binärbaum einen Vater" Falsch ?!?!


bitte schreibt noch schnell was ^^

DANKE AUF JEDEN FALL @ Binärbaum! Hast deinen namen verdient


cu

[dizzy]

Auch wenn es jetzt zu spät sein dürfte...:

Zitat:

Zitat von Trouble_Maker

Also ist die Aussage "Ein Binärbaum hat immer den Grad 2" Falsch und "Ein Binärbaum hat höchstens den Grad 2" Richtig ?!?!?

Nicht ganz. Ein Binärbaum heisst genau so, eben wegen seiner Eigenschaft vom Grade 2 zu sein. Hätte kein Knoten mehr als einen Nachfolger, so wäre es eine Liste, bei 3 Kindern ein ternärer Baum bis hin zu n-ären Bäumen vom Grad n.
=> Ein Binärbaum muss mindestens einen Knoten besitzen der 2 Kinder hat, um binär genannt werden zu können. Etwas verwirrend dabei ist, dass man ja durchaus eine Knotenklasse für binäre Bäume haben kann, aber auf Grund der Umstände nur eine Liste zu Stande kommt. Somit hat man dann einen zur Liste degenerierten Binärbaum.
Natürlich, und das steht einem frei, kann man einen strikten Binärbaum fordern, bei dem durch die Programmlogik gewährleistet wird, dass jeder Knoten genau 2 oder 0 Kinder hat. Das kann je nach Problemstellung evtl. auch mal sinnvoll sein, aber so strikt ist die eigentliche Definition nicht.

Zitat:

Zitat von Trouble_Maker

Ja genau: daher ist die Aussage "Jeder Knoten hat in einem Binärbaum einen Vater" Falsch ?!?!

Wurzeln stellen in jeder Baumart einen Sonderfall dar. Programmtechnisch sehen sie zwar gleich aus, aber wie du schon sagtest gibt es diesen kleinen Unterschied in der sprachlichen Definition ;).
Es macht zudem Sinn die Wurzel aus einer ganz normalen Knotenklasse zu generieren, da es z.B. bei AVL-Bäumen durch Rotationen vorkommt, dass eine Wurzel auf einmal ein Knoten wird un umgekehrt. Noch lustiger wird's ja bei B-Bäumen :) (ekelhafte Dinger die...).

Gruss,
Fabian

[Trouble_Maker]

Hi,
okay... vielen Dank an alle die hier gepostet haben! Letzendlich war die ganze Aufregung umsonst, weil wir doch nicht geschrieben haben :-D
-
Naja zumindest bin ich jetzt schlauer - und das ist ja die hauptsache :-)

danke ciao
Trouble_Maker