Aula 3

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

3 - Arvores binarias
	A estrutura de dados arvore é um TAD no qual os dados são organizados de forma hierarquica. Os elementos de uma arvore são denominados "nós", sendo que cada nó possui um nó pai e zero ou mais nós filhos. O nó do topo da arvore é denominado "raiz", ocupa a posição mais elevada da arvore e não possui um nó pai.
	• Nós que são filhos do mesmo pai, são irmãos
	• Nós que não tem filhos são denominados "externos" ou "folhas".
	• Nós relacionados como pai e filho pertencentes a uma arvore determinam uma aresta.
	• Um caminho em uma arvore é uma sequencia de nós, na qual quaisquer dois nós formam uma aresta.
	• Quando existe uma ordem entre filhos dos nós de uma arvore, esta é denominada "ordenada".
	Operações para manipulação e acesso a esses elementos:
	• Operação raiz: Retorna a raiz da arvore. No caso de uma arvore vazia, retornará o valor nulo.
	• Operação pai de um nó: Retorna o pai desse nó. Se o nó for a raiz, resultará em erro.
	• Operação filhos de um nó: Retorna um conjunto de nós formado por todos os filhos desse nó.
	• Operação para teste se um nó é folha: Verifica se o nó é uma folha, ou seja, não tem filhos.
	• Operação para teste se um nó é interno: Verifica se o nó é interno à arvore, ou seja, se possui filhos.
	• Operação tamanho: Retorna o numero de nós da arvore.
	• Operação para teste se é vazio: Verifica se uma arvore esta vazia, ou seja, não tem nós.
	A arvore binaria permite um maximo de dois filhos para cada nó.
3.1 - Elaboração de uma arvore binaria
	
	Uma arvore binaria apresenta as seguintes caracteristicas:
	• Deve ser ordenada; os filhos de um nó devem estar ordenados da esquerda para a direita.
	• Cada nó tem no maximo dois filhos, ou seja, zero, 1 ou 2
	• Cada um dos filhos é rotulado como filho da direita e filho da esquerda.
	
3.2 - Técnicas de varredura, altura e profundidade
	
	A profundidade de um determinado nó em uma arvore é o numero de ancestrais que esse nó possui. O calculo da profundidade de um nó qualquer da arvores pode ser obtido com algoritmos especificos de varredura dos nós da arvore.
	A altura de uma arvore é representada pelo numero de niveis da arvore. Uma arvore vazia apresenta altura igual a zero. Em uma arvore com apenas a raiz, a altura é 1. Assim como para a profundidade de um nó, o calculo da altura de uma arvore pode ser obtido com algoritmos especificos de varredura ou caminhamento.
	A forma sistematica de acessar todos os nós de uma arvore é denominada "caminhamento".
	A inspeção sistematica de todos os elementos de uma arvore pode ser realizada de duas maneiras basicas: 
	• No caminho pré-fixado, primeiramente, a raiz da arvore é visitada para a realização da inspeção, e, depois, as subárvores, representadas pelos filhos, são percorridas recursivamente.
	• No caminho pós-fixado, ocorre o oposto ao caminhamento pré-fixado. Primeiramente, são percorridas as subárvores recursivamente,e,depois, é inspecionada a raiz.