Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Beweis Anzahl Blätter vollständig binärer Bum der Höhe h
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Beweis Anzahl Blätter vollständig binärer Bum der Höhe h
 
Autor Nachricht
Ic3Cub38
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 05.08.2017
Beiträge: 1

BeitragVerfasst am: 05 Aug 2017 - 16:59:51    Titel: Beweis Anzahl Blätter vollständig binärer Bum der Höhe h

Hallo,

da ich neu in diesem Forum bin, bitte ich um Nachsicht, falls ich Fehler machen sollte :)

Aufgabe: Wie viele Blätter hat ein vollständiger binärer Baum der Höhe h? Beweis per vollständiger Induktion.

meine bisherige Idee:

Behauptung:
Baum der Höhe h hat 2^h Blätter

Induktionsanfang:
für h=0 --> 2^0=1 Blatt
stimmt.

Induktionsschritt:
T ist ein Baum der Höhe h
die Wurzel von T hat zwei Teilbäume als Söhne, die jeweils die Höhe h-1 haben
Diese Teilbäume haben eine Blätteranzahl von 2^(h-1)
Somit hat T 2*2^(h-1)=2^(h) Blätter.


Ich denke, dass die Grundidee hierbei richtig ist.
Allerdings glaube ich, dass dieser Beweis nicht vollständig ist. Z.B. weiß ich nicht, wie ich beweisen soll, dass die Teilbäume eine Blätternanzahl von 2^(h-1) haben.
Außerdem bin ich mir auch nicht sicher wie ich den Beweis formal korrekt aufschreiben soll...
Ich wäre sehr dankbar für eure Hilfe!

Vielen Dank im Voraus!
LG Ic3Cub38
taytm
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.08.2017
Beiträge: 1

BeitragVerfasst am: 08 Aug 2017 - 03:23:50    Titel:

Dass die Teilbäume mit Höhe h - 1 gerade 2^(h - 1) Blätter haben, ist deine Induktionsvoraussetzung. Ich finde, dass dein Beweis richtig aufgeschrieben ist, schließlich ist ein vollständiger Binärbaum gerade darüber definiert, dass jeder Knoten genau zwei Kinder hat.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Beweis Anzahl Blätter vollständig binärer Bum der Höhe h
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum