Arquivo de binary tree

Brincando de arvore binária com Python

Posted in Programação, Python with tags , , on 5 / julho / 2008 by medeubranco

De repente me deu vontade de fazer uma árvore binária em python. Não sei por que, nem para quê, mas deu vontade.

Usei um exemplo que creio ter visto no livro “C A linguagem de Programação” de Brian Kernighan e Dennis Ritchie : contagem de palavras em um texto.

O livro fala de árvores binárias como alternativa, neste problema de contagens de palavras, à pesquisa binária. Numa pesquisa binária, pressupomos que a lista de valores está previamente ordenada. Isso não deve ocorrer com as palavras de um texto qualquer. Não sabemos nem mesmo a quantidade de palavras que podem estar contidas nesse texto, de modo que pode não ser muito eficiente rodar previamente um algoritmo de ordenação. A salvação então é a tal árvore binária.

No meu código abaixo, criei uma classe (arvbin) para representar os nós da árvore. Os atributos da classe são: a palavra, o contador de ocorrências da palavra, um apontador para a palavra menor e outro para a maior:

class arvbin:
    def __init__(self, Valor):
        self.Menor=None  #apontador para a palavra menor
        self.Maior=None  #apontador para a palavra maior
        self.conta=1     #conttador de ocorrências
        self.valor=Valor #a palavra

Continue lendo