Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Wie viele Blattknoten besitzt ein gewurzelter Baum

Wie viele Blattknoten besitzt ein gewurzelter Baum

Universität / Fachhochschule

Binomialkoeffizienten

Differenzengleichungen

Erzeugende Funktionen

Graphentheorie

Inklusion-Exklusion

Kombinatorische Optimierung

Rekursives Zählen

Tags: Binomialkoeffizient, Differenzengleichung, Erzeugende Funktionen, Graphentheorie, Inklusion-Exklusion, Kombinatorische Optimierung, Rekursives Zählen

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
LarinV

LarinV

17:38 Uhr, 27.04.2022

Antworten
Aufgabe:

Hey ich habe eine Aufgabe bekommen, diese lautet:

T(0) und T(1) bestehen aus einem einzelnen Knoten 0 bzw. 1, der gleichzeitig die
Wurzel ist. F¨ur n ≥ 2 ist T(n) der Baum mit Wurzelknoten n, der zwei Kindknoten
besitzt, wobei die beiden Teilb¨aume, die am linken und rechten Kindknoten beginnen,
durch T(n − 1) bzw. T(n − 2) gegeben sind.

a) Wie viele Blattknoten besitzt T(n)?

( n ist naturliche Zahl und T(n) ist ein gewurzelten Baum(rekusiv))

(Wir wissen auch, dass ein Blattknoten ein Knoten ist, der keinen Kindknoten besitzt.)



b) Ein innerer Knoten ist ein Knoten, der kein Blatt ist. Wie viele innere Knoten besitzt T(n)?

c) Zeichnen Sie T(2),T(3) und T(4).



Problem/Ansatz:

Leider weiss ich gerade nicht wirklich ob ich auf den richtigen ergebnis gekommen bin. Ich habe mir einfach einen gewurzelten Baum gemalt und dann nachgezahlt um die reinfolge zu schauen und bin auf a)= bn=2ⁿ⁻1

zu b) habe ich leider noch nichts

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:
 
Online-Nachhilfe in Mathematik
Antwort
Nick76

Nick76 aktiv_icon

13:19 Uhr, 28.04.2022

Antworten
zu a):

Die Anzahl der Blattknoten von T(n) für n≥2, ergibt sich aus der Summe der
Blattknoten des linken und rechten Teilbaums.
Bezeichnet B(n) die Anzahl der Blattknoten von T(n) führt das auf die rekursive Formel

B(n)=B(n-1)+B(n-2)

Die Folge B(n) stimmt somit mit der Fibonacci-Folge 1,1,2,3,5... überein.

zu b):

Bezeichne I(n) die Anzahl der innerern Knoten von T(n) so erhält man folgende rekursive Formel:

I(n) =I(n-1)+I(n-2)+1 (der Wurzelknoten ist für n≥2 immer auch ein innerer Knoten)

Gruß

Nick
Frage beantwortet
LarinV

LarinV

21:38 Uhr, 05.05.2022

Antworten
danke