Home

Árvores binárias

Este documento está dividido nas seguintes secções:

  1. Nocões básicas
  2. Representação de árvores binárias
  3. Exemplos de operações com árvores binárias
  4. Links relacionados com árvores binárias

1. Noções básicas

Uma árvore binária é um conjunto finito de elementos que ou está vazio ou está dividido em 3 subconjuntos:

·  um elemento chamado raiz da árvore;
·  dois subconjuntos, cada um dos quais é, por si mesmo, uma árvore binária, chamados sub-árvore direita e sub-árvore esquerda.

Um exemplo de uma árvore binária é:

Fig. 1 - Exemplo de uma árvore binária

Fig. 1 - Exemplo de uma árvore binária

 

Na figura 2 são apresentados alguns exemplos de árvores que não são binárias.

Fig. 2 - Exemplo de árvores não binárias               Fig. 2 - Exemplo de árvores não binárias

Fig. 2 - Exemplos de árvores não binárias

 

 

Cada elemento de uma árvore é chamado nó.

O nó A é a raiz da árvore da fig. 1. Como B é a raiz da sua sub-árvore esquerda dizemos que B é o filho esquerdo de A, do mesmo modo, C é o filho direito de A. Por isso A é o pai dos nós B e C e estes dois são irmãos.

Um nó que não tem filhos chama-se folha. As folhas da árvore anterior são D, G e F.

Dizemos que a raiz é o nó que está no nível 0. O nível de qualquer outro nó é igual ao nível do pai mais um.

A altura de uma árvore binária é igual ao maior nível de um nó da árvore (obviamente que esse nó terá que ser uma folha).

Uma árvore binária completa de altura n é uma árvore em que todos os nós que não são folhas têm 2 filhos. Ou dito de outra forma, é uma árvore em que todas as folhas se encontram no nível n. É fácil ver que não pode haver nenhuma árvore de altura n que tenha mais nós que uma árvore completa de altura n.

 

2. Representação de árvores binárias

Uma árvore binária pode ser representada em Pascal por um conjunto de nós compostos por três campos: um campo com a informação associada a esse nó, um ponteiro para o seu filho esquerdo e um ponteiro para o seu filho direito.

Para além disto é ainda necessário um ponteiro externo que aponte para a raiz da árvore. Se a árvore estiver vazia esse ponteiro é igualado a nil.

Em Pascal podemos definir uma árvore da seguinte forma:

Fig. 3  - Representação em Pascal da árvore binária da fig. 1

 

Definicão de uma árvore binária em pseudo-codigo Definicão de uma árvore binária em Pascal

A={(a,fe,fd):a Î elemento ;fe,fd Î A } U {NULL}

 type arvore = ^caixa;
        caixa record
        node : elemento ;
        fd , fe :arvore;
end;
Funcões básicas de acesso em pseudo-codigo Funcões básicas de acesso em Pascal
no A -> Elemento
(a,fe,fd) -> a

function no(a:arvore):elemento;
 begin
   node:=a^.node
end;

fd A -> A
(a,fe,fd) -> fd		 function fd(a:arvore):arvore;
 begin
  fd:=a^.fd
end;
fe A -> A // retorna o filho esquerdo
(a,fe,fd) -> fe		 function fe(a:arvore):arvore;
 begin
  fd:=a^.fe
end;
evazarv A -> Boolean
(a,fe,fd) -> falso
null -> verdadeiro

function isempty(a:arvore):boolean;
 begin
  if a=nil then 
    isempty:=true
  else isempty:=false
end;
criar Elemento,A,A -> A
(a,fe,fd) -> (a,fe,fd)

function consa(a:elemento;fe,fd:A):arvore;
var abis:arvore;
begin
  new(abis);
  abis^.node:=a;
  abis^.fe:=fe;
  abis^.fd:=fd;
 consa:=abis;
end;
criarvaz -> A
-> null		 function create_empty:arvore;
 begin
  create_empty:= nil
end;

 

3. Exemplos de operações com árvores binárias

Para percorrermos uma árvore binária temos muitas vantagens em o fazermos recursivamente como os exemplos de funções que se seguem demonstram:

Funcões recursivas em pseudo-codigo Funcões recursivas em Pascal
Funcao altura(A) -> inteiro // devolve a altura de uma arvore
 Se evaz(A) entao devolve 0
 senao devolve(max(altura(fe),altura(fd))+1

function altura (a:arvore):integer;
begin
 if isempty(a) then
  altura:=0
 else
  altura:=max(altura(fe(a)),altura(fd(a))+1;
end;

Funcao maximoarv(A) -> elemento // devolve o maior elemento
 se nao evazarv(A) entao
  se evazarv(fe(A)) e evazarv(fd(A)) entao
   devolver no(A)
  senao devolver max3(maximoarv(fe(A)),maximoarv(fd(A)),no(A))
senao devolver 0 // aqui podemos escolher outro valor para nil		 function maximoarv(a:arvore):elemento;
begin
 if not isempty(a) then
  if not isempty(fe(a)) and not isempty(fd(a)) then
   maximoarv:=no(a)
  else maximoarv:= max3(maximoarv(fe(a)),maximoarv(fd(a)),no(a));
 else maximoarv:= 0;
end;
funcao numel(A) -> inteiro
 se evazarv(A) entao
  devolve 0
senao
  devolve numel(fe(A)+numel(fd(A))+1;

function numel(a:arvore):integer
begin
 if isempty(a) then
  numel:=0
 else
  numel:=numel(fe(a))+numel(fd(a))+1;
end;



Links relacionados com árvores binárias

 

Animações de Arvores binarias:

Notas de cursos (exteriores á UALG):