Árvore Binárias

Páginas: 7 (1501 palavras) Publicado: 13 de novembro de 2013
ESTRUTURA DE DADOS – ÁRVORE




SUMÁRIO
1. INTRODUÇÃO.................................................................................................3
1.1 DEFINIÇÃO......................................................................................................3
1.2 CONCEITOS.....................................................................................................31.3 ÁRVORE BINÁRIA............................................................................................4
1.4 ORDEM DE PERCURSO....................................................................................5
1.5 APLICAÇÕES....................................................................................................6
1.6ALOCAÇÃO......................................................................................................7
1.7 OUTROS TIPOS DE ÁRVORES...........................................................................8
REFERÊNCIA..........................................................................................................9

2

2. INTRODUÇÃO

Da mesma forma que as listas lineares, árvores são, estruturada de dados que
caracterizam umarelação entre os dados que a compõem. Essa relação existente entre
os dados conjunto de dados é subordinado a outro.
Uma árvore é composta por um conjunto de nós. Existe o nó r, denominado
raiz, que contem zero ou mais subárvores, cujas raízes são ligadas diretamente a r.
Esses nós raízes das subárvores são ditos filhos do nó pai, r. Nós com filhos são
comumente chamados de nós internos, e nósque não tem filhos são chamados de
folhas ou nós externo. É tradicional desenhar as estruturas de árvores com a raiz para
cima e as folhas para baixo. A figura 1 exemplifica a estrutura de uma árvore.

nó raiz
r

nó interno (subárvore)

i

f

r

r

f
r

f

folha (subárvore)

r

Figura 1. Estrutura de árvore

1.1 DEFINIÇÃO
Formalmente uma árvore é um conjunto finito de Tde um ou mais nós tais
que:
a) Existe um nó denominado raiz da árvore;
b) Os demais nós formam m ≥ 0 conjunto disjuntos T1, T2,..., Tm, onde cada um
destes conjuntos é uma árvore. As árvores Si (l ≤ i ≤ n) recebem a denominação
de subárvores.
1.2 CONCEITOS

NÍVEL: o nível de um nó T é definido como:
• O nível de um nó raiz é 0;
3

• O nível de um nó não raiz é dado por (nível de seunó PAI + 1).
GRAU: o grau de um nó T de uma árvore é igual ao número de filhos do nó T;
GRAU DA ÁRVORE: o grau de uma árvore T é o grau máximo entre os graus de
todos os seus nós;
ALTURA: A altura de um nó v em uma árvore binária é a distância entre v e o seu
descendente mais afastado. Mas precisamente, a altura de v é o número de
passos do mais longo caminho que leva de v até uma folha. Osnós folha sempre
têm altura igual a 0;
ALTURA ou PROFUNDIDADE DE UMA ÁRVORE: A altura de uma árvore T é dada
pela altura da raiz da árvore.
• Denota-se a altura de uma árvore com raiz dada pelo nó T por h(T), e a altura
de uma
subárvore com raiz T1 por h(T1).
Outras formas de representação:
• Representação por parênteses aninhados (A (B) (C (D (G) (H)) (E) (F (I)))) ou
seja, uma listageneralizada!
• Representação por Diagramas de Venn.

A
D

B

E

C

Figura 2. Representação por diagrama de Venn.
O número de filhos permitido por nó e as informações armazenadas em cada
nó diferenciam os diversos tipos de árvores existentes. Serão estudados dois tipos de
árvores. Primeiro, examinaremos as árvores binárias, onde cada nó tem, no máximo,
dois filhos. Depois examinaremosas chamadas árvores genéricas, onde o número de
filhos é indefinido. Estruturas recursivas serão usadas como base para o estudo e a
implementação das operações com árvores.
1.3 ÁRVORE BINÁRIA

Árvores binárias são estruturas do tipo árvore, onde o grau de cada nó é menor
ou igual a dois. Ela distingue-se entre subárvore da esquerda e subárvore de direita.
4

Em uma árvore binária...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Arvore Binaria
  • Arvore Binaria
  • Arvore Binaria
  • Árvore Binária
  • Árvore Binária
  • Arvore binaria
  • Arvore binaria
  • Arvore binária

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!