Cómo configurar un árbol de búsqueda binaria en Python

árboles binarios de búsqueda son uno de los tipos abstractos de datos básicos concebidos en la programación de computadoras . A través de un árbol de búsqueda binaria , se puede definir una estructura básica a través de la entrada y algoritmos de búsqueda que facilita la búsqueda y recuperación de información fácil y sistemática. Dado que es un tipo de datos " abstracto" , puede implementar de alguna forma en la mayoría de los lenguajes , incluyendo Python. Crear una clase para representar el árbol , usted puede construir fácilmente un sencillo árbol de búsqueda binaria. Cosas que necesitará
Python intérprete
Mostrar más instrucciones
1

Crear una clase para representar el árbol. Todo el código va a caer en esta clase y el control de cómo funciona el árbol :

>>> class BinaryTree :
2

definir los datos del árbol de la clase. En esta clase en particular , se define el árbol como una lista de Python . La lista en el árbol binario comienza con un tamaño inicial de 50 :

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

Crear la función de inserción . Esta función utiliza las matemáticas simples para determinar los puntos de inserción . Se comprobará cada lugar . Si el sitio contiene un número negativo ( -1 ), entonces el lugar está vacío y se inserta . Si no, se va al siguiente punto . La inserción en un árbol binario significa que los valores menores se mueven al nodo de " izquierda " ( 2i + 1 , donde " i" es el índice de la lista actual) y valores mayores a moverse al nodo " de la derecha " ( 2i +2 ) :

. . . def inserción (self, valor) : . . . index = 0 . . . mientras self._tree [ index] > = 0 : . . . si el valor > self._tree [ index] : . . . index = ( 2 * índice) + 1 . . . más: . . . index = ( 2 * índice) + 2 . . . self._tree [ index] = Valor
4

Crear una función de búsqueda . La función de búsqueda se comportará de manera similar a la función de inserción , pero sólo se comprobará si existe el valor en el árbol :

. . . Búsqueda def (self, valor) : . . . index = 0 . . . mientras self._tree [ index] > = 0 : . . . si self._tree [ indice] == valor : . . . devolverá True . . . devolverá False