Árvores

Exemplo completo

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Definição da estrutura do nó da árvore binária
typedef struct No {
    int dado;
    struct No *esquerda;
    struct No *direita;
} No;

// Função para criar um novo nó
No *criarNo(int valor) {
    No *novoNo = (No*)malloc(sizeof(No));
    if (novoNo == NULL) {
        printf("Erro: Falha na alocação de memória!\n");
        exit(1);
    }
    novoNo->dado = valor;
    novoNo->esquerda = NULL;
    novoNo->direita = NULL;
    return novoNo;
}

// INSERÇÃO em Árvore Binária de Busca (BST)
No *inserir(No *raiz, int valor) {
    // Caso base: árvore vazia ou posição encontrada
    if (raiz == NULL) {
        return criarNo(valor);
    }
    
    // Inserir na subárvore esquerda se valor é menor
    if (valor < raiz->dado) {
        raiz->esquerda = inserir(raiz->esquerda, valor);
    }
    // Inserir na subárvore direita se valor é maior
    else if (valor > raiz->dado) {
        raiz->direita = inserir(raiz->direita, valor);
    }
    // Se valor já existe, não inserir duplicata
    
    return raiz;
}

// BUSCA em Árvore Binária de Busca
bool buscar(No *raiz, int valor) {
    // Caso base: árvore vazia ou valor não encontrado
    if (raiz == NULL) {
        return false;
    }
    
    // Valor encontrado
    if (raiz->dado == valor) {
        return true;
    }
    
    // Buscar na subárvore esquerda
    if (valor < raiz->dado) {
        return buscar(raiz->esquerda, valor);
    }
    // Buscar na subárvore direita
    else {
        return buscar(raiz->direita, valor);
    }
}

// PERCURSO EM ORDEM (In-Order) - Esquerda, Raiz, Direita
// Em uma BST, produz valores em ordem crescente
void percursoEmOrdem(No *raiz) {
    if (raiz != NULL) {
        percursoEmOrdem(raiz->esquerda);    // Visita subárvore esquerda
        printf("%d ", raiz->dado);           // Visita raiz
        percursoEmOrdem(raiz->direita);      // Visita subárvore direita
    }
}

// PERCURSO PRÉ-ORDEM (Pre-Order) - Raiz, Esquerda, Direita
// Útil para copiar árvores e expressões prefixas
void percursoPreOrdem(No *raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->dado);           // Visita raiz
        percursoPreOrdem(raiz->esquerda);    // Visita subárvore esquerda
        percursoPreOrdem(raiz->direita);     // Visita subárvore direita
    }
}

// PERCURSO PÓS-ORDEM (Post-Order) - Esquerda, Direita, Raiz
// Útil para liberar memória e expressões sufixas
void percursoPosOrdem(No *raiz) {
    if (raiz != NULL) {
        percursoPosOrdem(raiz->esquerda);    // Visita subárvore esquerda
        percursoPosOrdem(raiz->direita);     // Visita subárvore direita
        printf("%d ", raiz->dado);           // Visita raiz
    }
}

// Função para encontrar o menor valor (nó mais à esquerda)
No *encontrarMinimo(No *raiz) {
    while (raiz->esquerda != NULL) {
        raiz = raiz->esquerda;
    }
    return raiz;
}

// REMOÇÃO de nó na BST
No *remover(No *raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }
    
    // Valor está na subárvore esquerda
    if (valor < raiz->dado) {
        raiz->esquerda = remover(raiz->esquerda, valor);
    }
    // Valor está na subárvore direita
    else if (valor > raiz->dado) {
        raiz->direita = remover(raiz->direita, valor);
    }
    // Valor encontrado - este é o nó a ser removido
    else {
        // Caso 1: Nó sem filhos (folha)
        if (raiz->esquerda == NULL && raiz->direita == NULL) {
            free(raiz);
            return NULL;
        }
        // Caso 2: Nó com apenas um filho
        else if (raiz->esquerda == NULL) {
            No *temp = raiz->direita;
            free(raiz);
            return temp;
        }
        else if (raiz->direita == NULL) {
            No *temp = raiz->esquerda;
            free(raiz);
            return temp;
        }
        // Caso 3: Nó com dois filhos
        else {
            // Encontrar o sucessor (menor valor na subárvore direita)
            No *sucessor = encontrarMinimo(raiz->direita);
            
            // Copiar o valor do sucessor para este nó
            raiz->dado = sucessor->dado;
            
            // Remover o sucessor
            raiz->direita = remover(raiz->direita, sucessor->dado);
        }
    }
    return raiz;
}

// Função para calcular a altura da árvore
int altura(No *raiz) {
    if (raiz == NULL) {
        return -1; // Altura de árvore vazia é -1
    }
    
    int alturaEsquerda = altura(raiz->esquerda);
    int alturaDireita = altura(raiz->direita);
    
    return 1 + (alturaEsquerda > alturaDireita ? alturaEsquerda : alturaDireita);
}

