Aula prática 09: árvores binárias de busca

Esta lista é para praticar o conteúdo, sem correção individual. Use Resposta esperada para comparação e autocorreção. Faça os desenhos no papel ou na ferramenta que preferir. Os trechos em C usam a representação e os nomes da implementação da aula. Não é necessário montar um programa completo. O tempo estimado inclui tentativa e conferência.

Convenções: cada exercício começa no estado apresentado, independentemente dos anteriores. Dentro de uma sequência, as operações são cumulativas. NULL significa ausência de nó ou de endereço válido, conforme o contexto. A raiz está no nível 1. A altura conta níveis: árvore vazia tem altura 0 e folha tem altura 1. Considere as alocações bem-sucedidas, salvo quando o exercício apresentar uma falha.

Representação em C: cada struct NO guarda info, esq e dir. O tipo ArvBin representa um ponteiro para nó. ArvBin* raiz aponta para uma alocação separada que guarda esse ponteiro, chamada aqui de caixa da raiz.

/* Um nó guarda a chave e os endereços dos filhos. */
struct NO{
    int info;
    struct NO *esq;
    struct NO *dir;
};

/* ArvBin representa o endereço de um nó. */
typedef struct NO* ArvBin;

raiz é o endereço da caixa. *raiz é seu conteúdo, o endereço do primeiro nó. (*raiz)->info acessa a chave desse nó. -> acessa um campo pelo ponteiro e & obtém um endereço. Assim, &((*raiz)->esq) permite tratar o campo esquerdo como a caixa de uma subárvore. Só use *raiz se raiz != NULL e só acesse os campos se *raiz != NULL.

= atribui, == compara e return encerra a chamada atual. malloc reserva memória e pode retornar NULL. free libera uma alocação sem atualizar automaticamente quem guardava seu endereço. Os trechos de funções pressupõem as declarações da implementação e as bibliotecas <stdlib.h> e <stdio.h>. As funções auxiliares libera_NO e remove_atual são usadas dentro de ArvoreBinaria.c.

Exercício 1: verificar a propriedade da ABB

Observe a posição de cada nó. Para verificar uma ABB, considere todos os descendentes de cada subárvore.

Classifique a estrutura e justifique:

1. É uma árvore binária?
2. É uma árvore binária de busca?

Exercício 2: criar a árvore sem criar um nó

Observe os estados A, B e C. A e B mostram o resultado da criação. Em C, um nó já foi inserido.

Responda com base na imagem:

1. Associe A, B e C a: falha de criação, árvore vazia e árvore com um nó.
2. Em C, quais são os valores de info, esq e dir?
3. Por que a caixa da raiz não conta como nó?

ArvBin* cria_ArvBin(){
    ArvBin* raiz = (ArvBin*) malloc(sizeof(ArvBin));
    if(raiz != NULL)
        *raiz = NULL;
    return raiz;
}

Exercício 3: inserir chaves e descartar uma duplicata

Faça um rastreamento manual das inserções. Use o código abaixo como referência para acompanhar os passos no desenho.

novo é o nó candidato. atual percorre a árvore, e ant guarda o pai.

As verificações iniciais tratam falhas de alocação. O laço procura uma posição vazia e descarta duplicatas. A comparação final liga o novo nó ao pai.

A função retorna 1 ao inserir e 0 para duplicata, falha de alocação ou caixa inexistente.

int insere_ArvBin(ArvBin* raiz, int valor){
    if(raiz == NULL)
        return 0;
    struct NO* novo;
    novo = (struct NO*) malloc(sizeof(struct NO));
    if(novo == NULL)
        return 0;
    novo->info = valor;
    novo->dir = NULL;
    novo->esq = NULL;

    if(*raiz == NULL)
        *raiz = novo;
    else{
        struct NO* atual = *raiz;
        struct NO* ant = NULL;
        while(atual != NULL){
            ant = atual;
            if(valor == atual->info){
                free(novo);
                return 0;//elemento já existe
            }

            if(valor > atual->info)
                atual = atual->dir;
            else
                atual = atual->esq;
        }
        if(valor > ant->info)
            ant->dir = novo;
        else
            ant->esq = novo;
    }
    return 1;
}

Considere que ArvBin* raiz = cria_ArvBin(); já criou uma árvore vazia. Faça um trace manual do código simulando as inserções de 32, 18, 46, 25, 38 e 18, nessa ordem, com insere_ArvBin(raiz, valor).

Desenhe os estados intermediários que precisar para acompanhar as inserções. Na última tentativa, anote o retorno da função.

Na resposta esperada, você encontrará apenas a árvore final e o retorno da última tentativa para conferir seu raciocínio.

