binær søgning træer er en af ​​de grundlæggende abstrakte datatyper undfanget i computer programmering. Gennem en binær søgning træ, kan du definere en grundlæggende struktur gennem input og søger algoritmer , der gør lokalisering og hente information nemt og systematisk . Da det er en " abstrakt " data type, kan du implementere det på en eller anden form i de fleste ethvert programmeringssprog , herunder Python. Oprettelse af en klasse til at repræsentere træet , kan du nemt bygge en simpel binær søgning træ. Ting du skal
Pythonfortolkeren
Vis Flere Instruktioner
1

Opret en klasse til at repræsentere træet. Alle koden vil falde i denne klasse, og styre, hvordan træet funktioner:

>>> class BinaryTree :
2

Definer de trædata i klassen. I denne særlige klasse definerer du træet som en Python listen. Listen i binært træ starter med en indledende størrelse på 50 : Hej

. . . _tree = [ -1] * 50
3

Opret insert -funktionen. Denne funktion bruger simpel matematik til at bestemme indsætningspunkter . Det vil kontrollere hver plet . Hvis stedet indeholder et negativt tal ( -1 ), så stedet er tom og vil indsætte. Hvis ikke , flytter det til det næste sted . Indsættelse i et binært træ betyder, at mindre værdier vil flytte til "venstre " node ( 2i + 1 , hvor "i " er den aktuelle liste index ), og større værdier vil flytte til " højre " node ( 2i +2) : Hej

. . . def insert (selv , værdi) : . . . indeks = 0 . . . mens self._tree [ indeks] > = 0: . . . hvis værdi> self._tree [ index ] : . . . indeks = ( 2 * index) + 1 . . . else: . . . indeks = ( 2 * index) + 2 . . . self._tree [ index ] = værdi
4

Opret en søgefunktion . Søgefunktionen vil opføre på samme måde som insert funktion, men vil kun kontrollere , hvis værdien findes i træet : Hej

. . . def søgning (selv , værdi) : . . . indeks = 0 . . . mens self._tree [ indeks] > = 0: . . . hvis self._tree [ indeks] == værdi : . . . returnere sandt . . . returnere False