Layra Soares Machado lsm24 - Interprete e descreva todas as funções do TAD "abp h"

Prévia do material em texto

#include <malloc.h>
#include <stdio.h>
typedef int telem; /* tipo base dos elementos da árvore */
typedef struct no /* estrutura utilizada para armazenar as informações
e dois campos de ponteiros */ {
struct no *esq;
telem info;
struct no *dir;
} tno; /* nó da árvore */
typedef tno *tabp; /* ponteiro para a raiz da árvore */
void criar (tabp *T) /* iniciando a raiz o primeiro nó da nossa árvore
onde ela irá começar , verifica se está retornando a NULL */
{
*T = NULL;
}
int vazia (tabp T)
{
return (T == NULL);
}
tabp busca(tabp T, telem dado) /* Nesta estrutura ocorre uma busca nos
elementos dos nós verificando se T retorna a NULL, caso não, verifica
T apontando pro info se retorna dado senão retorna retorna pra t que
aponta pra info que e maior q dado que retorna a busca pra esquerda
SENÃO retorna pra direita.*/
{
if (T == NULL)
return NULL;
if (T->info == dado)
return T;
if (T->info > dado)
return busca(T->esq, dado);
else
return busca(T->dir, dado);
}
int inserir (tabp *T, telem item) /* nesta estrutura está inserindo um
item recebendo um ponteiro para a árvore ou seja nó da árvore, primeiro
verifica se ele e NULL ,depois cria um novo nó utilizando a função
malloc para alocar a memória para esse novo nó com seu endereço, então
nao tenho ninguem a esquerda e a direita então o meu ponteiro é nulo
(*T)->esq = NULL;(*T)->dir = NULL; , logo então a minha raiz irá
receber o meu primeiro nó que acabei de criar (*T)->info = item;
{
int ok;
if (*T == NULL)
{
*T = (tno *) malloc(sizeof(tno));
if (*T == NULL)
return 0;
(*T)->esq = NULL;
(*T)->dir = NULL;
(*T)->info = item;
return 1;
}
if ((*T)->info < item)
ok = inserir(&((*T)->dir), item);
else
if ((*T)->info > item)
ok = inserir(&((*T)->esq), item);
else
ok = 0;
return ok;
}
void exibir (tabp T)/* Nesta estrutura irá exibir os elementos dos nós
dá árvores tanto a esquerda quanto a direita.
{
if (T != NULL)
{
exibir (T->esq);
printf ("%d ",T->info);
exibir (T->dir);
}
}
void esvaziar(tabp *T)/* Nesta estrutura irá esvaziar os elementos dos
nós dá árvores tanto a esquerda quanto a direita, VEMOS 3 maneiras
abaixo de remover esses nós, 1° verifica se um dos filhos não é nulo ,
aí verifica se a esquerda e diferente de nulo se for ai o aux recebe
endereço esquerda faz o mesmo para a direita, salva o endereço de
memória do nó filho e aí podemos retorna o endereço de memória do aux
do filho à esquerda ou à direita {
if (*T == NULL)
return;
esvaziar(&(*T)->esq);// remove nós folhas
esvaziar(&(*T)->dir);// remove nós folhas
free(*T);
*T = NULL;
}
tabp MaiorDireita(tabp *no){
if((*no)->dir != NULL) // remove nós folhas que possui filhos dir
return MaiorDireita(&(*no)->dir);
else{
tabp aux = *no;
if((*no)->esq != NULL) // remove nós folhas que possui filhos esq
*no = (*no)->esq;
else
*no = NULL;
return aux;
}
}
tabp MenorEsquerda(tabp *no){
if((*no)->esq != NULL)
return MenorEsquerda(&(*no)->esq);
else{
tabp aux = *no;
if((*no)->dir != NULL)
*no = (*no)->dir;
else
*no = NULL;
return aux;
}
}
void remover(tabp *T, int dado){ \\2° verifica se a raiz é nula se a
raiz não for nula verifica a sub árvore à esquerda e à direita , em
seguida a raiz não for nula e tiver um elemento raiz logo devemos
acessar esta raiz não nula e verificar sub nó à direita e a esquerda
comparando com conteúdo e fazendo o retorno da chamada recursiva …
if(*T == NULL)
{
printf("Numero nao encontrado na arvore!");
return;
}
if(dado < (*T)->info)
remover(&(*T)->esq, dado);
else
if(dado > (*T)->info)
remover(&(*T)->dir, dado);
else
{
tabp pAux = *T;
if (((*T)->esq == NULL) && ((*T)->dir == NULL))
{
free(pAux);
(*T) = NULL;
}
else
{
if ((*T)->esq == NULL)
{
(*T) = (*T)->dir;
pAux->dir = NULL;
free(pAux); pAux = NULL;
}
else
{
if ((*T)->dir == NULL)
{
(*T) = (*T)->esq;
pAux->esq = NULL;
free(pAux); pAux = NULL;
}
else
{
pAux = MaiorDireita(&(*T)->esq);
pAux->esq = (*T)->esq;
pAux->dir = (*T)->dir;
(*T)->esq = (*T)->dir = NULL;
free((*T));
*T = pAux;
pAux = NULL;
}
}
}
}
}