árvores binárias de pesquisa são um dos tipos de dados abstratos básicos concebidos em programação de computadores. Através de uma árvore de busca binária , você pode definir uma estrutura básica por meio de entrada e de busca algoritmos que torna a localização e recuperação de informações fácil e sistemática. Uma vez que é um "abstrato" tipo de dados , você pode implementá-lo de alguma forma em mais qualquer linguagem de programação , incluindo Python. Criando uma classe para representar a árvore, você pode facilmente construir uma simples árvore de busca binária . Coisas que você precisa
interpretador Python
Mostrar Mais instruções
1
Crie uma classe para representar a árvore. Todo o código vai cair nessa classe e controlar a forma como as funções de árvores :
>>> class BinaryTree :
2
Definir os dados de árvores na classe. Nesta aula particular, você define a árvore como uma lista Python. A lista na árvore binária começa com um tamanho inicial de 50:
. . . _tree = [-1] * 50
3
Criar a função de inserção. Esta função usa matemática simples para determinar os pontos de inserção. Ele irá verificar cada ponto . Se o local contém um número negativo ( -1 ), então o local está vazio e pode ser inserido. Se não, ele se move para o próximo ponto . A inserção em uma árvore binária significa que os valores menores irá se mover para o nó " mão esquerda" ( 2i + 1 , onde " i" é o índice de lista atual ) e os maiores valores se moverá para o nó " da direita " ( 2i +2):
. . . def insere (self, valor): . . . index = 0 . . . enquanto self._tree [ índice ]> = 0: . . . se o valor > self._tree [ índice ] : . . . index = (index 2 *) + 1. . . mais: . . . index = (index 2 *) + 2. . . self._tree [ índice ] = valor
4
Criar uma função de pesquisa . A função de busca vai se comportar de forma semelhante à função de inserção , mas só irá verificar se o valor existe na árvore :
. . . def busca (self, valor): . . . index = 0 . . . enquanto self._tree [ índice ]> = 0: . . . se o valor self._tree [index] == : . . . retornar True . . . retornar Falso
