---

Geschrieben von Jo am 25.05.2010 um 18:18:

  Binärbaum Theorie Beweis

Hey leute

ich bräuchte ein wenig Hilfe bei einer Binärbaumaufgabe.

Folgend:

Beweise, falls alle inneren Knoten eines binären Baumes zwei Nachfolger haben, so hat ein Binärer Baum mit n Blättern genau n-1 innere Knoten (inklusive Wurzel).

Ich weiß, dass diese Theorie stimmt (zumindest bin ich mir fast sicher^^) aber ich habe leider keine Ahnung wie man den Beweis antritt.

LG

Jo

---

Geschrieben von MaBa am 27.05.2010 um 11:01:

 

Hallo Jo,

da würde ich aber widersprechen. Ein Binärbaum der Höhe 4 hat eine 15 Knoten: 8 Blätter und 7 innere Knoten (inkl. Wurzel).

Zitat:

so hat ein Binärer Baum mit n Blättern genau n-1 innere Knoten (inklusive Wurzel).

n wäre hier also 4 und damit müsste es 4-1=3 innere Knoten geben.

Ich würde sagen es gibt 2^(n-1) - 1 innere Knoten, oder irre ich mich?

Mit freundlichen Grüßen,
MaBa

---

Geschrieben von Jo am 29.05.2010 um 18:09:

 

Hallo MaBa

du hast die antwort auf deine frage selbst gegeben,

Es heißt in meiner Aufgabe "ein Binärer Baum mit n Blättern genau n-1 innere Knoten (inklusive Wurzel)."

und du hast geschrieben :"Ein Binärbaum der Höhe 4 hat eine 15 Knoten: 8 Blätter und 7 innere Knoten (inkl. Wurzel)."

n ist 8 und 8 -1 ist 7

ich sehe keinen Widerspruch zu der Theorie.

Gruß Jo

---

Geschrieben von cgs am 30.05.2010 um 21:55:

  RE: Binärbaum Theorie Beweis

Hallo Jo,

das macht man mit Induktion. Da die Anzahl der Blätter nicht frei wählbar ist, verwendet man besser 2^i zum Rechnen. Zu zeigen ist dann:

Es gibt einen Fall, wo deine Vermutung gilt. Z. B. i=1.
Wenn es für 2^i gilt kann man zeigen, dass es auch für 2^(i+1) gilt.

Der Schluss von i auf i+1 funktioniert wie folgt: Ersetzt man bei einem Binärbaum mit 2^i Blättern alle Blätter durch einen Knoten mit zwei Blätter, dann hat der neue Binärbaum insgesamt 2^(i+1) Blätter und 2^i Knoten mehr als der ursprüngliche Baum.

LG cgs

---

Geschrieben von MaBa am 31.05.2010 um 10:17:

 

Hallo Jo,
sorry, ich hatte n als Höhe des Baumes verstanden, wodurch der Widerspruch durchaus berechtigt war ;-)

Viele Grüße,
MaBa

---

Geschrieben von Abed am 04.01.2016 um 23:41:

  noch ne Frage zum beweisen

wie kann ich beweisen ,
Ein vollständiger Binärbaum der Höhe n hat genau 2^n - 1 innere Knoten

.Ein Baum mit maximalem Verzweigungsgrad t besitzt auf Ebene k maximal tk Knoten.



danke

---

Geschrieben von eulerscheZahl am 05.01.2016 um 07:18:

 

Male dir einen Baum der Tiefe 2 oder 3. Zähle die Knoten insgesamt und in der untersten Reihe.
Bei Tiefe 3 sind es insgesamt 7, 4 davon sind Blätter.
Wenn die Teife um eins erhört wird, verdoppelt sich die Zahl der Blätter. Es gibt daher Blätter. Und . Die Gültigkeit der Summenformel könntest du mit Induktion beweisen.