Como percorrer uma árvore de pesquisa binária

Uma árvore de pesquisa binária (BST) é uma estrutura de dados amplamente utilizada na programação, em que os dados são armazenados sob a forma de nós, sendo que cada nó serve como nó pai ou nó filho. Neste contexto, o nó filho esquerdo é caracterizado pelo facto de o seu valor ser inferior ao do nó pai, enquanto o nó filho direito possui um valor que excede o do nó pai.

A travessia de uma árvore de pesquisa binária é um aspeto essencial da sua funcionalidade, permitindo o desempenho eficiente de várias operações, como a pesquisa, a eliminação e a inserção de elementos de dados. Este artigo abordará os meandros de três métodos distintos para navegar numa árvore de pesquisa binária - travessia de pré-ordem, travessia de ordem e travessia de pós-ordem.

Inorder Traversal

O inorder traversal é um procedimento para navegar pelos nós de uma árvore de pesquisa binária explorando recursivamente a subárvore esquerda, visitando o nó raiz e depois examinando recursivamente a subárvore direita. Devido ao facto de inspecionar os nós numa sequência de valores crescentes, este método é designado por travessia por ordem.

O ato de percorrer uma estrutura de dados em árvore envolve a navegação em cada nó individual, assegurando que cada nó é acedido precisamente uma vez.

Algoritmo de travessia por ordem

Para navegar por cada nó de uma árvore de pesquisa binária (BST), pode seguir-se este processo:

⭐ Percorrer recursivamente a subárvore esquerda.

⭐ Visitar o nó raiz.

⭐ Percorrer recursivamente a subárvore direita.

Visualização da travessia por ordem crescente

Uma ilustração pode servir para demonstrar a travessia de uma árvore de pesquisa binária por ordem crescente, que é apresentada nesta representação gráfica. A travessia por ordem ascendente de uma árvore de pesquisa binária típica é aqui representada.

A árvore de pesquisa binária dada tem “56” como nó raiz. Para percorrer toda a árvore, é necessário navegar primeiro na subárvore esquerda, que contém o valor “32”, seguido do nó raiz, que é “56”. Finalmente, pode ser percorrida a subárvore direita, que inclui o valor “62”.

A subárvore enraizada no nó 32 começa com a leitura do seu descendente esquerdo, que não tem descendentes. Posteriormente, a atenção é dirigida para o próprio Nó 32 e, em seguida, para o descendente direito Nó 44, que também não tem descendentes. Consequentemente, a sequência de travessia para a subárvore enraizada no Nó 32 é 28 -> 32 -> 44.

Em seguida, visite o nó raiz, 56.

Efetuar uma travessia da direita para a esquerda da árvore com raiz em ‘Início’, começando com uma viagem para a esquerda através da subárvore com raiz em ‘Isto’. Como esta subárvore não tem descendentes, avance para o nó ‘62’ e continue da direita para a esquerda. Subsequentemente, efectue uma travessia semelhante na subárvore direita com raiz em ‘88’, que também não tem descendência.

O algoritmo continua a percorrer a estrutura hierárquica da seguinte maneira:

A sequência de números acima mencionada representa um padrão ascendente, começando em 28 e aumentando em 14 de cada vez para chegar a 88 no final.

Aplicação da travessia por ordem

Para obter os valores dos nós numa árvore de pesquisa binária por ordem ascendente ou descendente, pode utilizar-se uma abordagem de travessia por ordem. Especificamente, isto implica percorrer primeiro a subárvore da direita, seguida do nó raiz e, finalmente, da subárvore da esquerda. Esta metodologia também pode ser utilizada para determinar a expressão de prefixo de uma árvore de expressões.

Percurso de pré-ordem

O percurso de pré-ordem de uma árvore binária envolve visitar primeiro o nó raiz e depois percorrer recursivamente a subárvore esquerda seguida da subárvore direita.

Algoritmo de percursos de pré-ordem

Para navegar por cada nó de uma árvore de pesquisa binária (BST), pode seguir-se este processo:

⭐ Visitar o nó raiz.

⭐ Percorrer recursivamente a subárvore esquerda.

⭐ Percorrer recursivamente a subárvore direita.

Visualização da travessia de pré-ordem

Foi fornecida uma ilustração que descreve o processo de travessia de pré-ordem de uma árvore de pesquisa binária.

Na árvore de pesquisa binária, o nó raiz é inicialmente processado antes de percorrer a subárvore esquerda com um valor de 32 e depois a subárvore direita com um valor de 62.

56 -> 32 -> 28 -> 44.

O procedimento para processar os nós na subárvore direita começa por avaliar o valor do nó raiz. Depois disso, a atenção é direccionada para a subárvore esquerda e é feita uma travessia em profundidade, culminando num nó sem filhos. Neste momento, a travessia de ambas as subárvores está concluída, uma vez que não existem mais nós filhos para serem processados.

