Resumo_Arvore

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Resumo Árvore Binária:
***********************************************************************************
OBS: Essa matéria caía na P3, mas foi removida da grade desse período! (2015.1)
Então >>ANTES<< de ler esse resumo, confirme se Árvore está sendo dada no período que você estiver cursando, pois podem alterar novamente!
***********************************************************************************
- Definição:
Árvore Binária é uma nova forma de armazenar/organizar os dados. É representado por um conjunto de Nós (Bolinhas) interligados no formato de uma árvore. (Muito usado pra representar hierarquias)
Daqui em diante chegamos no nível supremo de abstração e pra melhorar mais ainda, a forma mais tranquila de resolver os problemas de árvore é usando a temida Recursão!
Lembra eu dizendo que na P3 não ia ter escapatória? D:
Pois é, eu sei que é triste, mas agora não tem mais jeito. 
Peraí, escutei um "O que é recursão?" :O
Recomendo mais do que nunca minimizar esse bloco e ler meu "Resumo_Recursão" urgentemente! :D
Pra facilitar, sempre que o assunto for árvore, imagine exatamente dessa forma: 
Imagem: http://equipe.nce.ufrj.br/adriano/c/imagens/arvbin.gif 
OBS: Cada uma dessas bolinhas se chama Nó, sendo que cada Nó possui >>NO MÁXIMO<< 2 filhos! (Isso porque se trata de uma árvore > Binária <!)
OBS2: O Nó principal (O que fica no topo) se chama >> Raíz << e Um Nó que >>NÃO<< possui filhos é chamado de >> Folha <<
***********************************************************************************
Regra Importante: 
Toda Árvore Binária pode ser: 
- Vazia
>>OU<< 
- Possui uma Raíz + uma Sub árvore na esquerda (Esq) + uma Sub árvore na direita (Dir)
OBS: E cada uma das Sub árvores pode ser vazia ou possuir uma raíz mais uma Sub árvore na esquerda e na direita, assim por diante!
É exatamente esse o pensamento que você precisa pra resolver qualquer problema de árvore! :)
***********************************************************************************
>>TODO<< Nó armazena uma informação, um ponteiro para o Nó da esquerda e um ponteiro para o Nó da direita. (Parecido com Lista, só que aqui são dois ponteiros!)
OBS: Se o Nó for uma folha, ambos ponteiros apontam para NULL!
Outro detalhe importante é que esse tipo de árvore > NUNCA < está ordenada! Ou seja, se você quer buscar algo, precisa vasculhar a árvore inteira!
typedef struct noArv{
 int info;
 struct noArv *esq;
 struct noArv *dir;
}NoArv;
Essa é a representação da struct de >Qualquer< árvore! (Seja Árvore Binária ou Árvore Binária de Busca que veremos no próximo resumo) 
O >>ÚNICO<< detalhe que pode variar é o tipo da informação que ela armazena. (Nome, média, etc)
---------------------------------------//------------------------------------------
- Funções básicas de árvore binária:
OBS: Essas funções não costumam ser cobradas em prova, mas no mínimo entenda como cada uma funciona!
 
- Função pra criar uma árvore vazia:
NoArv * arv_criaVazia (){
 return NULL;
}
OBS: Se o enunciado não falar nada, é muito mais simples ao invés de chamar a função, declarar uma variável e atribuir o NULL manualmente! 
EX: NoArv *a = NULL;
 
