Hallo Leute,

wunder mich gerade über die Aufgabe 7.1 in F3.

In dieser Aufgabe sollen wir ein Algorithmus mit dem rekursiven Verfahren erstellen, der die Höhe eines Binärbaumes bestimmt.

Aber im F3 Skript, sowie in den Folien ist nix über die Höhe zu finden, nur über die Tiefe eines Binärbaumes (= log_2 n).

Was ist denn überhaupt die Höhe eines Binäbaumes?
In P3 wird sie als log_2 N+1 <= Höhe <= N-1 vorgestellt!

Sind Tiefe und Höhe hier das gleiche????

LG
Frischling

Hoehe = Tiefe = Anzahl der Schichten = Längster Pfad von Wurzel zu einem Blatt
(+/- 1, je nach Definition, ist ja nicht so wichtig)

Und was bedeutet das, wenn ein Binäbaum nict ausgeglichen ist? Kann ich die Höhe oder Tiefe dann nicht mit log_2 n, n Anzahl der Blätter ermitteln?

Und wenn nicht, wie mach ich es dann?

Ein Binärbaum hat doch immer zwei Nachfolger!

Wurzel
/….\
a……b
/.\…../.\
c..d..e…f

IST DAS EIN AUSGEGLICHENER BBaum?

Wurzel
/….\
a……b
/.\
c..d

UND DAS KEINER?????

Die Punkte sind nur für den Abstand!

LG
Frischling

Abstand geht auch per Leerzeichen wenn
..
drumherumsteht

das mit ausgeglichen oder nicht hast du richtig erkannt,

das hier ist eventuell auch möglich:
Wurzel / a / \ c d
du sollst nicht aus n sofort die Höhe berechen,
sondern dir ein richtiges Verfahren ausdenken,

Tipp dafür: hmm in der Aufgabe steht doch schon rekursiv,
Knoten anschauen, linke und rechte Nachfolger anschauen,
wenn man da richtig zählt kann man doch die Höhe bestimmen,

hast du da genaue Fragen?

Ja hab ich noch.

In der Aufgabe steht auch:

"Beschreiben Sie ein rekursives Verfahren zur Bestimmung der Höhe eines Binärbaums. […] nehmen sie an, dass die Eingabe des beliebigen Binärbaumd B in Form einer doppelt verketteten Liste erfolgt.[…]"

// Slater: weg wars

Ich müsste ja beim rekursiven Verfahren immer eine Teilliste neu durch die Funktion jagen.

Wenn ich jetzt folgendes habe function tree(B) (B ist eine Liste!) und dann irgendwo in dem Programm h = tree(right)

(right steht für wähle rechten Nachfolger als neuen (Wurzel-)knoten und wurde uns in der Aufgabe zur Verfügung gestellt)

Würde sowas denn gehen? Hätten wir dann eine Teilliste?

Hmm!

LG
Frischling

im Grunde ok,
das Verfahren an sich wird bei dir schon zum Ziel führen
(weswegen ich es auch gleich rauseditiere ;) ),
ich denke so genau wird da nicht auf die exakte Programmierversion wert gelegt,

ansonsten wäre mein Tipp:
B ist KEINE Liste sondern ein Baum, also ein Knoten, ein Element der Liste..

RIGHT ist dann ein anderes Element, keine Teilliste,

das sind ja alles nur Pointer,
da werden keine Listen erzeugt oder zerschnippelt