Bäume_Algorithmen_und_Datenstrukturen |
18.06.2017, 12:11 | Auf diesen Beitrag antworten » |
Flo | Bäume_Algorithmen_und_Datenstrukturen Meine Frage: Hallo, ich komme bei einer Studienaufgabe absolut nicht weiter. Ich habe nicht einmal einen Ansatz, da man trinäre Bäume weder unter Google noch in ausgewählter Lektüre findet. Hier die Aufgabe: Die Höhe eines Baums ist definiert als die Anzahl der Knoten in einem längsten Pfad von Knoten zu einem Blatt. Damit hat ein Baum, der nur aus der Wurzel besteht, schon die Höhe 1. Beweisen Sie, dass ein vollständiger trinärer Baum (jeder Knoten, der kein Blatt ist, hat genau 3 Kinder) der Höhe h genau (3h 1048576 1)/2 Knoten enthält. Hinweis: Wissen über die Geometrische Reihe ist immer nützlich. Über Hinweise, Tipps etc. wäre ich sehr erfreut. lg Meine Ideen: ... |
|
|
20.06.2017, 11:09 | Auf diesen Beitrag antworten » |
as_string | RE: Bäume_Algorithmen_und_Datenstrukturen Hallo! Was ein "trinärer Baum" ist, ist in der Aufgabe ja beschrieben: Jeder Nicht-Blatt-Knoten hat 3 Kinder. Bei einem "binären Baum" (den solltest Du finden können) sind es ja genau 2 Kinder. Die Formel. die Du für die Höhe angegeben hast, kann ich leider nicht richtig erkennen. Kannst Du die nochmal deutlich schreiben? Gruß Marco |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|