---------------------------------------//-----------------------------------------
- Função pra criar uma nova árvore: (Inserir um novo elemento)
NoArv * arv_cria (int info, NoArv * esq, NoArv * dir){ 
 NoArv * novo = (NoArv*) malloc (sizeof(NoArv));
 if(!novo) return NULL;
 novo->info = info;
 novo->esq = esq;
 novo->dir = dir;
 return novo;
}
OBS: Primeiro passo é alocar dinamicamente um novo Nó e depois atribuir os valores recebidos por parâmetro.
Lembrando que antes de inserir o primeiro elemento, precisamos obrigatoriamente criar a árvore vazia! (Inicializando com NULL)
---------------------------------------//-----------------------------------------
- Função que libera a árvore:
void arv_libera(NoArv *a){
 if(!a) return; //Não faz sentido liberar o que não existe, certo? :D
 
 arv_libera(a->esq);
 arv_libera(a->dir);
 free(a);
}
Primeiro libera o Nó da esquerda, depois o da direita e >>SOMENTE<< por último a raíz! A estratégia aqui é primeiro liberar os filhos e somente por último a raíz, pois se liberarmos a raíz antes, vamos perder acesso à seus filhos!
OBS: Essa forma de percorrer a árvore é chamada: Pós ordem. (Nó esquerdo, Nó direito e por último a Raíz)
-------------------------------------//-------------------------------------------
- Função que verifica se a árvore está vazia:
int arv_vazia (NoArv *a){
 return (a == NULL); 
}
OBS: Se a árvore estiver vazia retorna 1 (verdadeiro), senão retorna 0 (Falso)
-------------------------------------//---------------------------------------------
- Função que imprime todos os dados da árvore:
void arv_imprime (NoArv *a){
 if(!a) return; //Se não tem árvore, vai imprimir o que? :) 
 
 arv_imprime(a->esq);
 printf("%d\n", a->info);
 arv_imprime(a->dir);
}
OBS: Esse modo de percorrer a árvore é chamado: Simétrico.
Primeiro percorre o Nó da esquerda, depois a raíz e só por último o Nó da direita.
Observou que nas funções arv_libera e arv_imprime a forma mais tranquila de resolver é usando recursão? 
Tenta imaginar uma solução iterativa que percorra a árvore inteira e cobrindo todas as possibilidades sempre. Lembrando que cada Nó pode ter até no máximo 2 filhos, então isso complica bastante, por isso o recomendado é usar sempre recursão em árvore!
E >>SEMPRE<< que usamos recursão precisamos de um >> Caso Base << pra parar a recursão. Em árvore o caso base genérico é quando a árvore é vazia! Pois dessa forma, a recursão vai percorrendo os Nós da árvore e assim que ultrapassar um Nó Folha vai parar e ir "voltando"! (Os ponteiros de uma Folha sempre apontam pra NULL!)
if(!a) return;
OBS: Dependendo do que está sendo pedido no enunciado, a quantidade de casos base pode aumentar!
 
---------------------------------------//-----------------------------------------
- Funções que podem ser cobradas em Prova: (Ou parecidas) 
1) Função que conta e retorna a quantidade de folhas de uma árvore:
int contaFolhas (NoArv* a){
 if(!a) return 0; //Se não tem árvore quantas folhas temos no total? zero!
 if(!a->esq && !a->dir) return 1; 
 
 return contaFolhas(a->esq) + contaFolhas(a->dir);
}
Dessa vez temos mais um Caso Base! Se o Nó que estamos analisando for uma Folha, ou seja, um Nó em que ambos ponteiros da esquerda e direita apontam pra NULL! Encontramos quantas folhas? Uma! Por isso encerramos essa instância da função retornando 1! 
OBS: Lembrando que é o mesmo que escrever if(a->esq == NULL && a->dir == NULL)
Nunca esqueça que a recursão é basicamente várias chamadas da mesma função, ou seja, várias instâncias da mesma função, sendo que obrigatoriamente >>TODAS<< precisam retornar 0 (Se ultrapassar o Nó folha e chegar numa Sub árvore vazia) >> OU << retornar 1 (Se encontrar uma folha!) 
O último passo é usar a recursão pra percorrer a árvore inteira (Lado esquerdo e direito) e ao mesmo tempo ir somando a quantidade de folhas.
E à medida que a recursão chega no caso base e vai "voltando", cada instância da função retorna um desses dois valores pra quem chamou e o retorno de cada uma está sendo somado no total de folhas!
-------------------------------------//-------------------------------------------
2) Função que verifica se algum Nó da árvore possui um determinado valor: 
int arv_pertence (NoArv *a, int val){
 if(!a) return 0;
 if(a->info == val) return 1;
 return (arv_pertence(a->esq, val) || arv_pertence (a->dir, val));
}
Como vamos adivinhar se o valor está no lado esquerdo ou direito da árvore? 
Não tem como! Por isso precisamos percorrer ambos os lados, pois se caso o lado esquerdo >>OU<<
o lado direito retornar 1 (Encontrou o valor!) podemos encerrar a função.
Outra solução seria: 
int arv_pertence (NoArv *a, int val){
 if(!a) return 0;
 if(a->info == val) return 1;
 if(arv_pertence(a->esq, val)) return 1;
 return arv_pertence (a->dir, val);
}
OBS: Essas duas últimas linhas substitui o uso do > || < ! Mas eu ainda acho mais prático fazer da outra forma.
OBS: Lembra eu falando que é um erro fatal usar vários ifs seguidos?(Resumos Prog 1)
Pois é, a >>ÚNICA<< exceção é quando em cada uma das condições, a função é encerrada! Dessa forma, se caso a primeira condição 'if' for verdadeira, >>NÃO<< tem risco das outras serem verificadas!
E nas funções de árvore isso é o que mais tem, condições que encerram a função ou chamam a mesma função na recursão, então sem problemas! :)
 
