 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 ![[latex]2^{n-1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?2^{n-1}) Blätter. Und ![[latex]\sum_{i=1}^n 2^{i-1} = \sum_{i=0}^{n-1} 2^i = 2^n-1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\sum_{i=1}^n 2^{i-1} = \sum_{i=0}^{n-1} 2^i = 2^n-1) . Die Gültigkeit der Summenformel könntest du mit Induktion beweisen.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
05.01.2016 07:18 |
|
|
|
