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