UPE – Caruaru – Sistemas de Informação Disciplina: Estrutura de Dados e Arquivo Prof.: Paulemir G. Campos Árvores Binárias: Construção e Percursos 11/5/2015 EDA - Prof. Paulemir Campos 1 Árvores Binárias: Definições São estruturas de dados onde existe uma relação hierárquica entre seus elementos constituíntes, chamados nós; Há um nó principal, chamado raiz da árvore; A partir da raiz da árvore, cada nó pode ter no máximo dois nós, chamados filhos esquerdo e direito. 11/5/2015 EDA - Prof. Paulemir Campos 2 Árvores Binárias: Definições Por sua vez, os nós à esquerda do nó raiz constituem a Sub-Árvore Esquerda e os nós à direita do nó raiz formam a Sub-Árvore Direita; Contudo, a raiz de uma árvore binária e suas respectivas sub-árvores esquerda e direita devem formar sub-conjuntos finitos e disjuntos de nós. 11/5/2015 EDA - Prof. Paulemir Campos 3 Árvores Binárias: Exemplos Raiz da Árvore T Sub-Árvore Esquerda A B D E G 11/5/2015 Sub-Árvore Direita C H F I EDA - Prof. Paulemir Campos 4 Árvores Binárias: Exemplos Raiz da Árvore T2 Raiz da Árvore T1 A B Filho Esquerdo ou Sub-Árvore Esquerda de T1 11/5/2015 A T1 T2 B Note que as árvores binárias T1 e T2 são diferentes, pois, apesar de terem o mesmo conteúdo na raiz, o conteúdo de seus respectivos nós filhos direito e esquerdo são diferentes. EDA - Prof. Paulemir Campos Filho Direito ou Sub-Árvore Direita de T2 5 Árvores Binárias: Contra exemplos Exemplos de estruturas que não são árvores binárias. Sub-Árvore Esquerda B D G Sub-Árvore Direita A H Sub-Árvore Esquerda C E A F I B D G C E F Sub-Árvore Direita I 11/5/2015 EDA - Prof. Paulemir Campos 6 Árvores Binárias: Características Possuem um ponteiro para o nó raiz da árvore (alocação dinâmica); Cada nó pode ter até dois filhos; Raiz e Sub-Árvores Direita e Esquerda devem constituir conjuntos disjuntos; Em informática, crescem de cima para baixo, já que a raiz fica no topo (nível zero). 11/5/2015 EDA - Prof. Paulemir Campos 7 Árvores Binárias: Nós O grau de um nó representa o seu número de filhos; Ex.: Um nó de grau 2 indica que ele tem dois filhos. Tipos de nós: 11/5/2015 Folhas ou Externos – Não tem filhos. Não-Folhas ou Internos – Tem ao menos um filho. EDA - Prof. Paulemir Campos 8 Árvores Binárias: Profundidade A profundidade ou altura de uma árvore binária é determinada pelo seu maior nível. Nível 0 A B D G E H Nível 1 C F I Nível 2 Nível 3 A profundidade ou altura (h) da árvore binária acima é 3 (h=3). 11/5/2015 EDA - Prof. Paulemir Campos 9 Árvores Binárias: Tipos Árvore Estritamente Binária: Todo nó não-folha deve ter sub-árvores esquerda e direita não vazias. A B D F 11/5/2015 EDA - Prof. Paulemir Campos C E G 10 Árvores Binárias: Tipos Árvore Binária Completa: A É uma árvore estritamente binária em que todas as folhas estão no nível máximo da árvore. 11/5/2015 B D EDA - Prof. Paulemir Campos C E F G 11 Árvores Binárias: Tipos Árvore Binária Quase Completa: 1 – Todas as folhas estão no último ou penúltimo níveis; 2 – E, para cada nó com descendente direito no último nível, todos os descendentes esquerdos folhas também estiverem no último nível. 11/5/2015 A B D H C E F G I EDA - Prof. Paulemir Campos 12 Árvores Binárias Completas Cálculo do Número de Nós: O número de nós (n) é obtido com a fórmula abaixo, sendo fornecida a altura (h) da mesma. n2 11/5/2015 h 1 1 A B D C E F G Ex.: Na árvore acima de altura h=2, obtemos facilmente com a fórmula ao lado que o número de nós desta árvore binária completa é n=7. EDA - Prof. Paulemir Campos 13 Árvores Binárias Completas Cálculo da Altura: Sabendo-se o número de nós (n), pode-se com a fórmula abaixo obter-se a sua altura (h). A B D h log 11/5/2015 n 1 2 1 C E F G Ex.: Na árvore binária completa acima, cujo número de nós é n=7, obtemos com a fórmula ao lado que sua altura é h=2. EDA - Prof. Paulemir Campos 14 Árvores Binárias: Criação Definindo o tipo da estrutura: defina estrutura no { caracter ponteiro estrutura no } tArvore 11/5/2015 dado esquerdo, direito EDA - Prof. Paulemir Campos 15 Árvores Binárias: Criação Alocando memória dinamicamente ponteiro tArvore raiz raiz = aloque(tArvore) 11/5/2015 EDA - Prof. Paulemir Campos 16 Árvores Binárias: Criação Criando uma árvore binária: ponteiro tArvore CriaArvore(caracter novo){ ponteiro tArvore no no = aloque(tArvore) no->dado = novo no->esquerdo = NULL no->direito = NULL retorne no } 11/5/2015 EDA - Prof. Paulemir Campos 17 Árvores Binárias: Insere à Esquerda Insere_Esquerda(ponteiro tArvore raiz, caracter atual, caracter novo){ ponteiro tArvore folha se (raiz!=NULL){ se (raiz->dado==atual){ /* Encontrou o nó procurado */ se (raiz->esquerdo==NULL){ folha = CriaArvore(novo) raiz->esquerdo = folha } senão escreva(“Inserção inválida”) } senão { Insere_Esquerda(raiz->esquerdo, atual, novo) Insere_Esquerda(raiz->direito, atual, novo) } } } OBS.: Insere à direita é análogo a este procedimento. 11/5/2015 EDA - Prof. Paulemir Campos 18 Árvores Binárias: Percursos Principais formas de se percorrer uma árvore binária não vazia: Passeio Pré-Fixo Passeio Central Passeio Pós-Fixo 11/5/2015 EDA - Prof. Paulemir Campos 19 Árvores Binárias: Passeio Pré-Fixo (r-e-d) Efetua-se o procedimento recursivo, enquanto possível: Visita-se a raiz; Percorre-se a sub-árvore esquerda em ordem pré-fixa; Percorre-se a sub-árvore direita em ordem préfixa. 11/5/2015 EDA - Prof. Paulemir Campos 20 Árvores Binárias: Passeio Central (e-r-d) Efetua-se o procedimento recursivo, enquanto possível: Percorre-se a sub-árvore esquerda em ordem central; Visita-se a raiz; Percorre-se a sub-árvore direita em ordem central. 11/5/2015 EDA - Prof. Paulemir Campos 21 Árvores Binárias: Passeio Pós-Fixo (e-d-r) Efetua-se o procedimento recursivo, enquanto possível: Percorre-se a sub-árvore esquerda em ordem pós-fixa; Percorre-se a sub-árvore direita em ordem pós-fixa; Visita-se a raiz. 11/5/2015 EDA - Prof. Paulemir Campos 22 Árvores Binárias: Exemplos de Passeios A Pré-Fixo (r-e-d): ABDGCEHIF B C Central (e-r-d): DGBAHEICF D E F Pós-Fixo (e-d-r): GDBHIEFCA G 11/5/2015 H I EDA - Prof. Paulemir Campos 23 Referências Szwarcfiter, J. L.; Markenzon, L. Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC, 2a. ed., 1994. Veloso, P. et al. Estrutura de Dados. Rio de Janeiro: Editora Campus, 1996. 11/5/2015 EDA - Prof. Paulemir Campos 24