Baixe o app para aproveitar ainda mais
Prévia do material em texto
Estrutura de Dados AULA 7 Árvores Estrutura de Dados UNIP - Ciência da Computação e Sistemas de Informação • A estrutura de dados de árvores é bastante utilizada quando um ou mais dos seguintes itens é importante: acesso direto e seqüencial eficientes; facilidade de inserção e remoção de elementos; boa taxa de utilização de memória; e utilização de memória primária e secundária. • As árvores são desenvolvidas utilizando-se os conceitos da lista ligada e recursão. Árvores • A árvore é uma estrutura de dados bidimensional, não linear, utilizada na programação de computadores que se compõem de nós e arcos. • Essas árvores são representadas de cima para baixo com a raiz no topo e as folhas na base, diferente das árvores naturais. • A raiz é um nó que não possui pai, ou seja, outros nós acima dele e as folhas são nós que não possuem filhos, ou seja, nós abaixo delas, ou melhor, só possuem filhos nulos Árvores • Podemos dizer que, de modo geral, uma árvore possui as seguintes características: – nó raiz - é o primeiro nó da árvore e que fica acima de qualquer outro nó. Todos os outros nós são descendentes deste nó. Existe somente um nó raiz em qualquer estrutura de árvore; – nó folha - é o último nó da árvore e, por isso, ele não possui descendentes. Pode existir mais do que uma nó folha; – nó interior - é o nó que está no interior da árvore. Este nó possui descendentes e ascendentes e não pode ser o nó raiz e nem o nó folha; – trajetória - é o número de nós que possui entre um nó e outro; – grau do nó - é o número de descendentes que um nó possui. Também pode ser definido como o número de subárvores que um nó possui; – altura da árvore - é o número máximo de níveis que podem ter os nós da árvore; e – altura do nó - é o número máximo de níveis que podem ter os descendentes desse nó, inclusive com este nó. Árvores • Uma árvore binária pode estar vazia ou pode ser composta de três partes: o nó raiz, a subárvore à direita do nó raiz e a subárvore à esquerda do nó raiz. Essas partes também são árvores binárias. Uma sub árvore binária também pode estar vazia. Cada elemento da árvore binária é o que chamamos de nó e cada ligação de um nó para outro é o que chamamos de arco. Árvores Binárias • Para exemplificar o funcionamento de uma árvore binária, vamos representar uma árvore binária de letras, de acordo com a regra (recursiva): "todo elemento à esquerda é menor que a raiz, todo elemento à direita é maior ou igual à raiz". • Uma árvore binária com essa propriedade é chamada árvore de busca binária. Árvores Binárias • Inicialmente, esta árvore binária está vazia, ou seja, não existe elementos na árvore binária, portanto, a raiz da árvore binária é nula, conforme mostra a figura abaixo: Árvores Binárias • Vamos, então, inserir a letra E na árvore binária, em seguida inserir a letra A, depois a letra U, e, por último, a letra O, conforme a seqüência abaixo. • Perceba que o tamanho da árvore binária muda, dependendo do nível em que a letra é inserida: Árvores Binárias • Se quisermos remover um elemento da árvore binária, podemos remover qualquer elemento que esteja na árvore binária, por exemplo, vamos remover a letra U, observando a figura abaixo: Árvores Binárias • Uma propriedade fundamental de qualquer árvore binária é a de que existe um único caminho de sua raiz para qualquer nó. • Assim, podemos considerar que a altura de uma árvore binária é o comprimento do caminho mais longo que pode ter determinada árvore binária. Árvores Binárias • Assim, por exemplo, uma árvore binária com um único nó, a raiz, tem altura igual a zero; uma árvore binária com dois nós, um nó raiz e um nó folha, tem altura igual a 1; e assim por diante. A árvore binária da figura abaixo tem altura igual a 3. Árvores Binárias • Podemos separar uma árvore binária em níveis. O nível zero é o nível no qual se encontra o nó raiz. O nível 1 é o nível no qual estão os nós abaixo do nó raiz e assim por diante, conforme mostra a figura abaixo. A Árvore Binária Completa e o seu Número de Nós • Uma árvore binária é considerada completa se todo nó possuir uma subárvore binária à esquerda e outra à direita, com exceção de todos os nós folhas, que devem estar no mesmo nível. • Observando a figura perceba que, no nível 1, a árvore binária possui 2 = 21 nós, no nível 2 a árvore binária possui 4 = 22 nós, no nível 3 a árvore binária possui 8 = 23 nós, e assim por diante, até que, no nível n, a árvore binária possua 2n nós. Assim, considerando também o nó raiz, uma árvore binária completa possui 20 + 21 + 22 + 23 + ... + 2n nós. A Árvore Binária Completa e o seu Número de Nós • inserir - a operação de inserir insere um elemento na árvore binária; • remover - a operação de remover exclui um elemento da árvore binária. • retornaRaiz – a operação para devolver o elemento da raiz. Operações em Árvores Binárias Métodos em Árvores Binárias class BIntNo{ int valor; BIntNo esq, dir; BIntNo(int novoValor){ valor = novoValor; } } class ArvoreBinaria { private BIntNo raiz; public int retornaRaiz () { return raiz.valor; } Métodos em Árvores Binárias private BIntNo inserir(BIntNo arvore, int novoNo) { if (arvore == null) { return new BIntNo(novoNo); } else { if (novoNo < arvore.valor) { arvore.esq = inserir(arvore.esq, novoNo); } else { arvore.dir = inserir(arvore.dir, novoNo); } } return arvore; } public void inserir(int novoValor) { raiz = inserir(raiz, novoValor); } Métodos em Árvores Binárias public void excluirNo(int item) { BIntNo tempNo, pai, filho, temp; tempNo = raiz; pai = null; filho = raiz; while (tempNo != null && tempNo.valor != item) { pai = tempNo; if (item < tempNo.valor) { tempNo = tempNo.esq; } else { tempNo = tempNo.dir; } } Métodos em Árvores Binárias if (tempNo == null) { System.out.println("item não localizado!"); } if (pai == null) { // significa que estamos excluindo a raiz if (tempNo.dir == null) { Raiz = tempNo.esq; } else { if (tempNo.esq == null) { Raiz = tempNo.dir; } else { for (temp = tempNo, filho = tempNo.esq; filho.dir != null; temp = filho, filho = filho.dir); if (filho != tempNo.esq) { temp.dir = filho.esq; filho.esq = Raiz.esq; } filho.dir = Raiz.dir; Raiz = filho; } } Métodos em Árvores Binárias } else { // não estamos excluindo a raiz if (tempNo.dir == null) { if (pai.esq == tempNo) { pai.esq = tempNo.esq; } else { pai.dir = tempNo.esq; } } else { if (tempNo == null) { if (pai.esq == tempNo) { pai.esq = tempNo.dir; } else { pai.dir = tempNo.dir; } } else { Métodos em Árvores Binárias } else { for (temp = tempNo, filho = tempNo.esq; filho.dir != null; temp = filho, filho = filho.dir); if (filho != tempNo.esq) { temp.dir = filho.esq; filho.esq = tempNo.esq; } filho.dir = tempNo.dir; if (pai.esq == tempNo) { pai.esq = filho; } else { pai.dir = filho; } } } } } • Exercício: inserir os seguintes elementos em uma árvore binária: • 10, 20, 8, 2, 1, 15, 30, 18, 9, 3, 6, 5, 4 Árvores Binárias 10 20 15 30 18 8 92 3 6 5 4 1 Árvores Binárias • Exercício: remover o elemento 8 da árvore anterior Árvores Binárias • Outra operação comum é percorrer uma árvore binária • Uma árvore não tem uma ordem natural a ser percorrida. Desse modo, alguns métodos de percorrer são definidos, e iremos analisar três desses métodos. Todos os métodos sãopercorridos de forma recursiva, de modo que percorrer uma árvore binária envolve visitar a raiz e percorrer suas subárvores esquerda e direita. A diferença entre os métodos é a ordem na qual essas operações são efetuadas Operações em Árvores Binárias • Pré-ordem (ou percurso em profundidade) Visitamos (e processamos) a raiz Percorremos a subárvore esquerda em pré-ordem Percorremos a subárvore direita em pré-ordem • Em ordem (ou ordem simétrica) Percorremos a subárvore esquerda em ordem simétrica Visitamos (e processamos) a raiz Percorremos a subárvore direita em ordem simétrica • Pós-ordem Percorremos a subárvore esquerda em pós-ordem Percorremos a subárvore direita em pós-ordem Visitamos (e processamos) a raiz Operações em Árvores Binárias • Exercício: implementar os métodos abaixo – public void imprimePreOrdem(); – public void imprimeEmOrdem(); – public void imprimePosOrdem(); Árvores Binárias public void imprimePreOrdem() { imprimePreOrdem(Raiz); System.out.println(); } private void imprimePreOrdem(BIntNo no) { if (no != null) { System.out.print(no.valor + " "); imprimePreOrdem(no.esq); imprimePreOrdem(no.dir); } } Árvores Binárias public void imprimeEmOrdem() { imprimeEmOrdem(Raiz); System.out.println(); } private void imprimeEmOrdem(BIntNo no) { if (no != null) { imprimeEmOrdem(no.esq); System.out.print(no.valor + " "); imprimeEmOrdem(no.dir); } } Árvores Binárias public void imprimePosOrdem() { imprimePosOrdem(Raiz); System.out.println(); } private void imprimePosOrdem(BIntNo no) { if (no != null) { imprimePosOrdem(no.esq); imprimePosOrdem(no.dir); System.out.print(no.valor + " "); } } Árvores Binárias • Exercício: percorrer a árvore abaixo em – Pré-Ordem – Em Ordem – Pós Ordem Árvores Binárias 10 20 15 30 18 8 92 3 6 5 4 1 • Exercício: percorrer a árvore abaixo em – Pré-Ordem: 10 8 2 1 3 6 5 4 9 20 15 18 30 – Em Ordem: 1 2 3 4 5 6 8 9 10 15 18 20 30 – Pós Ordem: 1 4 5 6 3 2 9 8 18 15 30 20 10 Árvores Binárias Solução
Compartilhar