Fundamentos sobre Árvores
Uma árvore é um conjunto finito de n nós com n > 0. Quando n = 0
temos uma árvore nula.
Supondo que n > 0 temos uma árvore com as seguintes
características:
 Existe um nó especial chamado raiz;
Os demais são particionados em T1, T2, . . . . . , TK estruturas
disjuntas de árvores denominadas subárvore. Como as estruturas
são disjuntas, garante-se que um nó não aparecerá em mais de
uma subárvore.
a. Grau: Representa o número de subárvores de um nó. O nó “a” da árvore da
figura tem grau 3. Já o nó “h” tem grau 2.
b. Nó folha ou terminal: É o nó que possui grau 0, ou seja, não possui
subárvores. Na figura, os nós ‘e’, ’g’, ’k’, ’l’, ’m’, ’i’ e ‘j’ são folhas.
c. Grau de uma árvore (n-aridade): É definido como sendo igual ao máximo
dos graus de todos os seus nós. Na figura o grau da árvore é 3.
d. Nós filhos: São as raízes das subárvores de um nó, e este nó é o pai delas.
Considerando a figura, os nós ‘e’, ‘f’ e ‘g’ são filhos do nó ‘b’. O nó ‘b’, por
sua vez, é filho do nó ‘a’.
e. Nós irmãos: São os nós filhos que apresentam o mesmo pai (existe ainda
nó ancestral, descendente, descendente esquerdo ou direito). Os nós ‘e’, ‘f’,
e ‘g’, são nós irmãos, porque têm o mesmo pai ’b’.
f. Nível: Nível de um nó é sua distância da raiz da árvore. Como a raiz tem
uma distância zero de si própria, diz-se que ela tem nível 0. Na figura os nós
‘b’ , ‘c’ e ‘d’ estão no nível 1. Os nós ‘e’, ‘f’, ‘g’, ‘h’, ‘i’ e ‘j’ estão no nível 2.E,
finalmente, os ‘k’, ‘l’ e ‘m’ estão no nível 3
g. Altura (também denominada por profundidade): É o nível do nó folha que
tem o mais longo caminho até a raiz, somado um. Por definição, a altura de
uma árvore vazia é -1 . A altura da árvore da figura é 4. Observe a figura:
Representação de uma Árvore
Nível 0
a
Nível 1
c
Nível 2
Nível 3
b
e
f
d
i
g
h
k
l
m
j
Arvores Binárias








