estudante

Páginas: 9 (2008 palavras) Publicado: 18 de setembro de 2014
ESTRUTURA DE DADOS
ÁRVORES


Árvores
• utilizada em muitas aplicações
• modela uma hierarquia entre elementos
• árvore genealógica

• diagrama hierárquico de uma organização
• modelagem de algoritmos

• O conceito de árvores está diretamente ligado à recursão

Árvores
• Uma das mais importantes classes de estruturas de

dados em computação são as árvores.
• Aproveitando-se desua organização hierárquica,
muitas aplicações são realizadas usando-se
algoritmos relativamente simples, recursivos e de
eficiência bastante razoável.

Definição
• Uma árvore é uma estrutura de dados que se caracteriza por

uma relação de hierarquia entre os elementos que a compõem.

• uma coleção não vazia de vértices e ramos que

satisfazem a certos requisitos
• Possui uma certaorganização

• Exemplos de estruturas em forma de árvores são:
• O organograma de uma empresa;

• A divisão de um livro em capítulos, seções, tópicos, etc;
• A árvore genealógica de uma pessoa

Exemplos de árvores

Formas de visualização
• Representação hierárquica

Formas de visualização
• Representação por conjuntos

(diagrama de inclusão)

Formas de visualização
•Representação por expressão parentetizada (parênteses aninhados)
•Cada conjunto de parênteses correspondentes contém um nodo e seus filhos.
•Se um nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo.

Formas de visualização
• Representação por expressão não parentetizada
•Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e em

seguida por essesfilhos, representados do mesmo modo.

Formas de visualização
• Representação por edentação (diagrama de barras)

Formas de visualização
• Pode-se representar uma árvore de muitos outros

modos, mas é interessante notar que, dentre os
exemplos apresentados, a primeira representação é a
que permite uma melhor visualização, e que será
utilizada a partir deste ponto.
• As representações“por expressão parentizadas” e “por
expressão não parentizadas” não permitem boa
visualização da estrutura, mas podem ser úteis para
guardar em arquivos os dados de uma árvore.

• Como, por definição, os subconjuntos s1, s2,...,sm são disjuntos,

cada nó só pode ter um pai. Assim, o desenho abaixo, por exemplo,
não representa uma árvore:

Definições
• NÓ ou NODO ou VÉRTICE: é o dado apartir do qual é

definida a hierarquia.
• Raiz: é o nó principal, ou seja, aquele ao qual os demais

nós formam m >= 0 conjuntos disjuntos s1, s2, ... ,
sm, cada um desses conjuntos também é uma árvore
(denominada sub-árvore).
• qualquer nó é a raiz de uma sub-árvore consistindo dele e dos nós

abaixo

Definições
• Sub-árvore: é aquela que se forma a partir de um

determinado nó.
• Alinha que liga dois nodos da árvore denomina-se aresta
ou arco.
• Diz-se que existe caminho entre dois nodos V e W da
árvore, se a partir do nodo V puder-se chegar ao nodo
W percorrendo-se as arestas que ligam os nodos
intermediários entre V e W.
• Observa-se que existe sempre um caminho entre a raiz e

qualquer nodo da árvore.

Definições
• Se houver um caminho entre V e W, começandoem V diz-se






que V é um nodo ancestral de W e W é um nodo descendente de
V.
Se este caminho contiver uma única aresta, diz-se que V é o nodo
pai de W e que W é um nodo filho de V.
Dois nodos que são nodos filhos do mesmo nodo pai são
denominados nodos irmãos.
Uma característica inerente a árvores é que qualquer nodo, exceto a
raiz, tem um único nodo pai.
Se um nodo nãopossui nodos descendentes, ele é chamado
de folha ou nodo terminal da árvore.

Definições
• cada vértice (exceto a raiz) tem exatamente um antecessor imediato ou

pai
• cada vértice tem nós sucessores imediatos ou filhos, a não ser:
• nós sem filhos  terminais ou folhas

• filhos de um mesmo pai – irmãos

• nós com pelo menos um filho  não-terminais ou internos

Definições
•...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • estudante
  • Estudante
  • estudante
  • Estudante
  • Estudante
  • estudante
  • Estudante
  • estudante

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!