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

(2 votes)
Loading...

Similar Posts

Subscribe
Notify of
1 Answer
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Destranix
2 years ago

Ü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).