Tree Traversals (Inorder, Preorder e Postorder) com exemplos

O que é travessia de árvore?

Na estrutura de dados em árvore, travessia significa visitar os nós de alguma maneira específica. Existem nós2 tipos de travessias. Geralmente, esse tipo de travessia é baseado na árvore binária. Uma árvore binária significa que cada nó pode ter no máximo 2 nós.

Uma árvore binária é uma estrutura de dados bem conhecida. Há também uma árvore de pesquisa binária (BST). Este tipo de travessia é usado para diversos fins. A travessia de ordem de nível é usada para calcular a profundidade entre dois nós. Existe outro tipo de árvore chamada “AVL”, onde é necessário calcular a altura de um nó. Podemos representar uma árvore binária no array, mas para otimização de memória usaremos estrutura e ponteiro para referenciar o próximo nó.

Tipos de travessia de árvore

Como discutimos árvores binárias, agora discutimos os tipos individuais de travessias. Dependendo dos tipos, existem dois tipos de travessia. Anteriormente mencionamos a necessidade de ordem de nível ou travessia em largura. Agora Travessia em profundidade assim como a pós-ordem é usada para excluir um nó (discutiremos isso mais tarde), a pré-ordem é usada para copiar uma árvore binária e “inorder” percorrerá a árvore de maneira não decrescente.

Traversal em largura
Travessia em profundidade
Travessia de pré-encomenda
Travessia pós-ordem
Travessia em ordem

Traversal em largura

Também é conhecido como travessia de ordem de nível. Vamos considerar a árvore a seguir para demonstrar a travessia de ordem de nível.

Então, começaremos a partir do nó raiz “1”. Será marcado como nível 1. Então o algoritmo irá para todos os filhos do nó atual. Visitaremos os nós 2 e 3 agora. Eles serão marcados como nível 2.

Depois disso, como temos 2 nós no nível 2, visitaremos seus filhos também. Então, visitaremos 5,6,8,7 e marcaremos eles como nível 3. Aqui está algo que não é mencionado,

Nível do nó = nível do nó pai + 1

Nível 1: 1

Nível 2: 2 3

Nível 3: 5 6 8 7

Um algoritmo semelhante é usado para o BFS (Amplitude da primeira pesquisa).

Aqui está o pseudocódigo para passagem de ordem de nível:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Árvore Bianry Traversal Inorder

Vamos ter o mesmo exemplo de antes. Neste tipo de travessia, visitamos primeiro a subárvore esquerda, depois a raiz e, em seguida, a subárvore direita. Para facilitar a lembrança, podemos dizer que a ordem é esquerda-raiz-direita.

Para a árvore inteira, digamos que a raiz seja 1. Agora o algoritmo seguirá:

Visite a subárvore esquerda do nó 1.
O nó atual é 2 (pois é a subárvore esquerda de 1)

Visite a subárvore esquerda de 2. O nó atual será 5 desta vez.
Passando para 5, ele não tem filhos, então o nó 5 será marcado como visitado. Ele retornará ao nó pai; que é 2.
Como a subárvore esquerda de 2 é visitada, agora 2 também será visitada.
A algoritmo moverá o nó atual para a subárvore direita do nó 2, que é o nó 6. Depois de visitar o nó 6, ele se moverá para seu nó pai 2.
À medida que o nó 2 é visitado, agora visitaremos o pai de 2; que é o nó 1.
Depois disso, visitaremos a subárvore certa.

Portanto, a travessia final ficará assim:

Em ordem: 5 → 2 → 6 → 1 → 8 → 3 → 7

Aqui está o pseudocódigo para travessia em ordem:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Este é o algoritmo recursivo para a travessia em ordem. Para o Árvore de pesquisa binária (BST), A travessia em ordem fornece a matriz classificada de valores.

Travessia pós-pedido

Neste percurso, percorreremos primeiro a subárvore mais à esquerda e, em seguida, a subárvore mais à direita após a raiz. Todas as travessias serão em Pós-Ordem. Vamos demonstrar um exemplo:

Aqui para raiz = 1,

Iremos primeiro para a subárvore esquerda. Então a raiz se tornará 2.
Então 2 saiu da subárvore, então iremos para o nó 5. Agora a raiz é 5.
Não possui subárvore esquerda e também não possui subárvore direita. Então, agora marcaremos o nó 5 como visitado e iremos para o seu nó pai.

Agora a raiz é 2 e sua subárvore esquerda foi completamente visitada. Agora passaremos para sua subárvore direita. Então a raiz se torna 6.
Como o nó 6 não tem subárvore esquerda e direita, marcaremos o nó 6 como visitado e passaremos para seu nó pai 2.
Agora, as subárvores esquerda e direita estão sendo visitadas para o nó 2. Ele também será marcado como visitado.
Passaremos para o pai do nó 2, que é o nó 1.
A subárvore esquerda é visitada pela raiz 1. Agora, da mesma forma, visitaremos a subárvore direita.

O círculo marcado é a subárvore direita. Agora visitaremos a subárvore direita assim como visitamos a subárvore esquerda. Depois disso, visitaremos o nó. Portanto, a travessia final será:

Pós-ordem: 5 → 6 → 2 → 8 → 7 → 3 → 1

Aqui está o pseudocódigo para travessia pós-pedido:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Pré-encomenda Traversal

Para a travessia da pré-ordem, o algoritmo visitará primeiro o nó raiz, depois disso, passará para a subárvore esquerda e direita, respectivamente. Para facilitar a compreensão, podemos pensar em visitas de passagem de pré-encomenda como raiz → esquerda-direita.

Então, vamos selecionar o nó 1 como raiz.

De acordo com o algoritmo, a raiz será descoberta primeiro, depois a subárvore esquerda e depois a subárvore direita.
Então, visitaremos a raiz 1. Em seguida, passaremos para sua subárvore esquerda. A raiz se torna 2.
Visitaremos o nó 2 e passaremos para sua subárvore esquerda. Então, a raiz se torna 3.
Visitamos o nó 3 e depois passamos para seu nó pai. Agora o nó 2 e sua subárvore esquerda são visitados. É hora de visitar a subárvore certa.
Passaremos para a subárvore direita, a raiz se tornará 4. Visitaremos 4. Como 4 não tem nó filho, passaremos para seu nó pai.
Agora a raiz é 2 e é visitada junto com suas subárvores esquerda e direita. Então, passaremos para seu nó pai. Agora a raiz se torna 1.
Da mesma forma, visitaremos a subárvore certa.

Pré-encomenda: 1 → 2 → 3 → 4 → 5 → 6 → 7

Aqui está o pseudocódigo para travessia pós-pedido:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Implementação em Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) & gt;
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Saída:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Implementação em C

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}