Trata-se de uma árvore que pode ser nula ou apresentar as seguintes características:
Um nó especial chamado raiz;
Os demais nós são partiocinados em T1, T2 estruturas disjuntas de árvores binárias.
A estrutura T1 é chamada de subárvore esquerda e T2 subárvore direita da raiz. Cada
subárvore é também, por definição, uma árvore binária;
Considerando que precisamos armazenar n nós em uma árvore binária, sua altura
máxima é obtida por Hmax = n ; entretanto uma árvore binária com altura máxima é rara.
Isso ocorre quando a árvore inteira é construída em uma única direção. A altura mínima
é determinada por hmax = (log2 N) + 1 ;
Dada a altura da árvore binária h, o número mínimo e máximo de nós é conseguido
pelas fórmulas nmin = h e nmax = 2h – 1 ;
Árvores binárias estritamente binária: Ocorre quando todo nó que não é folha tiver
subarvores esquerda e direita não vazias. Uma árvore estritamente binária com n
folhas contém sempre 2n – 1 nós ;
Árvore binária completa : È uma árvore estritamente binária de profundidade d , cujas
folhas estejam no nível d. Considerando tn como o número total de nós em uma árvore
binária completa de altura h, observamos a seguinte relação: Tn = 2h - 1 ;
Uma árvore binária completa contém muitos nós, porém a distância do nó-raiz até
qualquer folha (altura da árvore) pode ser considerada pequena.
Duas árvores binárias distintas com
subárvores nulas
A
B
A
B
Árvore Estritamente Binária
A
B
C
E
D
F
G
Árvore Binária completa de altura 4
A
B
C
H
I
J
G
F
E
D
K
L
M
N
O
Árvore de busca binária e ilustração das
propriedades dessa Árvore
d
b
a
e
c
d
f
Todos < x
Todos ≥ x
14
4
15
3
9
7
9
5
4
14
18
16
20
17
5
Representação de um nó em uma
árvore binária
struct tree {
char info;
struct tree *esq, *dir;
};
Typedef struct tree *TREEPTR;
void tInsere (TREEPTR *plist , char x)
{
if ( ( *plist) ==NULL) (
*plist=(TREEPTR) malloc (sizeof (struct tree) ) ;
(*plist) ->info=x;
(*plist)->esq=NULL;
(*plist)->dir=NULL;
}
else{
if (x<(*plist)->info){
tInsere (&((*plist)->esq),x);
}
else
tInsere (&((*plist)->dir),x);
}
}
Pesquisa de um elemento
• Se T é uma árvore nula, não há o que
pesquisar
• Se a raiz de T armazena o elemento x, a
solução é imediata
• Se x é menor que o valor da raiz de T, a
busca prossegue na subarvore esquerda
de T
• Se x é maior ou igual a T, a busca
prossegue na subarvore direita de T
TREEPTR tPesq(TREEPTR *plist, char x)
{
if (*plist==NULL)
/*elemento nao encontrado */
return (NULL) ;
else
if (x== (*plist)->info) /*elemento encontrado na raiz*/
return(*plist);
else
if (x<(*plist)->info) /*procura-o numa subarvore*/
return(tPesq(&((*plist)->esq),x));
else
return(tPesq(&((*plist)->dir),x));
}
Remoção de um elemento
• Se a raiz não possui filhos, a solução é
imediata. Podemos removê-la e anular T
• Se a raiz possui um único filho,podemos
remover o nó pai e o nó filho toma seu
lugar
• Se a raiz possui dois filhos o nó com
maior elemento à esquerda é removido.
Seu elemento é colocado na raiz da
árvore
Antes
Depois
t
t
20
15
20
41
(a) Remoção do nó (41) sem nenhum filho
15
Antes
Depois
t
t
20
15
9
20
41
15
49
9
(b) Remoção do nó (41) com nenhum filho à esquerda.
49
Antes
Depois
t
t
20
15
9
20
41
9
49
(b) Remoção do nó (15) com nenhum filho à direita.
41
49
Antes
Depois
t
t
20
9
5
11
41
11
9
49
5
(b) Remoção do nó (20) com 2 filhos.
41
49
TREEPTR tMaior (TREEPTR *plist)
{
TREEPTR t;
t=*plist;
if (t->dir=NULL) {
*plist= (*plist)->esq;
return (t);
}
else
return (tMaior (&((*plist) ->dir)));
int tRemove (TREEPTR *plist , char *x)
{
TREEPTR p;
if (*plist==NULL)
return(1);
/*elemento nao encontrado
if ((*x==(*plist)->info)==1)
/*elemento encontrado na raiz
{
p=*plist;
if ((*plist)->esq==NULL)
*plist=(*plist)-> dir; /* a raiz nao tem filho esquerdo
else
if((*plist)->dir==NULL)
*plist=(*plist)->esq; /* a raiz nao tem filho direito
/* a raiz tem ambos os filhos
*/
else
{
p=tMaior(&((*plist)->esq) );
(*plist) -> info=p ->info;
}
free (p);
printf (“\nElemento achado e removido”) ;
}
else
if ((*x<(*plist)->info)==1)
tRemove(&((*plist)->esq).x) ; /*procura na subarvore esquerda
else
tRemove(&((*plist)->dir).x) ; /*procura na subarvore direita */
}
*/
*/
*/
*/
*/