Baixe o app para aproveitar ainda mais
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
Compartilhar