---

Geschrieben von Flo am 18.06.2017 um 12:11:

  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:
...

---

Geschrieben von as_string am 20.06.2017 um 11:09:

  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