0 Daumen
892 Aufrufe

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.

von

1 Antwort

0 Daumen
  1. Macht man aus zwei Teilbäumen T1 und T2 einen Baum mittels eines neuen Knotens K, dann hat der Teilbaum folgende innere Knoten:

    • K
    • Die inneren Knoten von T1
    • Die inneren Knoten von T2

    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.

von 2,6 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community