Python - árvore binária

A árvore representa os nós conectados por arestas. É uma estrutura de dados não linear. Possui as seguintes propriedades.

• Um nó é marcado como nó raiz.
• Cada nó, exceto a raiz, está associado a um nó pai.
• Cada nó pode ter um número arbitrário de nó chid.

Criamos uma estrutura de dados em árvore em python usando o conceito de nó discutido anteriormente. Designamos um nó como nó raiz e, em seguida, adicionamos mais nós como nós filhos. Abaixo está o programa para criar o nó raiz.

Criar raiz

Nós apenas criamos uma classe Node e adicionamos atribuindo um valor ao nó. Isso se torna uma árvore com apenas um nó raiz.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

Quando o código acima é executado, ele produz o seguinte resultado -

10

Inserindo em uma Árvore

Para inserir em uma árvore, usamos a mesma classe de nó criada acima e adicionamos um método de inserção a ela. O método de inserção compara o valor do nó ao nó pai e decide adicioná-lo como um nó esquerdo ou um nó direito. Finalmente, o método PrintTree é usado para imprimir a árvore.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

Quando o código acima é executado, ele produz o seguinte resultado -

3 6 12 14

Atravessando uma árvore

A árvore pode ser percorrida decidindo uma sequência para visitar cada nó. Como podemos ver claramente, podemos começar em um nó e visitar a subárvore esquerda primeiro e a subárvore direita em seguida. Ou também podemos visitar a subárvore direita primeiro e a subárvore esquerda a seguir. Conseqüentemente, existem nomes diferentes para esses métodos de travessia de árvore. Nós os estudamos em detalhes no capítulo que implementa os algoritmos de travessia de árvore aqui. Algoritmos de árvore transversal