Explorando Tree Traversal em JavaScript: Inorder, Preorder e Postorder com exemplos

Traversal de árvore é um conceito fundamental em ciência da computação que envolve visitar sistematicamente cada nó em uma estrutura de dados de árvore. Através da travessia da árvore, podemos processar os nós em uma ordem predeterminada, facilitando operações como busca, classificação e avaliação de expressões.

Neste artigo, exploraremos três dos métodos de travessia de árvore mais amplamente usados: inorder, preorder e postorder.

Por meio de exemplos claros e concisos implementados em JavaScript, você obterá uma compreensão sólida dessas técnicas de travessia.

Definição da estrutura da árvore

Antes de mergulhar nos algoritmos de travessia de árvore, vamos definir a estrutura que usaremos para a árvore binária. A árvore consistirá em nós, onde cada nó contém um valor e referências aos nós filhos esquerdo e direito.

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

Agora que definimos a estrutura da árvore, podemos continuar explorando os três métodos de travessia da árvore.

Travessia Inordem

A travessia em ordem segue o próximo padrão de nós visitantes em uma árvore binária - o algoritmo primeiro percorre a subárvore esquerda, depois visita o nó atual e, finalmente, percorre a subárvore direita. Isso garante que os nós sejam visitados em ordem crescente se a árvore representar uma estrutura de dados classificada.

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

Percurso recursivo em ordem

1. Verifique se o nó atual é nulo. Se sim, retorne.

   
   

2. Chame recursivamente a função na subárvore esquerda.

   
   

3. Visite o nó atual.

   
   

4. Chame recursivamente a função na subárvore direita.

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

Traversal de ordem não recursiva

1. Inicialize uma pilha vazia e defina o nó atual como a raiz da árvore.

   
   

2. Iterar enquanto a pilha não estiver vazia ou o nó atual não for nulo.

   • Empurre todos os nós esquerdos para a pilha até chegar a um filho esquerdo nulo.

   • Retire um nó da pilha, visite-o e defina o nó atual como seu filho direito.

     
     

3. Repita a etapa 2 até que a pilha esteja vazia e o nó atual seja nulo.

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

Traversal de pré-encomenda

No percurso de pré-ordem, o algoritmo primeiro visita o nó atual, depois percorre a subárvore esquerda e, finalmente, percorre a subárvore direita. Essa ordenação garante que os nós sejam visitados de maneira "top-down", começando pela raiz e seguindo em direção às folhas.

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

Traversal recursivo de pré-ordem

1. Verifique se o nó atual é nulo. Se sim, retorne.

   
   

2. Visite o nó atual.

   
   

3. Chame recursivamente a função na subárvore esquerda.

   
   

4. Chame recursivamente a função na subárvore direita.

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

Traversal de pré-ordem não recursivo

1. Comece com uma pilha vazia e coloque o nó raiz na pilha.

   
   

2. Inicialize uma matriz vazia para armazenar o resultado da travessia de pré-ordem.

   
   

3. Digite um loop while que é executado até que a pilha esteja vazia.

   
   

4. Retire um nó da pilha e visite-o adicionando seu valor à matriz de resultados.

   
   

5. Se o nó tiver um filho certo, coloque o filho certo na pilha.

   
   

6. Se o nó tiver um filho esquerdo, coloque o filho esquerdo na pilha.

   
   

7. Repita as etapas 3 a 6 até que a pilha esteja vazia.

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

Traversal de pós-ordem

Nesta travessia, o algoritmo primeiro percorre a subárvore esquerda, depois a subárvore direita e, finalmente, visita o nó atual. Essa ordenação garante que os nós sejam visitados de maneira “bottom-up”, começando pelas folhas e seguindo em direção à raiz.

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

Percurso recursivo de pós-ordem

1. Verifique se o nó atual é nulo. Se sim, retorne.

   
   

2. Chame recursivamente a função na subárvore esquerda.

   
   

3. Chame recursivamente a função na subárvore direita.

   
   

4. Visite o nó atual.

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

Traversal de pós-ordem não recursivo

1. Comece com uma pilha vazia e coloque o nó raiz na pilha.

   
   

2. Inicialize uma matriz vazia para armazenar o resultado da travessia de pós-ordem.

   
   

3. Digite um loop while que é executado até que a pilha esteja vazia.

   
   

4. Obtenha o nó superior da pilha (sem removê-lo).

   
   

5. Se o nó tiver um filho esquerdo, coloque o filho esquerdo na pilha e defina o filho esquerdo do nó atual como nulo.

   
   

6. Se o nó tiver um filho certo, coloque o filho certo na pilha e defina o filho certo do nó atual como nulo.

   
   

7. Se o nó não tiver filho esquerdo nem direito, é um nó folha. Retire o nó da pilha e adicione seu valor à matriz de resultados.

   
   

8. Repita as etapas 4 a 7 até que a pilha esteja vazia.

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

Conclusão

Espero que agora você tenha uma compreensão clara das diferenças entre inorder, preorder e postorder traversal em JavaScript. Com o conhecimento e os exemplos fornecidos, você agora está equipado para aplicar essas técnicas em suas próprias tarefas e projetos de maneira eficaz.