Binärbaum
-
Hallo,
ich hoffe, das Thema ist im richtigen Forenbereich gelandet. Wenn nicht, entschuldige ich mich dafür und bitte jemanden mit entsprechenden Rechten, das in den richtigen Bereich zu verschieben.
Wie dem auch sei, hier mein Problem: Ich soll aus der folgenden Zahlenkette einen Binärbaum aufbauen (zeichnen), indem ich die Zahlen nacheinander in den Baum einfüge: 8, 17, 5, 10, 2, 9, 23, 20, 30, 6, 7, 3. Soweit so gut. Dann soll ich das in Pre-Order-Reihenfolge zu Papier bringen; meine Lösung ist: 8-5-2-3-6-7-17-10-9-23-20-30.
Im nächsten Schritt soll man die 5 und 17 aus dem gezeichneten Baum entfernen. Habe ich auch getan (die 6 hochgezogen, um 5 zu ersetzen und 10 hochgezogen, um die 17 zu ersetzen). Da im nächsten Aufgabenteil gefragt wurde, ob der Baum vollständig ausgeglichen ist, habe ich noch eine zweite Variante probiert, indem ich die 17 nicht duch 10, sondern durch 20 ersetzt habe. Die passende In-Order-Schreibweise, die dann gefragt ist, lautet ja dann: 2-3-6-7-8-9-10-20-23-30.
Dann sollte, wie erwähnt, festgestellt werden, ob der Baum vollständig ausgeglichen ist, oder nicht. Ich sage, dass er das ist, weil die Höhe jedes Blattes im linken und rechten Teilbaum um maximal "1" unterscheidet (wenn man da quasi Höhenlinien einzeichnet ^^).
Bis hierhin, glaube ich, habe ich die Aufgabe gut verstanden. Trotzde wäre ich über eine Bestätigung dankbar.
Hier kommt mein Problem: Im letzten Aufgabenteil soll man die Zahl "31" an den Baum hängen und das "entstehende Problem" angeben sowie eine Lösung des Problems angeben. Ich sehe nur kein wirkliches Problem. Wenn ich die "31" an die zuletzt entstandenen Bäume hänge, dann ist einer von beiden (der, bei dem ich beim Löschen der "17" die "10" hochgezogen habe) nicht mehr vollständig ausgeglichen, der, bei dem ich beim Löschen der "17" die "20" hochgezogen habe, aber sehr wohl noch. Stehe ich da gerade auf dem Schlauch oder ist das schon das, wonach gefragt wurde? Sieht da irgendwer noch eine andere Ungereimtheit? Über Anregungen bin ich sehr dankbar!
Vielen Dank und Grüße,
Zateha
-
Sry, dass ich dir keine antwort geben kann, aber nur mal so aus interesse:
Was ist ein Binär-Baum?
Davon hab ich noch nie etwas gehört.
Wäre nett wenn mir das jemand sagen könnte, denn vieleicht kenne ich
das ja unter nen anderen namen oder hab sonstige iddeen.
-
-
Zateha schrieb:
Hallo,
ich hoffe, das Thema ist im richtigen Forenbereich gelandet. Wenn nicht, entschuldige ich mich dafür und bitte jemanden mit entsprechenden Rechten, das in den richtigen Bereich zu verschieben.
Wie dem auch sei, hier mein Problem: Ich soll aus der folgenden Zahlenkette einen Binärbaum aufbauen (zeichnen), indem ich die Zahlen nacheinander in den Baum einfüge: 8, 17, 5, 10, 2, 9, 23, 20, 30, 6, 7, 3. Soweit so gut. Dann soll ich das in Pre-Order-Reihenfolge zu Papier bringen; meine Lösung ist: 8-5-2-3-6-7-17-10-9-23-20-30.
Im nächsten Schritt soll man die 5 und 17 aus dem gezeichneten Baum entfernen. Habe ich auch getan (die 6 hochgezogen, um 5 zu ersetzen und 10 hochgezogen, um die 17 zu ersetzen). Da im nächsten Aufgabenteil gefragt wurde, ob der Baum vollständig ausgeglichen ist, habe ich noch eine zweite Variante probiert, indem ich die 17 nicht duch 10, sondern durch 20 ersetzt habe. Die passende In-Order-Schreibweise, die dann gefragt ist, lautet ja dann: 2-3-6-7-8-9-10-20-23-30.
Dann sollte, wie erwähnt, festgestellt werden, ob der Baum vollständig ausgeglichen ist, oder nicht. Ich sage, dass er das ist, weil die Höhe jedes Blattes im linken und rechten Teilbaum um maximal "1" unterscheidet (wenn man da quasi Höhenlinien einzeichnet ^^).
Bis hierhin, glaube ich, habe ich die Aufgabe gut verstanden. Trotzde wäre ich über eine Bestätigung dankbar.
Ich habe das Beispiel nicht im Detail nachgerechnet, aber deine Beschreibungen und Begründungen klingen so, als hättest du das Thema verstanden und richtig gelöst.
Hier kommt mein Problem: Im letzten Aufgabenteil soll man die Zahl "31" an den Baum hängen und das "entstehende Problem" angeben sowie eine Lösung des Problems angeben. Ich sehe nur kein wirkliches Problem. Wenn ich die "31" an die zuletzt entstandenen Bäume hänge, dann ist einer von beiden (der, bei dem ich beim Löschen der "17" die "10" hochgezogen habe) nicht mehr vollständig ausgeglichen, der, bei dem ich beim Löschen der "17" die "20" hochgezogen habe, aber sehr wohl noch. Stehe ich da gerade auf dem Schlauch oder ist das schon das, wonach gefragt wurde? Sieht da irgendwer noch eine andere Ungereimtheit? Über Anregungen bin ich sehr dankbar!
Wenn es um vollständig ausgeglichene Bäume geht, dann ist das tatsächlich das Problem, ansonsten verstehe ich auch nicht, was die meinen.
-
Hallo,
nur, um das abzuschließen: der Baum war tatsächlich nicht mehr ausgeglichen und das war das besagte Problem. Durch eine Rotation hat sich das gut lösen lassen (Stichwort: AVL-Baum).Danke für die Antworten!
