Binärbaum Theorie Beweis |
| 25.05.2010, 18:18 | Auf diesen Beitrag antworten » | ||
| 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 |
||
|
|
|||
| 27.05.2010, 11:01 | Auf diesen Beitrag antworten » | ||
| 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).
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 |
||
| 29.05.2010, 18:09 | Auf diesen Beitrag antworten » | ||
| 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 |
||
| 30.05.2010, 21:55 | Auf diesen Beitrag antworten » | ||
| 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 |
||
| Anzeige | |||
|
|
|||
| 31.05.2010, 10:17 | Auf diesen Beitrag antworten » | ||
| MaBa | Hallo Jo, sorry, ich hatte n als Höhe des Baumes verstanden, wodurch der Widerspruch durchaus berechtigt war ;-) Viele Grüße, MaBa |
||
| 04.01.2016, 23:41 | Auf diesen Beitrag antworten » | ||
| 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 |
||
| 05.01.2016, 07:18 | Auf diesen Beitrag antworten » | ||
| 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 |
||
|
|
