Arvores Binarias - Definição, Percursos e Representação

ESTRUTURA DE DADOS II 60 HORAS PROF JULIANO RATUSZNEI EMAIL JULIANORATUSZNEIUNICIDEDUBR 2 EMENTA Árvores Binárias Definições Percursos em árvores binárias e representação computacional ÁRVORE BINÁRIA Conjunto finito T de zero ou mais nós nodos tal que Se número de nós é maior do que zero Existe um nó denominado raiz da árvore Os demais nós formam 2 conjuntos disjuntos S1 S2 subárvore da esquerda e subárvore da direita onde cada um destes é uma árvore binária Se número de nós é igual a zero Árvore vazia 3 4 ÁRVORE BINÁRIA Raiz Subárvore da direita Subárvore da esquerda Sub Arvores são arvores binárias 5 ARVORE BINÁRIA Raiz Subárvore da direita Subárvore da esquerda Sub Arvores são arvores binárias TIPOS DE ÁRVORES BINÁRIAS Estritamente Binária 0 ou 2 filhos Binária Completa Subárvores vazias apenas no último ou penúltimo nível Binária Cheia Subárvores vazias somente no último nível Zigue Zague Nós internos com 1 subárvore vazia 7 TIPOS DE ÁRVORES BINÁRIAS Qual delas possui altura máxima Qual delas possui altura mínima ESTRUTURA DE DADO ÁRVORE BINÁRIA Árvores binárias são uma das árvores mais usadas em computação 8 abc de 9 REPRESENTAÇÃO DA ÁRVORES BINÁRIAS 10 REPRESENTAÇÃO DA ÁRVORES BINÁRIAS 11 CAMINHAMENTO EM ÁRVORE BINÁRIA Caminhamentos em árvore são formas de visitarmos todos os nodos de uma árvore em uma ordem prédefinida Existem três tipos de caminhamentos básicos préordem em ordem e pósordem Ordem Visita filho da esquerda Visita o nodo corrente Visita filho da direita 10 20 3040506070 CAMINHAMENTO EM ÁRVORE BINÁRIA implementar o caminhamento em ordem 12 Ordem Visita filho da esquerda Visita o nodo corrente Visita filho da direita 13 CAMINHAMENTO EM ÁRVORE BINÁRIA Implementar o caminhamento préordem e pósordem Préordem Visita o nodo corrente Visita filho da esquerda Visita filho da direita Pósordem Visita filho da esquerda Visita filho da direita Visita o nodo corrente 40 20 10 30 60 50 70 10 30 20 50 7060 40 14 CAMINHAMENTO EM ÁRVORE BINÁRIA Largura Visita é feita por nível da esquerda para a direita Profundidade Préordem ABDECFG 15 CAMINHAMENTO EM ÁRVORE BINÁRIA Realize os caminhamentos em Pósordem Largura Tempo estimado 10 min 16 CAMINHAMENTO EM ÁRVORE BINÁRIA Realize os caminhamentos em Pósordem 83 120 100 150 230 200 130 Largura 130 100 200 83 120 150 230 ÁRVORE DE BUSCA BINÁRIA ÁRVORE DEVE ESTAR ORDENADA Iniciase pela raiz verificar se O valor buscado é igual a raiz encontrou Valor buscado diferente da raiz verificase é maior ou menor que o valor da raiz Menor vai para esquerda Maior vai para direita 17 18 ÁRVORE DE BUSCA BINÁRIA ÁRVORE DEVE ESTAR ORDENADA Inserindo valores em uma árvore binária ordenada 510 112 300 29 433 34 221 Qual o caminho para encontrar o valor 230 510112300221 não encontra Qual o caminho para encontrar o valor 446 510 112 300 433 não encontrou 510 112 300 29 433 34 221 19 ÁRVORE DE BUSCA BINÁRIA 510 112 300 29 433 34 100 20 ÁRVORE DE BUSCA BINÁRIA 510 112 300 29 433 34 100 10 0 Não é uma árvore de busca binária 21 ÁRVORE DE BUSCA BINÁRIA Digamos que a árvore de busca binária tenha percorrido o seguinte caminho para achar o valor 587 352 366 371 594 595 589 587 É um árvore de busca binária Como verificar se é uma árvore de busca binária ÁRVORE DE BUSCA BINÁRIA Digamos que a árvore de busca binária tenha percorrido o seguinte caminho para achar o valor 587 352 366 371 594 595 589 587 É um árvore de busca binária Como verificar se é uma árvore de busca binária 352 366 371 594 587 589 595 22 587 23 INSERÇÃO EM ÁRVORES BINÁRIAS DE PESQUISA Como codificar as regras de árvore binária em um procedimento de inserção de modo que as regras de árvore binária sejam aplicadas a cada nodo inserido Sem indicação explicitamente onde os nodos devem ficar Desafio construir uma função para inserir nodos em uma árvore binária de pesquisa encontrar o ponto onde cada nodo deve ser inserido 24 INSERÇÃO EM ÁRVORES BINÁRIAS DE PESQUISA Para encontrar o ponto de inserção de um nodo em uma árvore binária de pesquisa precisamos observar as propriedades dessas árvores dado um nodo qualquer nodos menores do que ele são inseridos à sua esquerda nodos maiores do que ele são inseridos à sua direita Desafio como transformar essas ideias em código 25 INSERÇÃO EM ÁRVORES BINÁRIAS DE PESQUISA 26 ALGORITMO DE BUSCAS EM ÁRVORES BINÁRIAS DE PESQUISA O algoritmo de busca em árvores binárias de pesquisa pode ser dividido em três casos A chave procurada está na raiz da árvore Nesse caso simplesmente retornamos a raiz da árvore como resultado da busca A chave procurada é menor que a chave do nodo raiz Nesse caso precisamos procurar pela chave somente na subárvore esquerda A chave procurada é maior que a chave do nodo raiz Nesse caso precisamos procurar pela chave somente na subárvore direita A implementação da ideia acima assim como o tratamento do caso em que o nodo não está presente na árvore 27 ALGORITMO DE BUSCAS EM ÁRVORES BINÁRIAS DE PESQUISA ÁRVORES BINÁRIAS DE PESQUISA Apesar de alguns conceitos de árvores parecerem complexos somos capazes de implementálos com relativa facilidade Isso se deve ao fato de que a maioria dos conceitos de árvores possuírem uma natureza inerentemente recursiva A recursividade acaba sendo natural e simples Portanto sempre que você se deparar com um problema envolvendo árvores tente pensar em uma solução recursiva antes de mais nada 28