--------------------------------------//-------------------------------------------
3) Função que retorna a quantidade total de Nós da árvore:
int contaNos (NoArv *a){
 if(!a) return 0;
 return 1 + contaNos(a->esq) + contaNos(a->dir);
}
OBS: A única restrição aqui é se a árvore estiver vazia! Tirando isso, todos os outros Nós são válidos! Por isso precisamos contar 1 + os Nós da esquerda + os Nós da direita.
---------------------------------------//------------------------------------------
4) Função que retorna o maior valor encontrado na árvore:
int arvMaior(NoArv *a) {
	int v1, v2, v3;
	if(!a) return -1;
	v1 = a->info;
	v2 = arvMaior(a->esq);
	v3 = arvMaior(a->dir);
	return compara (v1, v2, v3);
}
Precisamos de três variáveis auxiliares pra ir armazenando o valor da raíz, Sub árvore esquerda e direita e ao mesmo tempo fazer uma comparação entre eles pra ver quem possui o maior valor! 
OBS: O recomendado é usar uma função auxiliar nas comparações, mas também é possível 
fazer as mesmas comparações dentro da função principal.
Função Auxiliar:
int compara (int v1, int v2, int v3){
	if(v1 > v2 && v1 > v3) return v1;
	else if(v2 > v3) return v2;
	return v3;
}
---------------------------------------//------------------------------------------
5) Função que verifica se duas árvores são iguais: 
OBS: Duas árvores só serão iguais se tiverem a >> MESMA << estrutura hierárquica e armazenem a mesma informação em cada Nó!
int arvIguais(NoArv *a1, NoArv *a2){
	if(!a1 && a2 || a1 && !a2) return 0;
	if(!a1 && !a2) return 1;
	if(a1->info != a2->info) return 0;
	return arvIguais(a1->esq, a2->esq) && arvIguais(a1->dir, a2->dir);
}
A estratégia é pensar assim: "O que faz uma árvore ser diferente da outra?"
A primeira coisa que pensamos é a informação de cada uma sendo diferente. 
Sim, essa é uma ótima condição! Mas não podemos esquecer que uma árvore vazia não armazena nada!
Então >>ANTES<< de tudo precisamos verificar se a primeira árvore é vazia > E < a segunda não > OU < o contrário !
"Tio, posso comparar as informações agora???" 
Calma! Que pressa é essa? Haha
E se ambas árvores estiverem vazias? :D
Somente depois de verificar isso que vamos ter certeza que as duas árvores >NÃO< são vazias e podemos finalmente comparar as informações!
E por fim, elas só serão iguais se >>TODOS<< os Nós do lado esquerdo > && < direito forem iguais! Ou seja, se um dos lados retornar zero é porque são diferentes!
---------------------------------------//------------------------------------------
6) Função que retorna a altura da árvore: 
**********************************************************************************
Regra Importante:
- A raíz principal possui altura zero!
- Uma árvore vazia possui altura -1!
- Altura de uma árvore é o >> MAIOR << caminho que leva da raíz principal até uma folha!
EX: http://equipe.nce.ufrj.br/adriano/c/imagens/arvbin.gif
OBS: A altura dessa árvore da imagem é 3! Pois tanto H e I possuem nível 3! E essa é a maior distância da raíz até uma folha!
***********************************************************************************
int altura (NoArv *a){
 if(!a) return -1;
 return 1 + max(altura(a->esq), altura (a->dir));
}
OBS: Precisamos descobrir a maior distância do lado esquerdo da árvore, assim como do lado direito e ao mesmo tempo ir comparando qual dos lados possui maior altura! 
A melhor forma de fazer essas comparações é através de uma função auxiliar! 
Função Auxiliar: 
int max (a, b){
 if(a > b) return a;
 return b;
}
Dessa forma, assim que a recursão "voltar" para a raíz, tanto pela esquerda quanto pela direita, a última comparação da árvore da imagem seria entre a altura 2 (Maior altura do lado esquerdo) com o 3 (Maior altura do lado direito)
---------------------------------------//------------------------------------------
7) Função que recebe como parâmetro uma altura e testa se a altura da árvore é maior que a do parâmetro: 
int arvAlturaMaior(NoArv *a, int altura) {
	if(altura < -1) return 1; 
	if(!a) return 0;
	if(arvAlturaMaior(a->esq, altura - 1) || arvAlturaMaior(a->dir, altura-1)) 
		return 1;
	return 0;
Sabemos que uma árvore vazia tem altura - 1, certo? :)
Vamos usar de novo a árvore da imagem como exemplo: 
http://equipe.nce.ufrj.br/adriano/c/imagens/arvbin.gif
A estratégia aqui é ir decrementando o parâmetro da altura na recursão!
Imagina que recebemos como parâmetro a altura 2: 
Então no Nó 'A' a altura é 2, Nó 'B' será 1, Nó 'D' será 0! Mas como 'D' é uma folha e toda folha aponta pra NULL (Árvore Vazia) e o Caso Base de toda recursão em árvore é quando chegamos na árvore vazia, a altura será exatamente -1 quando passar da folha 'D' ou 'E'! 
Após vasculhar o lado esquerdo da árvore não vamos encontrar nenhuma altura maior que a do parâmetro. Mas pelo lado direito, seguindo o percurso 'A' 'C' 'F' 'H' e 'NULL' a altura será -2! 
Ou seja, vamos diminuindo a altura recebida pelo parâmetro à medida que percorremos a árvore e se a altura ficar >>MENOR<< que -1 quer dizer que a altura da árvore é >>MAIOR<< que a recebida por parâmetro!
OBS: Pela primeira vez >>NÃO<< podemos colocar a condição if(!a) no começo! Pois primeiro precisamos verificar a altura >>ANTES<< de deixar a recursão "voltar"!
--------------------------------------//------------------------------------------
8) Função que busca um Nó com o valor x e se achar, retorna o Nível (Altura) desse Nó na árvore:
OBS: A função só recebe como parâmetro a árvore e o valor!
int arvore_nivel (NoArv *a, int x){
 if(!a) return -1;
 return contaNivel(a, x, 0);
}
Em primeiro lugar, como vamos retornar algo que não temos? (Dessa vez não recebemos a altura como parâmetro!)
É aí é que tá! Sempre, mas >>sempre<< que não tivermos algum parâmetro que seria importante em funções de árvore, é só usarmos uma função auxiliar para ""criar"" o parâmetro que estiver faltando!
Nesse trecho aqui: return contaNivel(a, x, 0);
Como a árvore não é vazia, pois já testamos no if(!a) , com certeza absoluta total, estamos na raíz da árvore que possui altura 0! Dessa forma, já podemos enviar esse zero como parâmetro pra representar o nível da árvore na função auxiliar!
Função auxiliar:
int contaNivel (NoArv *a, int x, int nivel){ 
 int h;
 if(!a) return -1; 
 if(a->info == x) return nivel; //Se achar, retorna o nível.
 h = contaNivel(a->esq, x, nivel+1);
 if(h != -1) return h;
 return contaNivel(a->dir, x, nivel+1);
}
Como o valor que procuramos pode estar no lado esquerdo ou direito da árvore, precisamos percorrer cada lado da árvore e ir incrementando a altura à medida que avançamos na árvore! 
OBS: Dessa vez precisamos incrementar a altura pois queremos achar um Nó específico! Na função anterior foi pedido pra verificar uma altura recebida, então não ia adiantar nada incrementar!
Como esse tipo de árvore >>NÃO<< é ordenada e pode ser necessário percorrer os dois lados pra achar o Nó, precisamos de uma variável auxiliar pra armazenar
o resultado do lado esquerdo e >>SÓ<< percorremos o lado direito se a variável 'h' for igual a -1! (Alcançou o NULL/Árvore Vazia, Não achou!)
Tirando isso é porque achamos no lado esquerdo e já podemos retornar a variável 'h' com o resultado da altura!
 
---------------------------------------//------------------------------------------
De todas essas funções, eu acho difícil cobrarem a número 7 e 8, mas as outras têm grandes chances! Levando em conta que na P3 de 2014.2 caiu algo parecido com as primeiras funções, envolvendo Folha e altura!
OBS: A notícia boa é que em nenhuma prova até então foi cobrado pra criar a árvore do zero, inserir elementos, etc
Faz sentido né? Eu não mencionei nenhuma Main nesse resumo! :)
Só costumam pedir funções mesmo, então se você leu tudo até aqui e mesmo assim não entendeu ou você simplesmente pulou o resumo inteiro só pra ver o que tinha escrito no final...Recomendo que você decore o máximo de funções possíveis! :D