Terminei a minha análise do código fornecido e estou em condições de fornecer um resumo da sua funcionalidade. O programa começa por definir o diretório de trabalho atual como “C:\Users\Sasha\Desktop\iitk_project”.Em seguida, ele navega pelo sistema de arquivos, começando nesse local inicial, usando a função chdir() do módulo os . Isso permite que ele se mova de um nível de diretório para outro dentro da hierarquia do sistema de arquivos. À medida que se move através de cada diretório, utiliza o método scandir() para listar todos os ficheiros e directórios dentro dessa localização particular. Para cada item listado, o programa executa várias acções com base no tipo de ficheiro ou diretório. Se um item for considerado um diretório (indicado pelo seu final com uma barra), o seu caminho é adicionado a uma lista chamada

A sequência de números acima mencionada sofreu transformações sucessivas, resultando no valor final de 88.

Aplicação da travessia de pré-ordem

A travessia de pré-ordem pode ser utilizada para produzir uma réplica da árvore de forma eficiente.

Percurso pós-ordem

O percurso pós-ordem refere-se ao procedimento recursivo de percorrer os nós de uma árvore de pesquisa binária, em que a sub-árvore esquerda é processada primeiro, seguida da sub-árvore direita e, por último, do nó raiz. Esta técnica é designada por postorder traversal porque envolve a visita ao nó raiz depois de explorar as subárvores.

Algoritmo de travessia pós-ordem

Para navegar por cada nó de uma árvore de pesquisa binária (BST), pode seguir-se este processo:

⭐ Percorrer recursivamente a subárvore esquerda.

⭐ Percorrer recursivamente a subárvore da direita.

⭐ Visitar o nó raiz.

Visualização da travessia pós-ordem

Foi fornecida uma ilustração que descreve o processo de travessia de uma árvore de pesquisa binária em ordem sequencial, com o último nó sendo visitado primeiro.

Comece por explorar a sub-árvore da esquerda, que compreende um total de 32 elementos. Em seguida, percorra a subárvore direita, que consiste em mais 32 elementos. Finalmente, processe o nó raiz, que contém mais 16 elementos.

Percorrer a subárvore esquerda da árvore com raiz no nó 32, como não há nenhum filho para o nó 28, avançar para a subárvore direita e processar o nó 44. Finalmente, processar o nó raiz, completando assim a travessia da subárvore na sequência 28 -> 44 -> 32.

O processamento da subárvore direita implica percorrê-la em profundidade, começando no nó 58 e prosseguindo em direção aos seus filhos 88 e 62, por essa ordem.

Em última análise, é necessário efetuar o processamento do nó raiz percorrendo toda a árvore numa sequência específica.

A sequência de números acima parece ser uma série ascendente, em que cada termo é obtido adicionando quatro ao termo anterior.

Aplicação da travessia pós-ordem

Pode-se utilizar uma travessia pós-ordem para remover uma árvore das suas folhas até às suas raízes. Além disso, este método pode ser utilizado para determinar a expressão pós-fixa de uma árvore de expressões.

Para percorrer todas as folhas de um determinado nó antes de chegar ao próprio nó, pode utilizar-se a abordagem de percorrer após a ordem.

Complexidade temporal e espacial das travessias de árvores de pesquisa binárias

A ordem de complexidade para os três métodos de travessia é O(n), que depende do tamanho da árvore binária, denotado como n. Da mesma forma, a complexidade espacial para cada método também é O(h), onde h representa a altura da árvore binária.

A dimensão da árvore binária é co-terminada pelo número total de nós que a compõem. A altitude da árvore binária é definida como o agregado das distâncias das arestas entre o nó raiz e o nó folha mais distal, o que serve como uma medida da extensão vertical da árvore.

Código Python para travessia de árvore de pesquisa binária

Foi fornecido um exemplo de código Python com o objetivo de executar três travessias distintas de uma árvore de pesquisa binária, englobando por ordem:1. Travessia por ordem2. Percurso de pré-ordem3. Postorder Traversal

 # Node class is used to create individual nodes
# of the Binary Search Tree (BST)
class Node:
    def __init__(self, element):
        self.left = None
        self.right = None
        self.value = element

# Function to perform the inorder tree traversal
def inorder(root):
    if root:
        # Traverse left subtree
        inorder(root.left)

        # Traverse root
        print(str(root.value) \\+ ", ", end='')

        # Traverse right subtree
        inorder(root.right)

# Function to perform the postorder tree traversal
def postorder(root):
    if root:
        # Traverse left subtree
        postorder(root.left)

        # Traverse right subtree
        postorder(root.right)

        # Traverse root
        print(str(root.value) \\+ ", ", end='')

# Function to perform the preorder tree traversal
def preorder(root):
    if root:
        # Traverse root
        print(str(root.value) \\+ ", ", end='')

        # Traverse left subtree
        preorder(root.left)

        # Traverse right subtree
        preorder(root.right)

# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)
 

Este programa deve produzir o seguinte resultado:

Algoritmos obrigatórios para programadores

Os algoritmos desempenham um papel fundamental no desenvolvimento de um programador proficiente. Para se destacar neste domínio, é imperativo ter um conhecimento profundo dos algoritmos. A familiaridade com algoritmos de renome como o merge sort, o quick sort, a pesquisa binária, a pesquisa linear e a pesquisa em profundidade é indispensável para qualquer aspirante a programador.