Informatik Ternärbäume?
Beweise die folgende Aussage durch Induktion ̈uber k: Jeder echte Ternärbaum (jeder Knoten hat 3 Kinder) mit k-inneren Knoten hat genau 2k + 1 Blätter.
kann mir wer in info herlfen? komm hier nicht weiter
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Informatik, Informatik
Überleg dir, wie viele Knoten du auf jeder Höhe hast und beweise das durch Induktion basierend auf der Knotenzahl der vorangegangenen Höhe.
Dann kannst du leicht zeigen, dass auf der letzten Ebene (Blätter) 2k + 1 Knoten liegen (indem du die Zahl der Knoten der vorletzten Ebene aus der Gesamtzahl der Knoten berechnest. Das kannst du auch induktiv beweisen womöglich).