[code lang=”c”]/*
UCB
Autor: Rodrigo Teles Calado
Descricao: Trabalhar com insercao e remocao de nos em arvore binaria.
Data: 25/10/2007
*/

/* Bibliotecas a serem incluidas */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* Definicao das estruturas */

/* Contem o no da arvore */
typedef struct stNo {
int info, altura;
struct stNo *esq, *dir;
} tNo;

/* Os prototipos */
tNo *cria_arvore(int );
tNo *cria_no(void );
void pos_esq (tNo *, int );
void pos_dir (tNo *, int );
void visita (tNo *);
void visitaem (tNo *);
void pos (tNo *);
void em (tNo *);
tNo *remover (tNo *, int);

/* Aqui comeca tudo */
void main(void ) {
tNo *raiz, /* raiz da arvore binaria */
*p, *q; /* ponteiros auxiliares */
char linha[80], /* linha com os numeros para a arvore */
*numero; /* ponteiro para os numeros lidos */
int num; /* numero em formato int */

puts("Entre com os numeros inteiros, separados por brancos.");
puts("Use uma unica linha para fornecer os numeros.");
gets(linha);

numero = strtok(linha, " "); /* pega o primeiro numero da lista */
num = atoi(numero); /* converte para inteiro */
raiz = cria_arvore(num); /* insere na raiz */
numero = strtok(NULL, " "); /* pega o segundo numero */

while (numero) {
q = raiz; p = raiz;
printf("Li numero %d\n", num); /* le novo numero */
num = atoi(numero);

while (num != p->info && q) { /* procura na arvore */
p = q;
if (num < p->info)
q = p->esq; /* passa para arvore esquerda */
else
q = p->dir; /* passa para direita */
}

if (num == p->info)
printf("O numero %d ja existe na arvore.\n", num);
else { /* nao achei, vou inserir o numero na arvore */
if (num < p->info)
pos_esq(p, num); /* insere na arvore esquerda */
else
pos_dir(p, num); /* insere na arvore direita */
}
numero = strtok(NULL, " "); /* continuemos */
} /* fim do while (numero) */

/* Aqui imprimimos a arvore e calculamos a altura de cada no */
puts("Imprime a arvore em pos ordem");
pos(raiz);

/* Como ficam os numeros ordenados? */
puts ("Imprime a arvore em ordem");
em(raiz);

/* Bem, vamos remover algo da arvore */
puts("Qual o no a remover.");
gets(linha);
sscanf(linha, "%d", &num);

p = remover (raiz, num);

/* Tenho de recalcular as alturas da arvore,
portanto, vamos pos ordem */
puts("Imprime a arvore em pos ordem");
pos(raiz);

/* Finalmente, imprimimos em ordem para ver se funcionou */
puts ("Imprime a arvore em ordem");
em(raiz);
}

/* A dificil rotina recursiva de percorrem uma arvore em pos ordem */
void pos (tNo *p) {
if (p->esq) pos(p->esq);
if (p->dir) pos(p->dir);
visita(p); /* aqui calcula a altura */
}

/* A tambem dificil rotina de percurso em ordem */
void em (tNo *p) {
if (p->esq) em(p->esq);
visitaem(p); /* Nesta visita nao calculamos a altura */
if (p->dir) em(p->dir);
}

/* A visita em pos ordem e usada para calcular a altura da arvore */
void visita (tNo *p) {
int alt1, alt2;
if (p->esq) alt1 = p->esq->altura;
else alt1 = 0;
if (p->dir) alt2 = p->dir->altura;
else alt2 = 0;
if (alt1>alt2) p->altura = alt1 + 1;
else p->altura = alt2 + 1;
printf("info = %d ", p->info);
printf("altura = %d\n", p->altura);
}

/* So imprime o conteudo do no */
void visitaem (tNo *p) {
printf("info = %d ", p->info);
printf("altura = %d\n", p->altura);
}

/* Cria um no completo para arvore */
tNo *cria_arvore (int x) {
tNo *p;

p = cria_no ();
if (p) {
p->info = x;
p->altura = 0;
return p;
}
else {
puts("Faltou espaco para alocar no.");
return NULL;
}

}

/* Cria um no basico para arvore, usada em cria_arvore */
tNo *cria_no(void ) {
tNo *p;

if ((p = (tNo *) malloc(sizeof(tNo))) == NULL)
return NULL;
else {
p->esq = NULL; p->dir = NULL;
return p;
}
}

/* Insere um no a esquera de um no */
void pos_esq(tNo *p, int x) {
tNo *q;

if (p->esq)
puts("Operacao de insercao a esquerda ilegal.");
else {
q = cria_arvore(x);
p->esq = q;
}
}

/* insere um no a direita de um no */
void pos_dir(tNo *p, int x) {
tNo *q;

if (p->dir)
puts("Operacao de insercao a direita ilegal.");
else {
q = cria_arvore(x);
p->dir = q;
}
}

/* Aqui esta o coracao do programa, a remocao */
tNo *remover (tNo *tree, int num) {
tNo *p, /* p aponta para o no a ser removido */
*q, /* q aponta para o pai do no */
*rp, /* rp aponta que ira substituir o no p */
*f,
*s; /* sucessor do no p */

p = tree; q=NULL;

/* procura o no com a chave num, p aponta para o no
e q aponta para o pai do no */
while ( p && p->info != num) {
q = p;
if ( num < p->info)
p = p->esq;
else
p = p->dir;
} /* fim do while */
if (!p) return NULL; /* a chave nao existe na arvore */

/* agora iremos ver os dois primeiros casos, o no tem um filho
no maximo */
if (p->esq == NULL)
rp = p->dir;
else
if (p->dir == NULL)
rp = p->esq;
else {
f=p;
rp = p->dir;
s = rp->esq; /* s e sempre o filho esq de rp */
while (s != NULL) {
f = rp;
rp = s;
s = rp->esq;
}
/* neste ponto, rp e o sucessor em ordem de p */
if (f != p) {
/* p nao e o pai de rp e rp == f->left */
f->esq = rp->dir;
/* remove o no rp de sua atual posicao e o
substitui pelo filho direito de rp
rp ocupa o lugar de p
*/
rp->dir = p->dir;
}
/* define o filho esquerdo de rp de modo que rp
ocupe o lugar de p
*/
rp->esq = p->esq;
}
/* insere rp na posicao ocupada anteriormente por p */
if (q == NULL)
tree = rp;
else
if (p == q->esq)
q->esq = rp;
else
q->dir = rp;
free(p);
return rp;
}[/code]

Author

Rodrigo Calado é sócio-fundador e CTO do Gran Cursos Online. Graduado em Gestão da Tecnologia da Informação, pós-graduando em Governança de TI pela Universidade Católica de Brasília e cursou MBA em Gestão e Empreendedorismo pela FGV. Possui convicta paixão pela área de tecnologia, educação digital, concursos públicos e empreendedorismo.

Write A Comment