2017-12-12 7 views
1

Ich sah eine Antwort hier mit der Idee in Python implementiert (nicht sehr vertraut mit Python) - Ich suchte nach einem allgemeineren Algorithmus.Wie finden wir in einer Liste von Schlüsseln den fast vollständigen binären Suchbaum dieser Liste?

EDIT:

Zur Klarstellung: Sagen wir eine Liste von ganzer Zahl Tasten angegeben sind: 44 88 12 23 74 32 7 39 10

wurde diese Liste ist willkürlich gewählt. Wir sollen einen fast vollständigen (oder vollständigen) binären Suchbaum aus dieser Liste erstellen. Es soll nur einen solchen Baum geben ... wie finden wir ihn?

+0

Es ist unklar, was Sie fragen. Bitte bearbeiten Sie Ihre Frage und fügen Sie weitere Details hinzu. Gib uns ein Beispiel. –

+0

@JimMischel Ich habe die Frage bearbeitet. Hoffnung ist jetzt klarer. –

Antwort

0

Ein binary search tree ist so konstruiert, dass alle Elemente im linken Teilbaum eines Knotens kleiner als der Knoten sind und alle Knoten im rechten Teilbaum größer als der Knoten sind.

Ein vollständiger (oder fast vollständiger) binärer Baum ist einer, in dem alle Ebenen außer möglicherweise der letzte vollständig voll sind, und die unterste Ebene ist auf der linken Seite gefüllt.

So zum Beispiel ist dies ein fast vollständiger binärer Suchbaum:

 4 
/ \ 
    2  5 
/\ 
1 3 

Dies ist nicht:

 3 
/ \ 
    2  4 
/  \ 
1   5 

Da die untere Ebene des Baums nicht von links gefüllt ist .

Wenn die Anzahl der Elemente eins weniger als eine Potenz von zwei ist (d. H. 3, 7, 15 usw.), dann ist das Erstellen des Baums einfach. Beginnen Sie mit dem Sortieren der Liste. Dann nimm das mittlere Element als Wurzel. Also, wenn Sie [1,2,3,4,5,6,7] haben, und der Wurzelknoten ist 4.

Sie tun das gleiche rekursiv für die rechte und linke Hälfte des Arrays.

Wenn die Anzahl der Elemente nicht um eins weniger als eine Potenz von zwei ist, müssen Sie den Startpunkt (den Wurzelknoten) so anpassen, dass die untere Zeile links gefüllt ist. Beachten Sie, dass Sie diese Anpassung möglicherweise auch rekursiv anwenden müssen, wenn Ihre Teilbaumlänge nicht weniger als eine Zweierpotenz ist.

Da dies eine Hausaufgabe ist, überlasse ich es Ihnen herauszufinden.

+0

Eigentlich studiere ich für Finale ... wurde leider nicht im Text erklärt. Aber danke für die Antwort. Gut erklärt. –

Verwandte Themen