Árvore binária
Última atualização
Uma árvore binária é uma hierarquia em que cada nó tem no máximo dois filhos, chamados de filho esquerdo e filho direito. O nó do topo é a raiz, os nós sem filhos são folhas, e o número de arestas da raiz até a folha mais profunda é a altura da árvore. Ao contrário de uma árvore binária de busca, uma árvore binária simples não tem regra de ordenação: é apenas o formato. Pressione play acima para ver uma árvore ser preenchida nível por nível e depois percorrida em ordem (esquerda, nó, direita).
As árvores binárias sustentam muitas estruturas: árvores binárias de busca, heaps, árvores de expressão e mais. Os percursos visitam cada nó em uma ordem definida: em ordem, em pré-ordem e em pós-ordem são os três percursos em profundidade, cada um útil para tarefas diferentes.
Terminologia
| Termo | Significado |
|---|---|
| Raiz | O nó do topo, sem pai |
| Folha | Um nó sem filhos |
| Altura | O caminho mais longo da raiz à folha (em arestas) |
| Profundidade | Distância de um nó em relação à raiz |
| Completa | Todos os níveis cheios exceto talvez o último, preenchido da esquerda para a direita |
Os três percursos em profundidade
| Percurso | Ordem | Uso comum |
|---|---|---|
| Em ordem | Esquerda, nó, direita | Saída ordenada de um BST |
| Pré-ordem | Nó, esquerda, direita | Copiar / serializar uma árvore |
| Pós-ordem | Esquerda, direita, nó | Excluir / avaliar uma árvore |
Exemplo resolvido
Percurso em ordem da árvore construída a partir de [4, 2, 6, 1, 3, 5] (preenchida nível por nível):
| Passo | No nó | Ação |
|---|---|---|
| 1 | 4 | Recorre à subárvore esquerda de 4 antes de visitá-lo |
| 2 | 2 | Recorre à subárvore esquerda de 2 antes de visitá-lo |
| 3 | 1 | Folha, sem filho esquerdo: visita 1, saída [1] |
| 4 | 2 | Esquerda concluída: visita 2, saída [1, 2], depois recorre à direita |
| 5 | 3 | Folha: visita 3, saída [1, 2, 3] |
| 6 | 4 | Subárvore esquerda concluída: visita 4, saída [1, 2, 3, 4], depois recorre à direita |
| 7 | 5 | Filho esquerdo de 6, uma folha: visita 5, saída [1, 2, 3, 4, 5] |
| 8 | 6 | Esquerda concluída, sem filho direito: visita 6, saída [1, 2, 3, 4, 5, 6] |
Quando usar uma árvore binária
| Use quando | Evite quando |
|---|---|
| Você precisa modelar dados intrinsecamente hierárquicos (sistemas de arquivos, árvores de expressão, DOM) | Os dados são planos e uma lista ou um array bastaria: uma árvore só adiciona sobrecarga |
| Você quer operações ordenadas e consegue mantê-la equilibrada (um BST ou uma árvore auto-balanceada) | Você precisa de busca por chave em O(1) médio: uma tabela hash supera qualquer árvore |
| Você precisa processar dados estruturados em ordem, pré-ordem ou pós-ordem | Os nós são inseridos em ordem crescente em um BST não equilibrado: degrada para uma lista O(n) |
| Consultas por intervalo ou iteração ordenada importam, o que tabelas hash não oferecem | A memória é escassa: cada nó carrega dois ponteiros para filhos além dos dados |
Código de Binary Tree
Uma implementação limpa e executável de Binary Tree em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Binary Tree em Python
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Código de Binary Tree em JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Código de Binary Tree em Java
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Código de Binary Tree em C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Código de Binary Tree em C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}Perguntas frequentes sobre árvores binárias
Qual é a diferença entre uma árvore binária e uma árvore binária de busca?
Uma árvore binária simplesmente limita cada nó a no máximo dois filhos, sem ordenação. Uma árvore binária de busca adiciona a regra de que tudo na subárvore esquerda é menor e tudo na subárvore direita é maior, o que é o que torna a busca rápida.
O que é um percurso em ordem?
O percurso em ordem visita a subárvore esquerda, depois o nó e depois a subárvore direita, de forma recursiva. Para uma árvore binária de busca isso produz os valores em ordem crescente, por isso é o percurso mais comum para demonstrar.
O que é uma árvore binária completa?
Uma árvore binária completa tem todos os níveis totalmente preenchidos exceto talvez o último, que é preenchido da esquerda para a direita. Esse formato permite armazenar a árvore de forma compacta em um array (sem necessidade de ponteiros para filhos), que é como os heaps binários são implementados.
Quando devo usar uma árvore binária em vez de um array ou uma tabela hash?
Recorra a uma árvore quando seus dados são naturalmente hierárquicos ou quando você precisa de operações ordenadas como consultas por intervalo e iteração ordenada, algo que tabelas hash não oferecem. Se você só precisa de busca rápida por chave sem ordenação, o acesso médio
O(1) de uma tabela hash supera uma árvore, e para dados planos um array é mais simples e melhor para a cache.Qual é a diferença entre a altura e a profundidade de uma árvore binária?
A profundidade é medida da raiz para baixo até um nó específico: o número de arestas no caminho da raiz até esse nó. A altura é medida de um nó para baixo até sua folha mais profunda, então a altura de toda a árvore é a profundidade de seu nó mais profundo. Uma árvore de um único nó tem altura
0, e seu único nó também tem profundidade 0.Por que uma árvore binária não equilibrada tem um desempenho tão ruim?
Buscar, inserir e excluir em uma árvore binária de busca custam
O(h), onde h é a altura. Quando as chaves são inseridas em ordem crescente a árvore vira uma linha reta, então h cresce até n e cada operação degrada para O(n), nada melhor que uma lista ligada. Árvores auto-balanceadas como AVL ou rubro-negra mantêm a altura em O(log n) para evitar isso.Recursos relacionados
Mais visualizações
