Tiefer Termbaum ausgeglichen < Datenstrukturen < Schule < Informatik < Vorhilfe
|
Status: |
(Frage) reagiert/warte auf Reaktion | Datum: | 13:13 Sa 21.02.2009 | Autor: | krueemel |
Aufgabe | 1. Wann ist ein (Term)Baum ausgeglichen?
2. Wann ist ein (Term)Baum vollständig ausgeglichen?
3. Ist ein "Blatt" auch ein Knoten? |
Guten Tag,
laut Definition gilt:
Baum ausgeglichen(ausgewogen)
Für jeden Knote gilt: die Tiefe der Teilbäume unterscheidet sich um höchstens 1.
Baum vollständig ausgeglichen (v. ausgewogen)
Für jeden Knoten gilt: Die Anzahl der Knoten in den Teilbäumen unterscheidet sich um höchstens 1.
Nun dazu meine Frage 3 (Ist ein "Blatt" auch ein Knoten"), zählt ein Blatt auch als Knoten?
Und ist mit Teilbäumen der rechte und linke Teilbaum gemeint, also hat ein Baum genau 2 Teilbäume? Oder ist das eher rekursivisch gemeint, jeweil immer wieder der Teilbaum?
Liebe Grüße
|
|
|
|
Hallo krueemel!
> 1. Wann ist ein (Term)Baum ausgeglichen?
> 2. Wann ist ein (Term)Baum vollständig ausgeglichen?
> 3. Ist ein "Blatt" auch ein Knoten?
> Guten Tag,
> laut Definition gilt:
> Baum ausgeglichen(ausgewogen)
> Für jeden Knote gilt: die Tiefe der Teilbäume
> unterscheidet sich um höchstens 1.
>
> Baum vollständig ausgeglichen (v. ausgewogen)
> Für jeden Knoten gilt: Die Anzahl der Knoten in den
> Teilbäumen unterscheidet sich um höchstens 1.
>
>
> Nun dazu meine Frage 3 (Ist ein "Blatt" auch ein Knoten"),
> zählt ein Blatt auch als Knoten?
Ich würde sagen, ja. Aber für die Aufgabe müsste es eigentlich egal sein, da Blätter keine Teilbäume haben und somit sich deren Tiefe auch um höchstens 1 unterscheidet und die Anzahl der Knoten in den nicht vorhandenen Teilbäumen ebenfalls.
> Und ist mit Teilbäumen der rechte und linke Teilbaum
> gemeint, also hat ein Baum genau 2 Teilbäume? Oder ist das
> eher rekursivisch gemeint, jeweil immer wieder der
> Teilbaum?
Das ist rekursiv gemeint, also jeder Knoten hat erstmal direkt zwei Teilbäume, jeder dieser Teilbäume hat aber ja eine Wurzel und diese Wurzel ist ein Knoten, der wieder genau zwei Teilbäume hat.
Hilft dir das weiter?
Viele Grüße
Bastiane
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 14:01 Sa 21.02.2009 | Autor: | krueemel |
so ganz so verstehe ich das nicht. Ich habe hier einen Baum, ist dieser ausgeglichen? vollständig ausgeglichen, oder weder noch?
Bild: http://www.clan-ffd.de/ffd/league/upload/upload/tb1.bmp
Liebe Grüße
|
|
|
|
|
Ist ausgeglichen. Deine Definition ist richtig, musst sie nur anwenden.
Gruß PHANTOMIAS
|
|
|
|