arvore

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (333 palavras )
  • Download(s) : 0
  • Publicado : 26 de agosto de 2013
Ler documento completo
Amostra do texto
Árvore, no contexto da programação e ciência da computação, é uma estrutura de dados que herda as características das topologias em árvore. Conceitualmente diferente das listasencadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica.
A Árvore é composta por 1(um) Elemento principal chamado Raiz, que possuiligações para outros Elementos, que são denominados de Ramos ou filhos. Estes ramos levam a outros elementos que também possuem outros ramos. O elemento que não possui ramos é conhecido como Folhae/ou Nó-terminal.
O número máximo de ramos em um elemento é chamado Ordem da Árvore. Uma árvore binária é aquela de ordem 2, i.e., em que cada elemento possui no máximo 2 ramos.
Uma dasoperações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso, também chamado de travessia da árvore, pode ser feito em pré-ordem (os filhos de um nó sãoprocessados após o nó) ou em pós-ordem (os filhos são processados antes do nó). Em árvores binárias é possível ainda fazer uma travessia em-Ordem, em que se processa o filho à esquerda, onó, e finalmente o filho à direita.
O algoritmo abaixo descreve uma travessia pré-ordem: PercursoPreordem(nó): Processa nó Para cada filho de nó (se houver) Executa recursivamentePercursoPreordem(filho)
Outra Operação, utilizada nas árvores de pesquisa é a travessia da Raiz até uma das Folhas. Essa operação tem um custo computacional proporcional ao número de níveis daárvore. O pior caso é a travessia de todos os elementos até a folha de nível mais baixo. Árvores balanceadas apresentam o melhor pior caso possível, para um certo número de Nós. O pior casoapresenta-se na árvore degenerada em que cada Nó possui exatamente Um filho, e a árvore tem o mesmo número de níveis que de Nós, assemelhando-se a uma lista ligada.
Ver também
tracking img