Exercício 4: rastrear uma busca com e sem sucesso

Observe os filhos de cada nó. Os campos NULL mostram onde uma busca pode terminar sem encontrar a chave.

Rastreie as buscas por 55 e por 25, cada uma começando na raiz. Use busca_ArvBin(raiz, valor).

Para cada busca, registre:

1. Os nós examinados, na ordem.
2. A direção de cada descida (esq ou dir).
3. O retorno da função. Inclua o NULL final no caminho se a chave estiver ausente.

Apoio em C:

Leia o código de busca da aula. atual começa no primeiro nó. O laço compara a chave e segue apenas uma subárvore.

A busca retorna o endereço do nó encontrado ou NULL. O return 0 inicial também representa um ponteiro nulo.

struct NO* busca_ArvBin(ArvBin *raiz, int valor){
    if(raiz == NULL)
        return 0;
    struct NO* atual = *raiz;
    while(atual != NULL){
        if(valor == atual->info){
            return atual;
        }
        if(valor > atual->info)
            atual = atual->dir;
        else
            atual = atual->esq;
    }
    return NULL;
}

Exercício 5: rastrear a exibição em Pré-Ordem

Observe as ligações da árvore. O percurso pode começar em qualquer nó e visitar a subárvore que começa nele.

Qual sequência será exibida por preOrdem_NO(no), com no apontando para o nó 7? Escreva os valores na ordem de exibição.

Apoio em C:

Use a mesma struct NO da aula. A função recebe diretamente um ponteiro para nó. Ela exibe info, percorre esq e depois dir.

/* Exibe em Pré-Ordem a subárvore que começa em no. */
void preOrdem_NO(struct NO* no){
    /* Encerra o ramo vazio para evitar acesso a um nó inexistente. */
    if(no == NULL)
        return;
    printf("%d\n", no->info);
    preOrdem_NO(no->esq);
    preOrdem_NO(no->dir);
}

Exercício 6: rastrear a exibição em Em-Ordem

Observe a mesma árvore do exercício 5. O ponteiro no indica o início do percurso.

Faça um trace manual de exibir_em_ordem(no), com no apontando para o nó 7, e escreva a sequência exibida.

Apoio em C:

void exibir_em_ordem(struct NO* no) {
    if (no == NULL) {
        return;
    }
    exibir_em_ordem(no->esq);
    printf("%d\n", no->info);
    exibir_em_ordem(no->dir);
}

Exercício 7: rastrear a exibição em Pós-Ordem

Observe a mesma árvore do exercício 5. O ponteiro no indica o início do percurso.

Faça um trace manual de exibir_pos_ordem(no), com no apontando para o nó 7, e escreva a sequência exibida.

Apoio em C:

void exibir_pos_ordem(struct NO* no) {
    if (no == NULL) {
        return;
    }
    exibir_pos_ordem(no->esq);
    exibir_pos_ordem(no->dir);
    printf("%d\n", no->info);
}

Exercício 8: liberar a memória de todos os nós da árvore

Considere o fim do uso da árvore: todos os nós serão liberados da memória.

Onde colocar free(no); para destruir todos os nós?

1. Indique A, B ou C para liberar todos os nós com segurança. Deixe as outras posições vazias.
2. Escreva a ordem dos valores de info dos registros liberados.

Apoio em C:

A função libera_NO é a auxiliar recursiva de libera_ArvBin no código da aula. Os comentários A, B e C marcam as posições possíveis para acrescentar free(no);.

free(no) libera apenas o registro indicado. Seus campos não podem ser acessados depois da liberação. A função percorre esq antes de dir.

/* Libera os nós; a posição da liberação deve preservar os filhos. */
void libera_NO(struct NO* no){
    /* Uma posição vazia não possui registro para liberar. */
    if(no == NULL)
        return;
    /* A */
    libera_NO(no->esq);
    /* B */
    libera_NO(no->dir);
    /* C */
}

Exercício 9: encerrar a destruição da caixa da raiz

Considere que raiz aponta para uma caixa válida. libera_NO(*raiz) já libera todos os nós, mas a caixa é uma alocação separada.

/* Libera os nós e, em seguida, a caixa da raiz. */
void libera_ArvBin(ArvBin* raiz){
    /* Sem caixa, não há memória a devolver. */
    if(raiz == NULL)
        return;
    libera_NO(*raiz);
    /* Acrescente aqui a liberação da caixa. */
}

No chamador, a variável ArvBin* raiz já existe:

libera_ArvBin(raiz);
/* Acrescente aqui a atualização da variável do chamador. */

Complete os dois pontos indicados com instruções em C:

