Binärbäume

[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