Die letzten 7 Beiträge |
eulerscheZahl |
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. |
Abed |
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 |
MaBa |
Hallo Jo,
sorry, ich hatte n als Höhe des Baumes verstanden, wodurch der Widerspruch durchaus berechtigt war ;-)
Viele Grüße,
MaBa |
cgs |
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 |
Jo |
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 |
MaBa |
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 |
Jo |
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 |
|
|