Prática – Árvore Binária de Pesquisa (ABP).

Trabalho Prático 001

1) Prática – Árvore Binária de Pesquisa (ABP).

a) Implemente o algoritmo de árvore binária de pesquisa tratado nas aulas práticas.

Nas aulas práticas desenvolvemos, adaptamos e modificamos alguns itens do

algoritmo para ABP. Neste trabalho devemos desenvolver todas as operações

com ABP e no programa principal um menu de opções como segue: 1-Inserir na

árvore; 2-Retirar da árvore; 3-Pesquisa na árvore; 4-Caminhamento Central; 5-

Caminhamento Pré-Ordem; 6-Caminhamento Pós-Ordem; 7-Finalizar;

• A opção 1-Inserir deverá solicitar um valor para o usuário e inserir na árvore.

• A opção 2-Retirar deverá solicitar um valor para o usuário e retirar da

árvore.

• A opção 3-Pesquisa deverá solicitar um valor para o usuário e pesquisar este

valor na árvore, informando se este valor está ou não na árvore.

• As opções 4-Central, 5-Pré e 6-Pós devem realizar os caminhamentos

Central, Pré-Ordem e Pós-Ordem, respectivamente, na árvore.

• A opção 7-Finalizar deverá encerrar o programa.

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

#define MAX 20

typedef long TipoChave;

typedef struct TipoRegistro {

TipoChave Chave;

} TipoRegistro;

typedef struct TipoNo * TipoApontador;

typedef struct TipoNo {

TipoRegistro Reg;

TipoApontador Esq, Dir;

} TipoNo;

typedef TipoApontador TipoDicionario;

void Pesquisa(TipoRegistro *x, TipoApontador *p)

{ if (*p == NULL)

{ printf("Erro: Não existe na arvore\n");

return;

} if (x->Chave < (*p)->Reg.Chave)

{

Pesquisa(x, &(*p)->Esq);

printf(" Esta localizado na arvore\n");

return;

}

if (x->Chave > (*p)->Reg.Chave)

Pesquisa(x, &(*p)->Dir);

//printf(" Esta localizado a Direita da arvore\n");

else{

*x = (*p)->Reg;

printf(" Registro localizado na arvore\n");

}

}

void Insere(TipoRegistro x, TipoApontador *p)

{ if (*p == NULL)

{ *p = (TipoApontador)malloc(sizeof(TipoNo));

(*p)->Reg = x;

(*p)->Esq = NULL;

(*p)->Dir = NULL;

return;

}

if (x.Chave < (*p)->Reg.Chave)

{ Insere(x, &(*p)->Esq);

return;

}

if (x.Chave > (*p)->Reg.Chave)

Insere(x, &(*p)->Dir);

else printf("Erro : Registro ja esta na arvore\n");

}

void Inicializa(TipoApontador *Dicionario)

{ *Dicionario = NULL; }

void Antecessor(TipoApontador q, TipoApontador *r)

{ if ((*r)->Dir != NULL)

{ Antecessor(q, &(*r)->Dir);

return;

}

q->Reg = (*r)->Reg;

q = *r;

*r = (*r)->Esq;

free(q);

}

void Retira(TipoRegistro x, TipoApontador *p)

{ TipoApontador Aux;

if (*p == NULL)

{ printf("Erro : Registro nao esta na arvore\n");

return;

}

if (x.Chave < (*p)->Reg.Chave) { Retira(x, &(*p)->Esq); return; }

if (x.Chave > (*p)->Reg.Chave) { Retira(x, &(*p)->Dir); return; }

if ((*p)->Dir == NULL)

{ Aux = *p; *p = (*p)->Esq;

free(Aux);

return;

}

if ((*p)->Esq != NULL)

{ Antecessor(*p, &(*p)->Esq);

return;

}

Aux = *p; *p = (*p)->Dir;

Free (Aux);