Binärbaum strukturelle Induktion

Question

Sei T ein nicht leerer, voller Binärbaum. Ein Binärbaum T ist voll, wenn jeder Knoten von T entweder ein Blatt (x(y,y)) ist oder T = x(T1,T2) genau zwei Kinder T1,T2 ungleich y hat.

1. Stellen Sie eine rekursive Formel für die Anzahl der inneren Knoten von T auf, d.h. wieviele innere Knoten hat T=x(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.

Answer 1

1. Macht man aus zwei Teilbäumen T₁ und T₂ einen Baum mittels eines neuen Knotens K, dann hat der Teilbaum folgende innere Knoten:

   • K
   • Die inneren Knoten von T₁
   • Die inneren Knoten von T₂

   Ein Teilbaum, der nur aus einem Blatt besteht, hat keine inneren Knoten.

2. IA: Ein Baum mit n = 1 Blättern hat n-1 = 0 innere Knoten.

   IV: Sei n eine natürliche Zahl und jeder Baum mit m < n Blättern hat m-1 innere Knoten.
   

   IS: Hat ein Baum n>1 Blätter, dann lässt er sich in zwei Teilbäume mit p bzw. q Blättern aufteilen. Dabei gilt p + q = n, p < n und q < n. Nach IV haben die Teilbäume p-1 bzw q-1 innere Knoten. Nach 1. hat der Baum dann p-1 + q-1 + 1 = n-1 innere Knoten.