Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (698 palavras )
  • Download(s) : 0
  • Publicado : 28 de janeiro de 2013
Ler documento completo
Amostra do texto
Àrvores

São estruturas de dados adequadas para a representação de hierarquias. Uma árvore é composta por um conjunto de nós.
Existe um nó R, denominado raiz, que contém zero ou mais subárvores,cujas raízes são ligadas diretamente a R. A raiz se liga a um ou mais elementos, e cada um destes forma uma nova subárvore. Esses elementos são seus galhos ou filhos.

Fundamentos básicos:
◦ GRAU– número de subárvores de um nó;
◦ FOLHA – um nó que possui grau zero, ou seja
não possui subárvores;
◦ FILHOS – são as raízes das subárvores de um nó;
◦ Nó não terminal é um nó que nãoé uma folha
e é diferente da raiz;
◦ A altura de uma árvore é o comprimento do caminho mais longo da raiz até uma das folhas;
◦ Uma árvore nula tem altura 0;
◦ Todos os nós sãoacessíveis a partir da raiz;
◦ Existe um único caminho entre a raiz qualquer outro nó;

Formas de representação gráfica

Árvores Binárias

Árvore Binária: Uma árvore binária é uma árvore que pode sernula, ou então tem as seguintes características:
◦ Existe um nó especial denominado raiz;
◦ Nenhum nó tem grau superior a 2 (dois), isto é, nenhum nó tem mais de dois filhos;
◦Existe um “senso de posição”, ou seja, distingue-se entre uma subárvore esquerda e
uma subárvore direita.

Atravessamento (ou caminhamento) de árvore é a passagem de forma sistemática por cadaum de seus nós;
- Diferentes formas de percorrer os nós de uma árvore:
◦ Pré-ordem ou prefixa (busca em profundidade);
◦ Em ordem ou infixa (ordem central);
◦ Pós-ordem ou posfixa ;◦ Em nível.

Pré-ordem (prefixa)
◦ visitar a raiz;
◦ caminhar na subárvore à esquerda, segundo
este caminhamento;
◦ caminhar na subárvore à direita, segundo este
caminhamento.Atravessamento em ordem (infixa)
◦ caminhar na subárvore à esquerda, segundo este caminhamento;
◦ visitar a raiz;
◦ caminhar na subárvore à direita, segundo este caminhamento....
tracking img