Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Bäume_Algorithmen_und_Datenstrukturen » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Bäume_Algorithmen_und_Datenstrukturen
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Flo
unregistriert
Bäume_Algorithmen_und_Datenstrukturen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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:
...
18.06.2017 12:11
as_string as_string ist männlich
Tripel-As


Dabei seit: 06.11.2013
Beiträge: 246
Herkunft: Heidelberg

RE: Bäume_Algorithmen_und_Datenstrukturen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
20.06.2017 11:09 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Bäume_Algorithmen_und_Datenstrukturen