ARVORES CUSTURADAS

Evellyn Mota
Mayk Menezes
Samir Dantas
Walter Wallace

Motivação
!
" Problemas da recursividade
! Memória e tempo de execução

!
" Problemas da árvore binária
! Ponteiros null

Problema
!
" Como evitar esses “desperdícios” de memória e espaço?
!
Perlis e Thomton propuseram a reutilização dos ponteiros nulls e a
"
eliminação da recursividade para o caminhamento em árvores binárias.

!

Árvore Alinhadas ou com Costura
!
" São árvores binárias onde todos os nós que não possuem um filho tem uma “costura” (link) para o seu sucessor ou predecessor.
!
" Estrutura do nó
TAGES
Q

LINKES ELEM
Q

LINKDI TAGDIR
R

Representação
!

Pseudo-Código
!
" Método insucc
! Finalidade: Obtenção do sucessor em ordem infixa de um nó pertencente a uma árvore binária costurada. Os nós da árvore possuem atributos < lbit, left, info, right, rbit >. lbit e rbit podem assumir os valores PONTEIRO (1) ou TEIA (0).

!

"
"
"
"
"
"
"
"
"
"

Início p (*x).right
Se ((*x).rbit = PONTEIRO) então /* existe um filho mais novo */
Enquanto ((*p).lbit = 1) p (*p).left /* avançar para a esquerda até encontrar uma folha, identificada pela teia */
Fim do Enquanto
Fim do Se retorne(p) Fim do Procedimento

" Método TravessiaInFixa

Pseudo-Código
!

! Finalidade: Travessia de uma árvore binária costurada, de raiz apontada por ptree, em ordem infixa.

!

" Início
/* p passa a ser o “ header” */
" p ptree
" Enquanto (TRUE) p insuc (p)
"
Se (p = ptree)
"
então
/* voltou-se ao “header”. Acabou o percursso */
"
retorne
"
senão
"
Imprima ((*p).info)
"
Fim do Se
"
" Fim do Enquanto
" Fim do Procedimento

!

Árvore Binária com Costura em Pré-Ordem à direita

!

Código em Java
!
" Representação do nó na linguagem Java class Node {
Node left, right; boolean leftThread, rightThread; }

Código em Java
!
Node leftMost(Node n) {
Node ans = n; if (ans == null) { return null;
}
while