Implementar uma estrutura de dados em árvore em Python

1. Implementar uma árvore do zero em Python
2. Percorrer uma árvore binária em Python
3. Implementar uma árvore usando uma biblioteca Python

Uma árvore é uma das estruturas de dados. Uma estrutura de dados nada mais é do que como organizamos os dados na memória. Uma árvore é uma combinação de nós (também conhecidos como vértices) e arestas. Uma árvore pode ter qualquer número de nós e arestas. Um nó é onde armazenamos os dados e uma aresta é um caminho entre 2 nós. Existem vários tipos de árvores disponíveis, como árvore binária, árvore ternária, árvore binária de busca, árvore AVL, etc.

Tipos de nós em uma árvore:

1. Nó pai: um nó que tem um ou mais filhos.
2. Nó filho: um nó que possui um nó pai.
3. Nó Folha: Um nó que não tem filhos.

Neste artigo, vamos primeiro ver como implementar uma árvore do zero sem usar nenhuma biblioteca e, mais tarde, você verá como implementar uma árvore com a ajuda de uma biblioteca Python.

Implementar uma árvore do zero em Python

Para criar uma árvore em Python, primeiro temos que começar criando uma classe Node que representará um único nó. Esta classe Node conterá 3 variáveis; a primeira é a left apontando para o filho esquerdo, a segunda variável data contendo o valor para aquele nó, e a variável right apontando para o filho direito.

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

Vamos inicializar uma árvore.

root = Node(10)

root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

A árvore se parece com a abaixo.

          10
        /    \
       34      89
     /    \ 
    45    50 

Sempre que você criar um objeto da classe Node, o construtor __init__ será chamado, e todas as variáveis ​​dentro desse construtor serão inicializadas. O root contém o nó raiz da árvore, que tem um valor de 10, e root.left e root.right usando o qual iremos inserir o filho esquerdo com o valor 34 e o direito filho para o nó raiz com o valor 89. Por ser uma árvore binária, cada nó conterá no máximo dois nós.

No final, inserimos mais dois nós na árvore, ou seja, 45 e 50, como filhos do nó 34. Você pode inserir qualquer número de nós que desejar dentro de uma árvore, dependendo do tipo de árvore que está criando.

Percorrer uma árvore binária em Python

Agora que criamos uma árvore, vamos atravessar a árvore para imprimir os elementos da árvore. A travessia visita todos os nós de uma árvore. Cada nó em uma árvore será visitado três vezes na travessia. A maneira pela qual atravessamos uma árvore é de cima para baixo e da esquerda para a direita.

Transversal de Pré-Ordem

Ao percorrer uma árvore, sempre que vemos o nó pela primeira vez, imprimimos esse nó e, em seguida, executamos a recursão no nó esquerdo e, em seguida, no nó direito.

def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

Resultado:

10 
34 
45 
50 
89

Traversal In-Order

Ao realizar o percurso em ordem, primeiro executamos a recursão no nó esquerdo e, em seguida, quando visitamos o mesmo nó pela segunda vez, imprimimos esse nó. Em seguida, executamos a recursão no nó certo.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

Resultado:

45 
34 
50 
10 
89

Traversal Pós-ordem

Para a travessia pós-pedido, realizamos a recursão no nó esquerdo e no nó direito e, em seguida, quando visitamos o mesmo nó pela terceira vez, imprimimos esse nó.

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)

Resultado:

45
50
34
89
10

Implementar uma árvore usando uma biblioteca Python

Como vimos, implementar uma árvore do zero leva algum tempo e requer muito código. Uma maneira mais fácil de implementar uma árvore em Python é usando uma biblioteca chamada anytree. A biblioteca anytree permite que você crie uma árvore sem escrever uma tonelada de código.

Para usar a biblioteca anytree, primeiro temos que instalá-la com a ajuda do comando abaixo.

pip install anytree

Aqui, também estamos criando a mesma árvore que criamos anteriormente. Agora podemos importar Node e RenderTree da biblioteca anytree.

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))

# Tree Structure
#          10
#        /    \
#       34      89
#     /    \
#    45    50

Resultado:

10
├── 34
│   └── 45
└── 89
    └── 50

Aqui, o Node criará um nó para nós que leva dois parâmetros; o primeiro é o valor do nó e o segundo é o nome do nó pai (este é um parâmetro opcional). Visto que em nossa árvore o nó root é o único nó que não possui nenhum pai, ao criar o nó root, passaremos apenas o primeiro parâmetro: o valor do nó e não o segundo parâmetro. O método RenderTree nos ajudará a imprimir a árvore inteira conforme mostrado na saída.