1. Na função, libere a caixa da raiz.
2. No chamador, faça raiz deixar de guardar o endereço liberado.

void libera_ArvBin(ArvBin* raiz){
    if(raiz == NULL)
        return;
    libera_NO(*raiz);//libera cada nó
    free(raiz);//libera a raiz
}

libera_ArvBin(raiz);
raiz = NULL;

Exercício 10: distinguir contagem e altura

Compare duas funções que recebem um ponteiro para o nó inicial de uma subárvore:

/* Retorna a quantidade de nós da subárvore que começa em no. */
int contar_nos(struct NO* no);

/* Retorna a altura em níveis da subárvore que começa em no. */
int calcular_altura(struct NO* no);

no pode apontar para qualquer nó. Quando no == NULL, as duas funções já retornam 0.

Dentro de contar_nos, as contagens das subárvores já foram calculadas:

int total_esquerda = contar_nos(no->esq);
int total_direita = contar_nos(no->dir);

Dentro de calcular_altura, as alturas das subárvores também já foram calculadas:

int altura_esquerda = calcular_altura(no->esq);
int altura_direita = calcular_altura(no->dir);

Complete o final de cada função, em C:

1. Escreva o return de contar_nos.
2. Escreva o final de calcular_altura. Use if para escolher o caminho mais longo.

Não é necessário escrever as funções inteiras.

return 1 + total_esquerda + total_direita;

/* Apenas o maior caminho determina a altura. */
if (altura_esquerda > altura_direita) {
    return 1 + altura_esquerda;
}
return 1 + altura_direita;

Exercício 11: rastrear a remoção de uma folha

Considere que raiz aponta para a caixa da árvore abaixo.

Faça um trace manual da chamada remove_ArvBin(raiz, 36) usando as duas funções abaixo.

Apoio em C:

int remove_ArvBin(ArvBin *raiz, int valor){
    if(raiz == NULL)
        return 0;
    struct NO* ant = NULL;
    struct NO* atual = *raiz;
    while(atual != NULL){
        if(valor == atual->info){
            if(atual == *raiz)
                *raiz = remove_atual(atual);
            else{
                if(ant->dir == atual)
                    ant->dir = remove_atual(atual);
                else
                    ant->esq = remove_atual(atual);
            }
            return 1;
        }
        ant = atual;
        if(valor > atual->info)
            atual = atual->dir;
        else
            atual = atual->esq;
    }
    return 0;
}

struct NO* remove_atual(struct NO* atual){
    struct NO *no1, *no2;
    if(atual->esq == NULL){
        no2 = atual->dir;
        free(atual);
        return no2;
    }
    no1 = atual;
    no2 = atual->esq;
    while(no2->dir != NULL){
        no1 = no2;
        no2 = no2->dir;
    }

    if(no1 != atual){
        no1->dir = no2->esq;
        no2->esq = atual->esq;
    }
    no2->dir = atual->dir;
    free(atual);
    return no2;
}

Exercício 12: rastrear a remoção da raiz com um filho

Considere que raiz aponta para a caixa da árvore abaixo.

Faça um trace manual da chamada remove_ArvBin(raiz, 52) usando as funções remove_ArvBin e remove_atual do exercício 11.

Exercício 13: localizar os substitutos de um nó com dois filhos

Observe as duas subárvores da raiz 60. Para achar o maior valor de uma subárvore, siga dir. Para achar o menor, siga esq.

Localize os dois candidatos a substituir 60:

1. O maior nó da subárvore esquerda.
2. O menor nó da subárvore direita.

Para cada candidato, escreva o caminho a partir da raiz da subárvore e o valor de info. A função remove_atual da aula usa o maior da esquerda.

Exercício 14: rastrear a remoção da raiz com dois filhos

Considere que raiz aponta para a caixa da árvore abaixo.

Faça um trace manual da chamada remove_ArvBin(raiz, 64) usando as funções remove_ArvBin e remove_atual do exercício 11.

Perceba que nesse caso, vai acontecer uma busca pelo nó de maior valor da subárvore esquerda.

Exercício 15: verificar o critério de balanceamento

Compare as árvores A e B, que contêm as mesmas chaves.

Considere balanceada uma árvore em que, em cada nó, as alturas das subárvores esquerda e direita diferem no máximo em 1.

Classifique A e B como balanceada ou não balanceada e justifique.

Exercício 16: comparar os maiores caminhos de busca

Observe as árvores A e B. Cada seta entre dois nós representa uma aresta.

Compare a busca bem-sucedida mais longa em A e B, começando na raiz.

Para cada árvore, informe: altura em níveis, nós examinados e arestas percorridas.