Beweis Konstruktionsregeln vollständiger Binärbaum - strukturelle Induktion |
| 06.02.2015, 08:39 | Mark22 | Auf diesen Beitrag antworten » |
| Beweis Konstruktionsregeln vollständiger Binärbaum - strukturelle Induktion Meine Aufgabe ist folgende: Beweisen Sie, dass jeder Baum, der gemäß den Konstruktionsregeln KI und KZ aus (folgender) Definition aufgebaut wird, ein vollständiger Binärbaum ist, d.h. für ihn gelten immer die Bedingungen 1, 2, 3 und 4 aus folgender Definition. Definition Konstruktionsregeln: (KI) Ein Baum nur einem Knoten ist ein vollständiger Baum. (K2) Ist T ein vollständiger Baum dann ist folgendes auch ein vollständiger Baum: (x ist der Wurzelknoten) x / \ T T Definition Bedingungen: 1. Jeder Knoten hat entweder keinen Oder genau einen Vorgänger. 2. Es gibt genau einen Knoten ohne Vorgänger, die Wurzel des Baumes. 3. Hat jeder Knoten in einem Baum höchstens zwei Nachfolger wird er Binärbaumbaum genannt. 4. Hat jeder Innere Knoten genau genau zwei Nachfolger und haben alle Blätter die gleiche Tiefe, wird der Baum ein vollständiger Binärbaum genannt. Meine Ideen: Behauptung: T' = 2*T+1 ist ein vollständiger Binärbaum Annahme: Ein Binärbaum mit nur einem Knoten ist ein vollständiger Binärbaum. Schritt: Und hier komm ich nicht mehr wirklich weiter. Ich habe bisher auch leider immer nur Beweise über die Höhe des Baums gefunden. Ich muss ja beweisen, dass für die Konstruktionsregel T' = 2*T+1 die Aussagen 1-4 gelten. Müssen die dann noch als aussagenlogischer Ausdruck dargestellt werden? Und wie sähe der Induktionsschritt dann erst mal aus? |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
Doppelpost!