Informatiker Board | Druckvorschau: Binäre Bäume

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Binäre Bäume (http://www.informatikerboard.de/board/thread.php?threadid=2983)

Geschrieben von Stinzi am 27.04.2016 um 20:45:

Binäre Bäume

Hallo zusammen...... Mache gerade meine AlgoDat HÜ aber ich weiß nicht was mein Professor in der Aufgabe von mir will.... ich weis wie so ein Baum aussieht aber nicht wie ich die Aufgaben machen soll!

Könnt ihr mir Helfen?

Danke

Geschrieben von eulerscheZahl am 27.04.2016 um 20:53:

Zu a)
Die minimale Knotenzahl erreichst du, wenn jeder Knoten maximal einen Nachfolger hat, es also keine Verzweigungen gibt. Das gibt dann eine Liste.
Maximale Knotenzahl gibt es, wenn jeder innere Knoten zwei Nachfolger hat und die äußeren Knoten nur in der letzten Reihe vorkommen. Dann hast du $[latex]\sum\limits_{i=0}^h2^i[/latex]$ Knoten.
Wie du das formal ausdrückst, kann ich dir auch nicht sagen.

b,c und d sind nur a) anders formuliert.

Geschrieben von Stinzi am 27.04.2016 um 21:13:

ok....

formaler beweis werd ich mal mit induktion versuchen!!
Aber DANKE total nett!!

Geschrieben von Stinzi am 27.04.2016 um 21:39:

hab gerade versucht das nachzuvollzeihen....

checke aber deine Summenschreibweise gerade nicht Zunge raus

müsste i nicht bei 1 starten? verwirrt

Geschrieben von eulerscheZahl am 27.04.2016 um 21:41:

0 ist die Wurzel. Die allein hat Höhe 0 (sonst ergeben die Behauptungen keinen Sinn).