Há mais de uma maneira de visitar todos os nós em um BST.
As árvores binárias são uma das estruturas de dados mais utilizadas na programação. Uma árvore de busca binária (BST) permite o armazenamento de dados na forma de nós (nó pai e nó filho nó) de modo que o nó filho esquerdo seja menor que o nó pai e o nó filho direito seja maior.
As árvores binárias de pesquisa permitem operações eficientes de passagem, pesquisa, exclusão e inserção. Neste artigo, você aprenderá sobre as três maneiras de percorrer uma árvore de pesquisa binária: travessia em pré-ordem, travessia em ordem e travessia em pós-ordem.
Travessia Inordem
A travessia em ordem é o processo de percorrer os nós de um árvore de pesquisa binária processando recursivamente a subárvore esquerda, depois processando o nó raiz e, finalmente, processando recursivamente a subárvore direita. Uma vez que processa os nós em ordem de valor ascendente, a técnica é chamada de travessia em ordem.
Atravessar é o processo de visitar cada nó em uma estrutura de dados de árvore exatamente uma vez.
Algoritmo de Inorder Traversal
Repita para percorrer todos os nós do BST:
- Atravesse recursivamente a subárvore esquerda.
- Visite o nó raiz.
- Atravesse recursivamente a subárvore direita.
Visualização de Inorder Traversal
Um exemplo visual pode ajudar a explicar a travessia da árvore de pesquisa binária. Esta figura mostra a travessia em ordem de um exemplo de árvore de pesquisa binária:
Nesta árvore de busca binária, 56 é o nó raiz. Primeiro, você precisa percorrer a subárvore esquerda 32, depois o nó raiz 56 e depois a subárvore direita 62.
Para a subárvore 32, primeiro percorra a subárvore esquerda, 28. Esta subárvore não tem nenhum filho, então percorra os 32 nós. Em seguida, percorra a subárvore direita, 44, que também não tem filhos. Portanto, a ordem de passagem para a subárvore com raiz em 32 é 28 -> 32 -> 44.
Em seguida, visite o nó raiz, 56.
Em seguida, percorra a subárvore direita, com raiz em 62. Comece percorrendo sua subárvore esquerda, com raiz em 58. Ele não tem filhos, então visite o nó 62 a seguir. Finalmente, percorra a subárvore direita, 88, que também não tem filhos.
Então o algoritmo visita os nós da árvore na seguinte ordem:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Aplicação de Inorder Traversal
Você pode usar a travessia em ordem para obter os valores dos elementos do nó em ordem crescente. Para obter os valores em ordem decrescente, basta inverter o processo: visite a subárvore direita, depois o nó raiz e depois a subárvore esquerda. Você pode usar o algoritmo para localizar a expressão de prefixo de uma árvore de expressão.
Traversal de pré-encomenda
O percurso de pré-ordem é semelhante ao inorder, mas processa o nó raiz antes de processar recursivamente a subárvore esquerda e depois a subárvore direita.
Algoritmo de travessia de pré-ordem
Repita para percorrer todos os nós do BST:
- Visite o nó raiz.
- Atravesse recursivamente a subárvore esquerda.
- Atravesse recursivamente a subárvore direita.
Visualização da travessia de pré-ordem
A figura a seguir mostra a travessia de pré-ordem da árvore de pesquisa binária:
Nesta árvore de pesquisa binária, comece processando o nó raiz, 56. Em seguida, percorra a subárvore esquerda, 32, seguida pela subárvore direita, 62.
Para a subárvore esquerda, processe o valor no nó raiz, 32. Em seguida, percorra a subárvore esquerda, 28, e finalmente a subárvore direita, 44. Isso completa a travessia da subárvore esquerda com raiz em 32. A travessia ocorre na seguinte ordem: 56 -> 32 -> 28 -> 44.
Para a subárvore direita, processe o valor no nó raiz, 62. Em seguida, percorra a subárvore esquerda, 58, e finalmente a subárvore direita, 88. Novamente, nenhum nó tem filhos, então a travessia está completa neste ponto.
Você percorreu a árvore completa na seguinte ordem:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Aplicação de Preorder Traversal
Você pode usar a travessia de pré-ordem para criar uma cópia da árvore com mais facilidade.
Traversal de pós-ordem
Traversal de pós-ordem é o processo de percorrer nós de uma árvore de busca binária recursivamente processar a subárvore esquerda, depois processar recursivamente a subárvore direita e, finalmente, processar a subárvore nó raiz. Como ele processa o nó raiz após ambas as subárvores, esse método é chamado de travessia em pós-ordem.
Algoritmo de travessia de pós-ordem
Repita para percorrer todos os nós do BST:
- Atravesse recursivamente a subárvore esquerda.
- Atravesse recursivamente a subárvore direita.
- Visite o nó raiz.
Visualização de travessia de pós-ordem
A figura a seguir mostra a travessia de pós-ordem da árvore de pesquisa binária:
Comece percorrendo a subárvore esquerda, 32, depois a subárvore direita, 62. Termine processando o nó raiz, 56.
Para processar a subárvore, com raiz em 32, percorra sua subárvore esquerda, 28. Como 28 não tem filhos, vá para a subárvore direita, 44. Processo 44, pois também não tem filhos. Por fim, processe o nó raiz, 32. Você percorreu esta subárvore na ordem 28 -> 44 -> 32.
Processe a subárvore correta usando a mesma abordagem para visitar os nós na ordem 58 -> 88 → 62.
Por fim, processe o nó raiz, 56. Você percorrerá a árvore completa nesta ordem:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Aplicação de Postorder Traversal
Você pode usar a travessia de pós-ordem para excluir uma árvore da folha para a raiz. Você também pode usá-lo para localizar a expressão pós-fixada de uma árvore de expressão.
Para visitar todos os nós folha de um determinado nó antes de visitar o próprio nó, você pode usar a técnica de travessia de pós-ordem.
Complexidade de tempo e espaço de travessias de árvore de pesquisa binária
A complexidade de tempo de todas as três técnicas de passagem é Sobre), onde n é o tamanho do árvore binária. A complexidade espacial de todas as técnicas de travessia é Oh), onde h é a altura da árvore binária.
O tamanho da árvore binária é igual ao número de nós dessa árvore. A altura da árvore binária é o número de arestas entre o nó raiz da árvore e seu nó folha mais distante.
Código Python para travessia de árvore de pesquisa binária
Abaixo está um programa Python para executar todas as três passagens da árvore de pesquisa binária:
# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element# Function to perform the inorder tree traversal
definorder(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
defpostorder(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
defpreorder(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 a seguinte saída:
Algoritmos essenciais para programadores
Algoritmos são uma parte essencial da jornada de todo programador. É crucial para um programador ser bem versado em algoritmos. Você deve estar familiarizado com alguns dos algoritmos, como classificação por mesclagem, classificação rápida, pesquisa binária, pesquisa linear, pesquisa em profundidade e assim por diante.