Binärer Suchbaum < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen oder widerlegen Sie die folgenden Aussagen:
Der Inorder-Nachfolger eines Knotens mit zwei Nachfolgern in einem binären Suchbaum hat maximal einen Nachfolger. |
Hi Leute!
Ich hab hier ein Bild von einem Baum, den ich mir auf mein Blatt gemalt hab: http://s7.directupload.net/file/d/3245/shywzi2o_jpg.htm
Wenn ich mir jetzt den (Wurzel-)Knoten 6 anschaue, dann ist das der Knoten, mit zwei Nachfolgern; nämlich 3 und 8.
Frage: Welcher von den zwei Knoten (3 bzw. 8) ist nun der Inorder-Nachfolger?
Meiner Ansicht nach funktioniert ja die Inorder so: Man schaut zur Wurzel und dann (implementationsabhängig) entweder zum linken oder erst zum rechten Nachfolger und schreibt diesen Wert dann links oder rechts neben der Wurzel hin.
Warum aber soll nun der Inorder-Nachfolger eines Knotens mit zwei Nachfolgern eines maximal einen Nachfolger haben? Das kapier ich nicht...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:21 Mo 06.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
