Wie viele Knoten kann ein Binärbaum auf der Ebene n haben? Verwenden Sie Induktion, um die Antwort zu beweisen

Question

Dies ist eine Hausaufgabe und ich hatte nicht viel Zeit, aber ich kenne einige der Antwort und brauche ein wenig Hilfe PLZ

Ich denke, wie dies annehmen wir haben :

1 Knoten ----> Stufe 1

2,3 Knoten ----> Stufe 2

3,4,5,6,7 Knoten ----> Stufe 3

4,5,6, ....., 15 Knoten ----> Ebene 4

5,6,7,8,9, ....., 31-Knoten ----> Ebene 5

Knoten (s) Intervall von [min = X-Knoten (n) max = 2^X - 1 Knoten (s)], wobei X die Ebene

ab sofort vertreten auf i bin verwirrt, wie

Answer 1

Wie ich erinnere Induktion Sie verwenden haben den Nth Fall und den n + 1-ten Fall zu beweisen. Und wir sehen für jedes N, dass die N + 1-te Ebene genau doppelt so viele hat. Somit kann durch 2^gezeigte (N + 1)/2^N = 2

Die Gesamtzahl von Knoten kann, indem die Summe aus n = 0 bis N gefunden werden - 1 von 2^n

Wahrscheinlich will eine schlüssigere und ausführlichere Antwort, aber das ist das Wesentliche.

Answer 2

abzuschließen es klingt wie Sie es richtig haben. Die minimale Menge von Knoten ein Binärbaum haben kann, ist n und das Maximum 2^n-1

Answer 3

Ein Knoten auf der Ebene n in einem binären Baum hat n Vorfahren. Beweis durch Induktion: Zeige P (0): Ein Knoten auf Ebene 0 hat keine Vorfahren. (Dies ist richtig, weil es die Wurzel ist.) Zeigen Sie P (1): Ein Knoten auf Ebene 1 hat einen Vorfahren. (Das ist wahr; der Vorfahr ist die Wurzel, sein Vater, der auf Level 0 ist.) Angenommen, P (K): Ein Knoten auf Ebene K hat K Vorfahren. Sein Vater ist auf der Ebene K - 1. Beweisen Sie P (K + 1): Ein Knoten auf der Ebene K + 1 wird einen weiteren Vorgänger als den Knoten auf der Ebene K haben. Das K + 1. Element wird eine Elternebene haben (K +1) -1 oder Ebene K.