Aula_Arvores_Binarias_e_BST_C

Prévia do material em texto

Árvores Binárias e Árvores de Busca em C
Teoria básica e exemplos práticos
O que é uma Árvore Binária?
Estrutura hierárquica de dados
Cada nó tem no máximo dois filhos: esquerdo e direito
Termos: raiz, nó, folha, subárvore, altura
Aplicações de Árvores Binárias
Representação de expressões matemáticas
Árvores de decisão
Compiladores e análise sintática
Estrutura de um Nó em C
typedef struct Node {
 int valor;
 struct Node* esquerda;
 struct Node* direita;
} Node;
Função de Inserção
Recursiva: compara valor com o nó atual
Insere à esquerda se menor, à direita se maior
Código: Inserção em BST
Node* novoNo(int valor) {
 Node* no = (Node*)malloc(sizeof(Node));
 no->valor = valor;
 no->esquerda = no->direita = NULL;
 return no;
}
Node* inserir(Node* raiz, int valor) {
 if (raiz == NULL) return novoNo(valor);
 if (valor valor)
 raiz->esquerda = inserir(raiz->esquerda, valor);
 else
 raiz->direita = inserir(raiz->direita, valor);
 return raiz;
}
Exemplo
int main() {
 Node* raiz = NULL;
 raiz = inserir(raiz, 50);
 inserir(raiz, 30);
 inserir(raiz, 70);
 inserir(raiz, 20);
 inserir(raiz, 40);
 inserir(raiz, 60);
 inserir(raiz, 80);
 printf("Em ordem: ");
 emOrdem(raiz);
 return 0;
}
Função de Busca
Busca recursiva comparando valores
Retorna o nó ou NULL se não encontrar
Código: Busca em BST
Node* buscar(Node* raiz, int valor) {
 if (raiz == NULL || raiz->valor == valor) return raiz;
 if (valor valor)
 return buscar(raiz->esquerda, valor);
 else
 return buscar(raiz->direita, valor);
}
Travessia Em Ordem (In-Order)
Percorre recursivamente: esquerda → raiz → direita
Usado para exibir os elementos em ordem crescente
Código: Travessia em Ordem
void emOrdem(Node* raiz) {
 if (raiz != NULL) {
 emOrdem(raiz->esquerda);
 printf("%d ", raiz->valor);
 emOrdem(raiz->direita);
 }
}
Remoção em BST – Casos
1. Nó sem filhos: remover diretamente
2. Nó com um filho: substituir pelo filho
3. Nó com dois filhos: substituir pelo menor da subárvore direita
Código: Remoção em BST
Node* remover(Node* raiz, int valor) {
 ... // verificação e casos
 if (raiz->esquerda == NULL) return raiz->direita;
 if (raiz->direita == NULL) return raiz->esquerda;
 Node* temp = encontrarMinimo(raiz->direita);
 raiz->valor = temp->valor;
 raiz->direita = remover(raiz->direita, temp->valor);
 return raiz;
}
Visualização Antes e Depois da Remoção
 Antes: Depois (remover 70):
 50 50
 / \ / \
 30 70 30 80
/ \ / \ / \ /
20 40 60 80 20 40 60
Exemplo no main()
Node* raiz = NULL;
raiz = inserir(raiz, 50);
inserir(raiz, 30); inserir(raiz, 70);
emOrdem(raiz); remover(raiz, 70); emOrdem(raiz);
Aplicações Práticas de BST
Índices de banco de dados
Compiladores
Árvores de decisão em jogos
Algoritmos de compressão (Huffman)
image1.png
image2.svg
 
.MsftOfcThm_Accent1_Fill_v2 {
 fill:#4F81BD; 
}
.MsftOfcThm_Accent1_Stroke_v2 {
 stroke:#4F81BD; 
}