Como criar uma ÁRVORE BINÁRIA de PESSOAS?

Dando continuidade ao nosso Curso de Programação C e ao estudo das árvores binárias de busca, até o momento toda árvore binária que construímos era uma árvore binária de número inteiros. Nesta aula vamos construir uma árvore binária de pessoas.

A primeira coisa que precisamos definir é quais dados o tipo pessoa irá possuir e, principalmente, que dado será a chave utilizada na busca e remoção. Nosso tipo pessoa é definido no trecho de código a seguir e a chave será o campo cpf.

/*
      Definição do tipo pessoa com nome e cpf
*/
typedef struct{
    char nome[50];
    int cpf;
}Pessoa;

Provavelmente será necessário ler os dados de uma pessoa a partir do teclado e imprimir essas pessoas na tela, ao imprimir a árvore. Então, iremos precisar também de procedimentos para estas ações, apresentados no trecho de código a seguir.

/*
     Função para ler os dados de uma pessoa
*/
Pessoa ler_pessoa(){
    Pessoa p;
    printf("\tDigite o nome da pessoa: ");
    fgets(p.nome, 49, stdin);
    printf("\tDigite o cpf: ");
    scanf("%d", &p.cpf);
    return p;
}

//   Procedimento para imprimir os dados de uma pessoa
void imprimir_pessoa(Pessoa p){
    printf("\tNome: %s\tCpf: %d\n", p.nome, p.cpf);
}

Agora, o nó da nossa árvore binária não terá apenas um número inteiro em seu interior, mas uma variável do tipo pessoa, assim:

/*
     Definição do nó da árvore binária
*/
typedef struct no{
    Pessoa pessoa;
    struct no *direita, *esquerda;
}NoArv;

Por fim, precisamos alterar o código já desenvolvido para suportar as operações de inserção, busca e remoção com o tipo pessoa, tendo o cpf como chave, como apresentado no código abaixo.

Código de exemplo completo em C para uma Árvore Binária de Pessoas

/*
            Aula 277: Árvore Binária de Busca de Pessoas

            Código escrito por Wagner Gaspar
            Setembro de 2021
*/

typedef struct{
    char nome[50];
    int cpf;
}Pessoa;

typedef struct no{
    Pessoa pessoa;
    struct no *direita, *esquerda;
}NoArv;

Pessoa ler_pessoa(){
    Pessoa p;
    printf("\tDigite o nome da pessoa: ");
    fgets(p.nome, 49, stdin);
    printf("\tDigite o cpf: ");
    scanf("%d", &p.cpf);
    return p;
}

void imprimir_pessoa(Pessoa p){
    printf("\tNome: %s\tCpf: %d\n", p.nome, p.cpf);
}

NoArv* inserir_versao_1(NoArv *raiz, Pessoa p){
    if(raiz == NULL){
        NoArv *aux = malloc(sizeof(NoArv));
        aux->pessoa = p;
        aux->esquerda = NULL;
        aux->direita = NULL;
        return aux;
    }
    else{
        if(p.cpf < raiz->pessoa.cpf)
            raiz->esquerda = inserir_versao_1(raiz->esquerda, p);
        else
            raiz->direita = inserir_versao_1(raiz->direita, p);
        return raiz;
    }
}

void inserir_versao_2(NoArv **raiz, Pessoa p){
    if(*raiz == NULL){
        *raiz = malloc(sizeof(NoArv));
        (*raiz)->pessoa = p;
        (*raiz)->esquerda = NULL;
        (*raiz)->direita = NULL;
    }
    else{
        if(p.cpf < (*raiz)->pessoa.cpf)
            inserir_versao_2(&((*raiz)->esquerda), p);
        else
            inserir_versao_2(&((*raiz)->direita), p);
    }
}

void inserir_versao_3(NoArv **raiz, Pessoa p){
    NoArv *aux = *raiz;
    while(aux){
        if(p.cpf < aux->pessoa.cpf)
            raiz = &aux->esquerda;
        else
            raiz = &aux->direita;
        aux = *raiz;
    }
    aux = malloc(sizeof(NoArv));
    aux->pessoa = p;
    aux->esquerda = NULL;
    aux->direita = NULL;
    *raiz = aux;
}

NoArv* buscar_versao_1(NoArv *raiz, int cpf){
    if(raiz){
        if(cpf == raiz->pessoa.cpf)
            return raiz;
        else if(cpf < raiz->pessoa.cpf)
            return buscar_versao_1(raiz->esquerda, cpf);
        else
            return buscar_versao_1(raiz->direita, cpf);
    }
    return NULL;
}

NoArv* buscar_versao_2(NoArv *raiz, int cpf){
    while(raiz){
        if(cpf < raiz->pessoa.cpf)
            raiz = raiz->esquerda;
        else if(cpf > raiz->pessoa.cpf)
            raiz = raiz->direita;
        else
            return raiz;
    }
    return NULL;
}

