0 Daumen
900 Aufrufe

ich habe leider keine Ahung, was mit dieser Aufgabe gemeint ist bzw. was ich da tun muss. Kann mir wer weiterhelfen?

Sei T ein nicht leerer, voller Binärbaum. Ein Binärbaum T ist voll, wenn jeder Knoten von T
entweder ein Blatt (•(◦, ◦)) ist oder T = •(T1, T2) genau zwei Kinder T1, T2 6= ◦ hat.
  1. Stellen Sie eine rekursive Formel für die Anzahl der inneren Knoten von T auf, d.h. wieviele
  innere Knoten hat T = •(T1, T2), der genau aus den linken und rechten Teilbaum T1 bzw. T2
  besteht?
  2. Zeigen Sie mithilfe von Aufgabenteil 1 sowie der Strukturellen Induktion, dass die Anzahl der
  inneren Knoten von T genau n − 1 ist, wobei n die Anzahl der Blätter von T ist.

Danke im Voraus

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community