// Função para contar total de nós
int contarNos(No *raiz) {
    if (raiz == NULL) {
        return 0;
    }
    return 1 + contarNos(raiz->esquerda) + contarNos(raiz->direita);
}

// Função para liberar toda a memória da árvore (usa pós-ordem)
void liberarArvore(No *raiz) {
    if (raiz != NULL) {
        liberarArvore(raiz->esquerda);   // Libera subárvore esquerda
        liberarArvore(raiz->direita);    // Libera subárvore direita
        free(raiz);                      // Libera o nó atual
    }
}

// Função para imprimir a árvore de forma visual (rotacionada 90° para direita)
void imprimirArvore(No *raiz, int espaco) {
    const int INCREMENTO = 10;
    
    if (raiz == NULL) {
        return;
    }
    
    // Aumentar distância entre níveis
    espaco += INCREMENTO;
    
    // Processar subárvore direita primeiro
    imprimirArvore(raiz->direita, espaco);
    
    // Imprimir nó atual após espaçamento
    printf("\n");
    for (int i = INCREMENTO; i < espaco; i++) {
        printf(" ");
    }
    printf("%d\n", raiz->dado);
    
    // Processar subárvore esquerda
    imprimirArvore(raiz->esquerda, espaco);
}

// Função principal com exemplos
int main() {
    No *raiz = NULL;
    
    printf("=== DEMONSTRAÇÃO DE ÁRVORE BINÁRIA DE BUSCA ===\n\n");
    
    // Inserindo valores na árvore
    printf("1. INSERÇÃO DE VALORES:\n");
    int valores[] = {50, 30, 70, 20, 40, 60, 80};
    int numValores = sizeof(valores) / sizeof(valores[0]);
    
    for (int i = 0; i < numValores; i++) {
        raiz = inserir(raiz, valores[i]);
        printf("Inserido: %d\n", valores[i]);
    }
    
    printf("\nÁrvore criada (visualização rotacionada 90°):\n");
    imprimirArvore(raiz, 0);
    
    // Informações sobre a árvore
    printf("\n2. INFORMAÇÕES DA ÁRVORE:\n");
    printf("Altura: %d\n", altura(raiz));
    printf("Total de nós: %d\n", contarNos(raiz));
    
    // Demonstrando os diferentes percursos
    printf("\n3. PERCURSOS (TRAVERSALS):\n");
    printf("Em Ordem (crescente):    ");
    percursoEmOrdem(raiz);
    printf("\nPré-Ordem (raiz primeiro): ");
    percursoPreOrdem(raiz);
    printf("\nPós-Ordem (raiz último):   ");
    percursoPosOrdem(raiz);
    printf("\n");
    
    // Demonstrando busca
    printf("\n4. BUSCA DE VALORES:\n");
    int valorBusca[] = {40, 25, 80, 100};
    int numBuscas = sizeof(valorBusca) / sizeof(valorBusca[0]);
    
    for (int i = 0; i < numBuscas; i++) {
        if (buscar(raiz, valorBusca[i])) {
            printf("Valor %d: ENCONTRADO\n", valorBusca[i]);
        } else {
            printf("Valor %d: NÃO ENCONTRADO\n", valorBusca[i]);
        }
    }
    
    // Demonstrando remoção
    printf("\n5. REMOÇÃO DE NÓS:\n");
    printf("Removendo o valor 20 (nó folha):\n");
    raiz = remover(raiz, 20);
    printf("Em ordem após remoção: ");
    percursoEmOrdem(raiz);
    
    printf("\nRemovendo o valor 30 (nó com dois filhos):\n");
    raiz = remover(raiz, 30);
    printf("Em ordem após remoção: ");
    percursoEmOrdem(raiz);
    
    printf("\n\nÁrvore final:\n");
    imprimirArvore(raiz, 0);
    
    // Limpeza da memória
    printf("\n6. LIBERANDO MEMÓRIA:\n");
    liberarArvore(raiz);
    printf("Memória liberada com sucesso!\n");
    
    return 0;
}

/*
=== ANÁLISE DE COMPLEXIDADE ===

OPERAÇÕES EM BST (caso médio):
- Inserção: O(log n)
- Busca: O(log n)
- Remoção: O(log n)
- Percursos: O(n)

OPERAÇÕES EM BST (pior caso - árvore degenerada):
- Inserção: O(n)
- Busca: O(n)
- Remoção: O(n)

ESPAÇO:
- Memória: O(n) para armazenar n nós
- Pilha de recursão: O(h) onde h é a altura da árvore

=== APLICAÇÕES PRÁTICAS ===
1. Sistemas de busca e indexação
2. Implementação de dicionários e mapas
3. Análise de expressões matemáticas
4. Algoritmos de ordenação (TreeSort)
5. Sistemas de arquivos hierárquicos
*/