int altura(NoArv *raiz){
    if(raiz == NULL){
        return -1;
    }
    else{
        int esq = altura(raiz->esquerda);
        int dir = altura(raiz->direita);
        if(esq > dir)
            return esq + 1;
        else
            return dir + 1;
    }
}

int quantidade_nos(NoArv *raiz){
    if(raiz == NULL)
        return 0;
    else
        return 1 + quantidade_nos(raiz->esquerda) + quantidade_nos(raiz->direita);

    // operador ternário
    //return (raiz == NULL)? 0: 1 + quantidade_nos(raiz->esquerda) + quantidade_nos(raiz->direita);
}

int quantidade_folhas(NoArv *raiz){
    if(raiz == NULL)
        return 0;
    else if(raiz->esquerda == NULL && raiz->direita == NULL)
        return 1;
    else
        return quantidade_folhas(raiz->esquerda) + quantidade_folhas(raiz->direita);
}

// função para remover nós da Árvore binária
NoArv* remover(NoArv *raiz, int chave) {
    if(raiz == NULL){
        printf("Valor nao encontrado!\n");
        return NULL;
    } else { // procura o nó a remover
        if(raiz->pessoa.cpf == chave) {
            // remove nós folhas (nós sem filhos)
            if(raiz->esquerda == NULL && raiz->direita == NULL) {
                free(raiz);
                printf("Elemento folha removido: %d !\n", chave);
                return NULL;
            }
            else{
                // remover nós que possuem 2 filhos
                if(raiz->esquerda != NULL && raiz->direita != NULL){
                    Pessoa p;
                    NoArv *aux = raiz->esquerda;
                    while(aux->direita != NULL)
                        aux = aux->direita;
                    p = raiz->pessoa;
                    raiz->pessoa = aux->pessoa;
                    aux->pessoa = p;
                    printf("Elemento trocado: %d !\n", chave);
                    raiz->esquerda = remover(raiz->esquerda, chave);
                    return raiz;
                }
                else{
                    // remover nós que possuem apenas 1 filho
                    NoArv *aux;
                    if(raiz->esquerda != NULL)
                        aux = raiz->esquerda;
                    else
                        aux = raiz->direita;
                    free(raiz);
                    printf("Elemento com 1 filho removido: %d !\n", chave);
                    return aux;
                }
            }
        } else {
            if(chave < raiz->pessoa.cpf)
                raiz->esquerda = remover(raiz->esquerda, chave);
            else
                raiz->direita = remover(raiz->direita, chave);
            return raiz;
        }
    }
}

void imprimir_versao_1(NoArv *raiz){ // 50 25 30 100
    if(raiz){
        imprimir_pessoa(raiz->pessoa);
        imprimir_versao_1(raiz->esquerda);
        imprimir_versao_1(raiz->direita);
    }
}

void imprimir_versao_2(NoArv *raiz){ // 25 30 50 100
    if(raiz){
        imprimir_versao_2(raiz->esquerda);
        imprimir_pessoa(raiz->pessoa);
        imprimir_versao_2(raiz->direita);
    }
}

int main(){

    NoArv *busca, *raiz = NULL;
    int opcao, valor;

    do{
        printf("\n\t0 - Sair\n\t1 - Inserir\n\t2 - Imprimir\n\t3 - Buscar\n\t4 - Altura\n\t5 - Tamanho\n\t6 - Folhas\n\t7 - Remover\n");
        scanf("%d", &opcao);
        scanf("%c");

        switch(opcao){
        case 1:
            //printf("\n\tDigite um valor: ");
            //scanf("%d", &valor);
            //raiz = inserir_versao_1(raiz, valor);
            //inserir_versao_2(&raiz, valor);
            inserir_versao_3(&raiz, ler_pessoa());
            break;
        case 2:
            printf("\n\tPrimeira impressao:\n\t");
            imprimir_versao_1(raiz);
            printf("\n");
            printf("\n\tSegunda impressao:\n\t");
            imprimir_versao_2(raiz);
            printf("\n");
            break;
        case 3:
            printf("\n\tDigite o cpf a ser procurado: ");
            scanf("%d", &valor);
            //busca = buscar_versao_1(raiz, valor);
            busca = buscar_versao_2(raiz, valor);
            if(busca){
                printf("\n\tValor encontrado:\n");
                imprimir_pessoa(busca->pessoa);
            }
            else
                printf("\n\tValor nao encontrado!\n");
            break;
        case 4:
            printf("\n\tAltura da arvore: %d\n\n", altura(raiz));
            break;
        case 5:
            printf("\n\tQuantidade de nos: %d\n", quantidade_nos(raiz));
            break;
        case 6:
            printf("\n\tQuantidade folhas: %d\n", quantidade_folhas(raiz));
            break;
        case 7:
            printf("\t");
            imprimir_versao_2(raiz);
            printf("\n\tDigite o cpf a ser removido: ");
            scanf("%d", &valor);
            raiz = remover(raiz, valor);
            break;
        default:
            if(opcao != 0)
                printf("\n\tOpcao invalida!!!\n");
        }
    }while(opcao != 0);

    return 0;
}

Início