Rekursive Formel für die Anzahl innerer Knoten eines Binärbaumes? Strukturelle Induktion

Question

Aufgabe:

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.

Answer 1

Antwort mit KI erzeugt

Rekursive Formel für die Anzahl der inneren Knoten eines Binärbaumes

Ein voller Binärbaum ist definiert als ein Baum, in dem jeder Knoten entweder kein Kind (und somit ein Blatt ist) oder genau zwei Kinder hat. Wir wollen eine Formel für die Anzahl der inneren Knoten in einem solchen Baum T finden. Die Anzahl der inneren Knoten in einem Baum T mit den Teilbäumen T1 und T2 kann rekursiv wie folgt ausgedrückt werden:

Sei \(n(T)\) die Anzahl der inneren Knoten in Baum T. Für einen vollständigen Binärbaum bedeutet dies:

1. Basisfall: Für einen Baum mit einem einzigen Knoten (welcher auch ein Blatt ist), \(T = •(◦, ◦)\), ist die Anzahl der inneren Knoten 0, da keine Kinder vorhanden sind: \(n(T) = 0\).

2. Rekursionsfall: Für einen Baum T, der aus den Teilbäumen T1 und T2 besteht, ist die Anzahl der inneren Knoten die Summe der inneren Knoten von T1 und T2, plus eins für den Wurzelknoten selbst:

\( n(T) = n(T1) + n(T2) + 1 \)

Diese Formel erlaubt es, die Anzahl der inneren Knoten eines beliebigen vollständigen Binärbaums rekursiv zu berechnen.

Strukturelle Induktion für die Anzahl der inneren Knoten relativ zu den Blättern

Zu zeigen ist, dass in einem vollständigen Binärbaum T die Anzahl der inneren Knoten genau \(n - 1\) beträgt, wobei \(n\) die Anzahl der Blätter in T ist.

Induktionsbasis: Für den einfachsten vollständigen Binärbaum, welcher nur ein Blatt enthält, gilt: \(n = 1\) und die Anzahl der inneren Knoten ist \(0\). Hier stimmt die Behauptung, da \(0 = n - 1\).

Induktionsannahme: Wir nehmen an, dass für alle vollständigen Binärbäume bis zu einer bestimmten Größe die Anzahl der inneren Knoten genau \(n - 1\) beträgt, wobei \(n\) die Anzahl der Blätter des Baumes ist.

Induktionsschritt: Betrachten wir nun einen Baum T, der durch Hinzufügen von zwei Teilbäumen T1 und T2, die jeweils die Eigenschaft erfüllen, gebildet wird. Sei \(n_1\) die Anzahl der Blätter in T1 und \(n_2\) die Anzahl der Blätter in T2. Nach Induktionsannahme hat T1 \(n_1 - 1\) innere Knoten und T2 hat \(n_2 - 1\) innere Knoten. Die Gesamtzahl der Blätter in T ist \(n = n_1 + n_2\), und die Gesamtzahl der inneren Knoten in T ist:

\( n(T) = n(T1) + n(T2) + 1 = (n_1 - 1) + (n_2 - 1) + 1 = n_1 + n_2 - 1 = n - 1 \)

Somit ist gezeigt, dass die Anzahl der inneren Knoten eines beliebigen vollständigen Binärbaums genau \(n - 1\) beträgt, wobei \(n\) die Anzahl der Blätter ist. Dies schließt den Beweis durch strukturelle Induktion.