Binärbaum Theorie Beweis |
Jo unregistriert
|
|
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
|
|
25.05.2010 18:18 |
|
|
MaBa
Eroberer
Dabei seit: 26.04.2010
Beiträge: 55
|
|
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
__________________ Dipl.-Inform. Markus Barth
Wissenschaftlicher Mitarbeiter
Studiengänge Angewandte Informatik / Medieninformatik
Fachhochschule Trier
Umwelt-Campus Birkenfeld
|
|
27.05.2010 11:01 |
|
|
Jo unregistriert
|
|
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
|
|
29.05.2010 18:09 |
|
|
cgs
Grünschnabel
Dabei seit: 30.05.2010
Beiträge: 2
|
|
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
|
|
30.05.2010 21:55 |
|
|
Abed
Mitglied
Dabei seit: 31.10.2015
Beiträge: 27
|
|
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
|
|
04.01.2016 23:41 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
05.01.2016 07:18 |
|
|
|