Baixe Fundamentos Mot e outras Notas de aula em PDF para Engenharia Telemática, somente na Docsity! 1 Curso Superior de Tecnologia em Telemática Programação e Estruturas de Dados Árvores – Fundamentos e Implementações Copyright©2010 Prof. César Rocha cesarocha@ifpb.edu.br 2 Objetivos § Explorar os conceitos fundamentais acerca do uso de árvores utilizando a linguagem C § Organização e implementação, características, vantagens, desvantagens, regras de utilização, operações básicas e algoritmos de implementação § Será abordada ainda uma implementação de árvore bastante conhecida: árvore binária § Este módulo será utilizado como referência na entrega dos futuros projetos § Implementação das estruturas e algoritmos, criação das bibliotecas e práticas de laboratório 5 Conceitos § Uma árvore consiste de uma estrutura não-linear que representa uma relação de hierarquia § Uma árvore é composta por um conjunto de nós § Existe um nó R, chamado de nó raiz § Este nó contém zero ou mais sub-árvores, cujas raízes são ligadas diretamente à R § Os nós raízes das sub-árvores são ditos filhos do nó R § Nós que não têm filhos são chamados de folhas § É bastante comum desenhar as árvores com o nó raiz para cima e os nós folhas para baixo 6 Graficamente § Representamos explicitamente a direção dos ponteiros, na figura acima: § Eles apontam sempre do pai para os filhos § Diferente do exemplo acima, podemos ter nós contendo mais de duas sub-árvores Raiz BA C D F Sub-árvores do nó RAIZ- s IFilho do nó Ail Nó RAIZ ITArvore *a Nós folhasls f s 7 Grau § O número de sub-árvores presentes em um determinado nó indicará o Grau desse nó § Qual o grau de cada nó mostrado anteriormente? § Conceito de Grau Máximo: § número máximo de sub-árvores que o nó pode ser raiz § Nós que não tem grau, são chamados de nós folhas § Para identificar os nós de uma estrutura, usamos a relação de hierarquia existente em uma árvore genealógica § Nó Filho, Nó pai, Nó neto, Nó irmão, ... 10 § Em uma árvore binária, todos os seus nós possuem, no máximo, duas sub-árvores § Cada nó pode ter zero, um ou dois filhos. § E ainda, é uma árvore de grau máximo igual a dois. § As duas sub-árvores possíveis em cada nó são também denominadas de: § sub-árvore esquerda (sae). § sub-árvore direita (sad). § Árvore binária completa § Árvore em que cada nó possui dois filhos (exceto os nós folhas, é claro). Conceitos Nó sadsae 11 Graficamente § Observe: § Onde: Nó 10 30 60 50 20Nível 1 Nível 2 Nível 3 40 ... ... Raízes das sub-árvores Nós folhas (grau = 0) DireitaEsquerda Grau máximo = 2 12 Árvores binárias Pense um pouco... § O que você acha que seria necessário para implementar uma biblioteca de um novo TAD que representasse uma árvore binária? uma estrutura que guarde: dado e ponteiros dois apontadores indicando: esquerda e a direita do nó /* arvorebin.h */ Inicialização da árvore Criar nó raiz Árvore vazia Imprimir a árvore Inserir filho esquerdo Inserir filho direito Remover um determinado nó / i . / i i li i i i i i i fil i fil i i i /* estruturação */ typedef struct arv { int info; struct arv *esq; struct arv *dir; }no; / / f i i f ; ; i ; ; 15 Tipos de percursos § Observe: § Percursos: A B D E G CNível 1 Nível 2 Nível 3 F Pré-ordem: A, B, D, E, C, F, G DireitaEsquerda Grau máximo = 2 In-ordem: D, E, B, A, F, C, G Pós-ordem: E, D, B, F, G, C, A 16 Algoritmos em C § O que deverá ser feito pelo aluno: § Escolha e instalação do ambiente a ser trabalhado no laboratório § Modelagem deste TAD (dados e operações) § Implementação dos algoritmos de operações básicas vistos em sala de aula na linguagem C § Utilização das regras de modelagem vistas no módulo anterior (criação de bibliotecas) e modularização § Implantação de código legível e bem documentado § Nomes de variáveis condizentes com o problema § Prática de laboratório 17 Para um bom aproveitamento: § O aluno deve identificar a relação entre TAD (biblioteca e modularização) com a implementação da fila no código! § Resolva todas as questões da prática de laboratório de árvores § Procure o professor ou monitor da disciplina e questione conceitos, listas, etc. § Não deixe para codificar tudo e acumular assunto para a primeira avaliação. § Este é apenas um dos assuntos abordados na prova!