Estrutura De Dados

Árvores binárias de busca

typedef struct s_cel {

int elem;

struct s_cel *esq,*dir;

} cel;

typedef cel* no;

no busca(no raiz, int valor) {

no p = raiz;

while((p!=NULL)&&(p->elem!=valor) {

if(p->elem>valor)

p=p->esq;

else

p=p->dir;

}

return p;

}

– Implemente a versão recursiva do algoritmo de busca

no buscaRec(no raiz, int valor) {

if( raiz->elem == valor)

return raiz;

if(raiz->elem > valor)

return(buscaRec(raiz->esq);

if(raiz->elem < valor)

return(buscaRec(raiz->dir);

}

– Escrever em C a rotina insABB(raiz,x) que insira o elemento x na árvore binária de busca ABB

– Representar a ávore binária de busca depois da inserção dos elementos: 5 9 3 1 8 3 4 2 7

– Escrever em C a rotina max(ABB) que retorne o maior elemento de uma árvore binária de busca ABB

– Escreva uma rotina recursiva alt(p) que calcule a altura da árvore binária apontada por p.

– Escreva um programa usando árvore binária de busca que calcule o número de repetições num vetor de inteiros.

Inserção em árvore AVL

typedef struct s_cel {

int elem;

int altura;

struct s_cel *esq,*dir;

} cel;

typedef cel* no;

no insere(no esse, int valor){

if(esse==NULL)

esse=criano(valor);

else {

if(valor<esse->elem) {

esse->esq=insere(esse->esq,valor);

if(altura(esse->esq)-altura(esse->dir)==2)

if(valor < esse->esq->elem)

esse = rodaUmEsquerda(esse);

else

esse = rodaDuploEsquerda(esse);

}

else

if(valor > esse->elem) {

esse->dir=insere(esse->dir,valor);

if(altura(esse->dir)-altura(esse->esq)==2)

if(valor > esse->dir->elem)

esse = rodaUmDireita(esse);

else

esse = rodaDuploDireita(esse);

}

}

esse->altura = Max(altura(esse->esq),altura(esse->dir))+1;

return esse;

}

no criano(int valor) {

no novo = malloc(sizeof(cel));

novo->elem=valor;

novo->esq=novo->dir=NULL;