Árvores
1
Definição
Definição (Árvore) Uma árvore T é um
conjunto finito e não vazio de nós,
com as seguintes propriedades:
Um certo nó do conjunto, r, é chamado de
raiz da árvore; e
2. Os demais nós são repartidos em sub conjuntos,
T1, T2, ..., Tn , cada um dos quais sendo uma
árvore.
1.
É usual adotar para a árvore T a notação.
2
Nomenclatura
Seja
uma árvore com n  0
Grau de um nó é o número de sub-árvores do
nó
Folha é um nó de grau zero
As raízes ri das sub-árvores Ti são filhas de r
A raiz r da árvore T é pai das raízes ri
Raízes ri e rj de árvores distintas Ti e Tj são
irmãs
3
Nomenclatura
Nível ou profundidade de um nó ri de uma árvore T é o
comprimento do caminho entre a raiz e o nó ri


A raiz está no nível zero e seus filhos estão no nível 1 (Preiss)
A raiz está no nível 1 e seus filhos estão no nível 2 (Horowitz)
Altura de um nó é o caminho mais longo do nó até uma folha
Altura de uma árvore é a altura do nó raiz
O pai de um nó é seu ancestral e o pai de seu pai também
O filho de um nó é seu descendente e o filho de seu filho
também
Ordem de um nó é o grau do nó
Ordem de uma árvore é a ordem de seu nó de maior ordem
4
Nomenclatura
Níveis em
versão
Horowitz
5
Representação de árvores por parênteses
A árvore acima teria a seguinte representação usando
parênteses:
(A(B(E(K, L), F)) , (C (G)), (D(H(M), I, J))))
6
Outras representações de árvores
7
Caminho e Comprimento de Caminho
Definição (Caminho e Comprimento de Caminho)
Para uma árvore T contendo o conjunto de nós R, um
caminho em T é definido como uma seqüência não
vazia de nós
ri  R para1  i  k tal que o i  ésim o nó da seqüência, ri ,
é o pai do (i  1)  ésim o nó da seqüênciari 1. O com prim ent
o
do
min ho PPéékk11
doca
caminho
8
Árvores N-árias
Definição (Árvores N-arias)
Uma árvore N-aria T é um conjunto finito de
nós com as propriedades:
1. Ou o conjunto é vazio, T= ; ou
2. O conjunto consiste em uma raiz, R, e exatamente
N árvores N-arias distintas. Os demais nós são
repartidos em N0 sub conjuntos, T0,T1 , ..., TN-1 ,
cada qual sendo uma árvore N-aria tal que
9
Árvore Binária
Definição (Árvore Binária) Uma árvore binária
T é um conjunto finito de nós com as
propriedades:
1. Ou o conjunto é vazio, T =  ; ou
2. O conjunto consiste em uma raiz, r, e exatamente
duas árvores binárias distintas T L e TR . A árvore
TL é chamada árvore da esquerda de T, e a árvore
TR é chamada árvore da direita de T.
10
Travessia ou Visitação de Árvores
Existem dois métodos de visitação
sistemática a todos os nós de uma árvore:
Travessia em largura ou breadth-first traversal
(BFT)
 Travessia em profundidade ou depth-first
traversal (DFT)

11
Backtracking
Backtracking é um esquema de solução de uma série de
sub problemas cada um dos quais podendo ter múltiplas
possíveis soluções e aonde a solução escolhida para um
subproblema pode afetar as possíveis soluções dos
subproblemas posteriores
Para resolver o problema como um todo encontra-se a
solução do primeiro sub problema e busca-se
recursivamente resolver os outros sub problemas com base
na primeira solução
Se isto não for possível ou caso se deseje obter todas as
possíveis soluções faz-se o backtrack e tenta-se a próxima
solução possível para o primeiro sub problema e assim por
diante
Backtracking termina quando não mais existem soluções
para o primeiro sub problema.
12
DFT e BFT
depth-first search ou busca em profundidade:
Algoritmo de busca em grafos que estende o
caminho corrente tanto quanto possível, antes de
executar backtracking, até o último ponto aonde
houve escolha e tentar outro caminho alternativo
breadth first search ou busca em largura:
Algoritmo de busca em grafos que tenta todas as
possíveis extensões de um passo antes de tentar
extensões maiores

Isto obriga que se mantenham em memória todos os
caminhos correntes, ou, pelo menos, seus pontos
terminais.
13
BFT (Breadth-First Traversal)
Enquanto a travessia em profundidade (DFT) é
definida recursivamente a travessia em largura é
melhor compreendida como uma travessia não
recursiva
A travessia BFT de uma árvore visita os nós em
ordem de sua profundidade na árvore


BFT primeiro visita todos os nós à profundidade zero
(i. e. a raiz), então todos os nós à profundidade um e
assim por diante
Em cada nível os nós são visitados da esquerda para a
direita
14
Árvores Genéricas
15
Árvores Genéricas
16
Árvores Binárias
17
Árvores Binárias
18
Árvores binárias completas e incompletas
19
Implementação de árvores binárias por “arrays”
Esta árvore binária tem altura k e número n de nós.
n = 2k - 1 = 2 4 - 1 = 15
1
2
3
i
14
15
2
i
13
14
ou
0
1
20
Implementação de árvores binárias por “arrays”
Se um nó está na posição i, seu pai está na posição
i/2 se i  0 (caso o nó inicial seja 0 em vez de 1
o valor será i/2 - 1)
O filho esquerdo (mais velho) de i está na posição:


2 i se 2*i  n (caso o nó inicial seja 0 em vez de 1 o
valor será 2*i+1)
Caso contrário este filho não existe
O filho direito (mais novo) de i está na posição:


2*i + 1 se 2*i + 1n (caso o nó inicial seja 0 em vez de
1 o valor será 2*i+2)
Caso contrário este filho não existe
21
Implementação de árvores binárias por encadeamento
Os nós das árvores binárias podem ser
representados da forma
22
Implementação de árvores binárias por encadeamento
23
Caminhamento ou percurso sobre árvores binárias
Uma seqüência de nós que contenha todos os nós de
uma árvore binária, sem repetições, produz uma relação
de ordem total para seus nós que é chamado de
caminhamento ou percurso sobre a árvore
24
Caminhamento ou percurso sobre árvores binárias
São possíveis as seguintes seqüências:






ECD - ordem infixa
EDC - ordem pós-fixa
CED - ordem pré-fixa
CDE
(pré-fixa)
DCE
descartadas (infixa)
DEC
(pós-fixa)
A ordem infixa é a ordem de percurso na qual percorre-se a sub árvore
da esquerda, “visita-se” a raiz e percorre-se a sub árvore da direita.
A ordem pós-fixa é aquela na qual percorre-se a sub árvore da
esquerda, a sub árvore da direita e “visita-se” a raiz.
A ordem pré-fixa é aquela na qual “visita-se” a raiz, percorre-se a sub
árvore da esquerda e a sub árvore da direita.
25
Caminhamento ou percurso sobre árvores binárias
Percurso ou notação pré-fixa:
Percurso ou notação infixa:
Percurso ou notação pós-fixa:
ABDHIECFG
HDIBEAFCG
HIDEBFGCA
26
Notação Decimal de Dewey
Os nós de uma árvore binária podem ser identificados por uma seqüência de zeros
e uns em uma notação análoga à notação decimal de Dewey de acordo com as
regras que se seguem.
(i) A raiz é representada por “1”
(ii) O filho mais velho do nó “x” é representado por “x0”
(iii) O filho mais novo do nó “x” é representado por “x1”.
27
Notação Decimal de Dewey
Notação de Dewey
1
10
11
100
101
111
Chave do nó
A
B
C
D
E
F
É comum apresentar todos os nós como seqüências de caracteres com o mesmo
tamanho, igual a altura da árvore, completando-se a árvore binária anterior por:
Notação de Dewey
1bb
10b
11b
100
101
111
Chave do nó
A
B
C
D
E
F
onde ‘b’ representa o caractere “branco”.
28
Implementação Java
29
Framework de Árvores
30
Interface Tree
//pgm09_01.txt
public interface Tree
extends Container
{
Object getKey ();
Tree getSubtree (int i);
boolean isEmpty ();
boolean isLeaf ();
int getDegree ();
int getHeight ();
void depthFirstTraversal (PrePostVisitor
visitor);
void breadthFirstTraversal (Visitor visitor);
}
31
Métodos da Interface Tree
getKey
Este método retorna o objeto contido no nó raiz de uma árvore.
getSubtree
Este método retorna a -iésima sub árvore de uma árvore.
isEmpty
Este método booleano retorna true se a raiz da árvore for uma árvore vazia, i, e. um nó
externo.
isLeaf
Este método booleano retorna true se a raiz da árvore for um nó folha.
getDegree
Este método retorna o grau do nó raiz de uma árvore. Por definição, o grau de um nó
externo é zero.
getHeight
Este método retorna a altura de uma árvore. Por definição, a altura de uma árvore vazia
é -1.
depthFirstTraversal and breadthFirstTraversal
Estes métodos são semelhantes ao método accept da classe container. Ambos executam
uma travessia. Todos os nós são visitados sistematicamente. O primeiro aceita um
PrePostVisitor e o último aceita um Visitor. Quando um nó for visitado os métodos
apropriados do visitor são aplicados ao nó.
32
Método depthFirstTraversal de
AbstractTree
//
pgm09_02.txt
public abstract class AbstractTree
extends AbstractContainer
implements Tree
{
public void depthFirstTraversal (PrePostVisitor visitor)
{
if (visitor.isDone ())
return;
if (!isEmpty ())
{
visitor.preVisit (getKey ());
for (int i = 0; i < getDegree (); ++i)
getSubtree (i).depthFirstTraversal (visitor);
visitor.postVisit (getKey ());
}
}
// ...
}
33
Interface PrePostVisitor
//pgm09_03.txt
public interface PrePostVisitor
{
void preVisit (Object object);
void inVisit (Object object);
void postVisit (Object object);
boolean isDone ();
}
34
Classe Abstrata AbstractPrePostVisitor
//pgm09_04.txt
public abstract class AbstractPrePostVisitor
implements PrePostVisitor
{
public void preVisit (Object object)
{}
public void inVisit (Object object)
{}
public void postVisit (Object object)
{}
public boolean isDone ()
{ return false; }
}
35
Classe PreOrder
// //pgm09_05.txt
public class PreOrder
extends AbstractPrePostVisitor
{
protected Visitor visitor;
public PreOrder (Visitor visitor)
{ this.visitor = visitor; }
public void preVisit (Object object)
{ visitor.visit (object); }
public boolean isDone ()
{ return visitor.isDone (); }
}
36
Classe InOrder
// //pgm09_06.txt
public class InOrder
extends AbstractPrePostVisitor
{
protected Visitor visitor;
public InOrder (Visitor visitor)
{ this.visitor = visitor; }
public void inVisit (Object object)
{ visitor.visit (object); }
public boolean isDone ()
{ return visitor.isDone (); }
}
37
Classe PostOrder
// //pgm09_07.txt
public class PostOrder
extends AbstractPrePostVisitor
{
protected Visitor visitor;
public PostOrder (Visitor visitor)
{ this.visitor = visitor; }
public void postVisit (Object object)
{ visitor.visit (object); }
public boolean isDone ()
{ return visitor.isDone (); }
}
38
Exemplo de travessia de Árvores
Visitor v = new PrintingVisitor ();
Tree t = new SomeTree ();
// ...
t.depthFirstTraversal
(new PreOrder (v));
t.depthFirstTraversal
(new InOrder (v));
t.depthFirstTraversal
(new PostOrder (v));
39
Implementação de BFT (1)
// pgm09_08.txt
public abstract class AbstractTree
extends AbstractContainer
implements Tree
{
public void breadthFirstTraversal (Visitor
visitor)
{
Queue queue = new QueueAsLinkedList ();
if (!isEmpty ())
queue.enqueue (this);
}
}
}
40
Implementação de BFT (2)
while (!queue.isEmpty () && !visitor.isDone ())
{
Tree head = (Tree) queue.dequeue ();
visitor.visit (head.getKey ());
for (int i = 0; i < head.getDegree (); ++i)
{
Tree child = head.getSubtree (i);
if (!child.isEmpty ())
queue.enqueue (child);
}
}
}
}
41
Método accept
// pgm09_09.txt
public abstract class AbstractTree
extends AbstractContainer
implements Tree
{
public void accept (Visitor visitor)
{ depthFirstTraversal
(new PreOrder (visitor)); }
// ...
}
A escolha de ordem pré-fixa foi arbitrária
42
Exemplo de varredura de Árvore
Tree tree = new BinaryTree ();
// ...
Enumeration e = tree.getEnumeration ();
while (e.hasMoreElements ())
{
Object obj = e.nextElement ();
System.out.println (obj);
}
43
Classe interna TreeEnumeration
// pgm09_10.txt
public abstract class AbstractTree
extends AbstractContainer
implements Tree
{
public Enumeration getEnumeration ()
{ return new TreeEnumeration (); }
protected class TreeEnumeration
implements Enumeration
{
protected Stack stack;
// ...
}
// ...
}
44
Construtor de TreeEnumeration
// pgm09_11.txt
public abstract class AbstractTree
extends AbstractContainer
implements Tree
{
protected class TreeEnumeration
implements Enumeration
{
public TreeEnumeration ()
{
stack = new StackAsLinkedList ();
if (!isEmpty ())
stack.push (AbstractTree.this);
}
}
// ...
}
A escolha da enumeração ser por BFT foi arbitrária
45
Método hasMoreElements da Classe
AbstractTree
// pgm09_12.txt
public abstract class AbstractTree
extends AbstractContainer
implements Tree
{
protected class TreeEnumeration
implements Enumeration
{
public boolean hasMoreElements ()
{ return !stack.isEmpty (); }
46
Método nextElement da Classe AbstractTree
public Object nextElement ()
{
if (stack.isEmpty ())
throw new NoSuchElementException ();
Tree top = (Tree) stack.pop ();
for (int i = top.getDegree () - 1; i >= 0; --i)
{
Tree subtree = (Tree) top.getSubtree (i);
if (!subtree.isEmpty ())
stack.push (subtree);
}
return top.getKey ();
}
}
}
O empilhamento foi em ordem inversa para a enumeração ser em ordem direta
(BFT)
47
Árvores Genéricas
48
Classe GeneralTree
// //pgm09_13.txt
public class GeneralTree
extends AbstractTree
{
protected Object key;
protected int degree;
protected LinkedList list;
// ...
}
49
Métodos Construtor e Purge de GeneralTree
// pgm09_14.txt
public class GeneralTree
extends AbstractTree
{
protected Object key;
protected int degree;
protected LinkedList list;
public GeneralTree (Object key)
{
this.key = key;
degree = 0;
list = new LinkedList ();
}
public void purge ()
{
list.purge ();
degree = 0;
}
}
50
Método getSubtree da Classe
Generaltree
// pgm09_15.txt
public class GeneralTree
extends AbstractTree
{
protected Object key;
protected int degree;
protected LinkedList list;
public Object getKey ()
{ return key; }
51
Método getSubtree da Classe
Generaltree
public Tree getSubtree (int i)
{
if (i < 0 || i >= degree)
throw new IndexOutOfBoundsException ();
LinkedList.Element ptr = list.getHead ();
for (int j = 0; j < i; ++j)
ptr = ptr.getNext ();
return (GeneralTree) ptr.getDatum ();
}
}
// ...
}
52
Métodos attachSubtree e detachSubtree
public void attachSubtree (GeneralTree t)
{
list.append (t);
++degree;
}
public GeneralTree detachSubtree (GeneralTree t)
{
list.extract (t);
--degree;
return t;
}
53
Árvores N-árias
54
Classe NaryTree
// //pgm09_16.txt
public class NaryTree
extends AbstractTree
{
protected Object key;
protected int degree;
protected NaryTree[] subtree;
// ...
}
55
Construtores de NaryTree (1)
// pgm09_17.txt
public class NaryTree
extends AbstractTree
{
protected Object key;
protected int degree;
protected NaryTree[] subtree;
public NaryTree (int degree)
{
key = null;
this.degree = degree;
subtree = null;
}
56
Construtores de NaryTree (2)
public NaryTree (int degree, Object
key)
{
this.key = key;
this.degree = degree;
subtree = new NaryTree[degree];
for (int i = 0; i < degree; ++i)
subtree [i] = new NaryTree
(degree);
}
// ...
}
57
Método isEmpty
//
pgm09_18.txt
public class NaryTree
extends AbstractTree
{
protected Object key;
protected int degree;
protected NaryTree[] subtree;
public boolean isEmpty ()
{ return key == null; }
}
58
Métodos getKey e attachKey
public Object getKey ()
{
if (isEmpty ())
throw new InvalidOperationException ();
return key;
}
public void attachKey (Object object)
{
if (!isEmpty ())
throw new InvalidOperationException ();
key = object;
subtree = new NaryTree[degree];
for (int i = 0; i < degree; ++i)
subtree [i] = new NaryTree (degree);
}
59
Método detachKey
public Object detachKey ()
{
if (!isLeaf ())
throw new InvalidOperationException
();
Object result = key;
key = null;
subtree = null;
return result;
}
60
Métodos getKey, attachKey e detachKey
getKey é um método de acesso que retorna
o objeto contido na raiz da árvore.
attachKey insere um objeto na raiz de uma
árvore N-aria. São criadas N sub árvores
vazias
detachKey remove o objeto da raiz de uma
árvore. Para manter a definição de árvore
N-aria só se pode remover a raiz de um nó
folha.
61
Métodos getSubTree e attachSubTree
//
pgm09_19.txt
public Tree getSubtree (int i)
{
if (isEmpty ())
throw new InvalidOperationException ();
return subtree [i];
}
public void attachSubtree (int i, NaryTree t)
{
if (isEmpty () || !subtree [i].isEmpty ())
throw new InvalidOperationException ();
subtree [i] = t;
}
62
Método detachSubTree
NaryTree detachSubtree (int i)
{
if (isEmpty ())
throw new InvalidOperationException ();
NaryTree result = subtree [i];
subtree [i] = new NaryTree (degree);
return result;
}
63
Árvores Binárias
64
Classe BinaryTree
//
pgm09_20.txt
public class BinaryTree
extends AbstractTree
{
protected Object key;
protected BinaryTree left;
protected BinaryTree right;
// ...
}
65
Construtores de BinaryTree (1)
//
pgm09_21.txt
public class BinaryTree
extends AbstractTree
{
protected Object key;
protected BinaryTree left;
protected BinaryTree right;
public BinaryTree (
Object key, BinaryTree left, BinaryTree right)
{
this.key = key;
this.left = left;
this.right = right;
}
66
Construtores de BinaryTree (2)
public BinaryTree ()
{ this (null, null, null); }
public BinaryTree (Object key)
{ this (key, new BinaryTree (),
new BinaryTree ()); }
// ...
}
67
Método Purge
//
pgm09_22.txt
public class BinaryTree
extends AbstractTree
{
protected Object key;
protected BinaryTree left;
protected BinaryTree right;
public void purge ()
{
key = null;
left = null;
right = null;
}
// ...
}
68
Travessia de árvores binárias
//pgm09_23.txt
public class BinaryTree
extends AbstractTree
{
protected Object key;
protected BinaryTree left;
protected BinaryTree right;
public void depthFirstTraversal (PrePostVisitor visitor)
{
if (!isEmpty ())
{
visitor.preVisit (key);
left.depthFirstTraversal (visitor);
visitor.inVisit (key);
right.depthFirstTraversal (visitor);
visitor.postVisit (key);
}
}
69
}
Comparação de árvores
70
Comparação de árvores
protected int compareTo (Comparable object)
{
BinaryTree arg = (BinaryTree) object;
if (isEmpty ())
return arg.isEmpty () ? 0 : -1;
else if (arg.isEmpty ())
return 1;
else
{
int result = ((Comparable) getKey ()).compare (
(Comparable) arg.getKey ());
if (result == 0)
result = getLeft ().compareTo (arg.getLeft ());
if (result == 0)
result = getRight ().compareTo (arg.getRight
());
return result;
}
71
}
Classe AbstractTree
//
pgm09_09.txt
public abstract class AbstractTree
extends AbstractContainer
implements Tree
{
public void accept (Visitor visitor)
{ depthFirstTraversal (new PreOrder
(visitor)); }
// ...
}
72
DFT (depthFirstTraversal)
//
pgm09_23.txt
public class BinaryTree
extends AbstractTree
{
protected Object key;
protected BinaryTree left;
protected BinaryTree right;
public void depthFirstTraversal (PrePostVisitor visitor)
{
if (!isEmpty ())
{
visitor.preVisit (key);
left.depthFirstTraversal (visitor);
visitor.inVisit (key);
right.depthFirstTraversal (visitor);
visitor.postVisit (key);
}
}
}
73
Implementação C++
74
Definição da Classe Tree
// pgm09_01.cpp
class Tree : public virtual Container
{
class Iter;
public:
virtual Object& Key () const = 0;
virtual Tree& Subtree (unsigned int) const = 0;
virtual bool IsEmpty () const = 0;
virtual bool IsLeaf () const = 0;
virtual unsigned int Degree () const = 0;
virtual int Height () const;
virtual void DepthFirstTraversal (PrePostVisitor&) const;
virtual void BreadthFirstTraversal (Visitor&) const;
void Accept (Visitor&) const;
};
75
Definições da Função Membro
Traversal da Classe Tree
// pgm09_02.cpp
void Tree::DepthFirstTraversal ( PrePostVisitor&
visitor) const
{
if(visitor.IsDone ())
return;
if(!IsEmpty ())
{
visitor.PreVisit (Key ());
for(unsigned int i = 0; i < Degree (); ++i)
Subtree (i).DepthFirstTraversal (visitor);
visitor.PostVisit (Key ());
}
}
76
Definições das Classes PrePostVisitor
e PreOrder
// pgm09_03.cpp
class PrePostVisitor : public Visitor
{
public:
virtual void PreVisit (Object&) {}
virtual void Visit (Object&) {}
virtual void PostVisit (Object&) {}
};
class PreOrder : public PrePostVisitor
{
Visitor& visitor;
public:
PreOrder (Visitor& v) : visitor (v) {}
void PreVisit (Object& object)
{ visitor.Visit (object); }
};
77
Definições das Classes InOrder e
PostOrder
class InOrder : public PrePostVisitor
{
Visitor& visitor;
public:
InOrder (Visitor& v) : visitor (v) {}
void Visit (Object& object)
{ visitor.Visit (object); }
};
class PostOrder : public PrePostVisitor
{
Visitor& visitor;
public:
PostOrder (Visitor& v) : visitor (v) {}
void PostVisit (Object& object)
{ visitor.Visit (object); }
};
78
Definição da Função Membro
BreadthFirstTraversal da Classe Tree
// pgm09_04.cpp
void Tree::BreadthFirstTraversal (Visitor& visitor) const
{
Queue& queue = *new QueueAsLinkedList ();
queue.RescindOwnership ();
if(!IsEmpty ())
queue.Enqueue(const_cast<Tree&> (*this));
while(!queue.IsEmpty() && !visitor.IsDone()) {
Tree const& head = dynamic_cast<Tree const &>
(queue.Dequeue ());
visitor.Visit(head.Key ());
for(unsigned int i = 0; i < head.Degree (); ++i) {
Tree& child = head.Subtree(i);
if(!child.IsEmpty ())
queue.Enqueue (child);
}
}
delete &queue;
79
}
Definição da Função Membro Accept
da Classe Tree
// pgm09_05.cpp
void Tree::Accept (Visitor& visitor) const
{ DepthFirstTraversal (PreOrder (visitor)); }
80
Definição da Classe Tree::Iter
// pgm09_06.cpp
class Tree::Iter : public Iterator
{
Tree const& tree;
Stack& stack;
public:
Iter(Tree const&);
~Iter();
void Reset();
bool IsDone() const;
Object& operator * () const;
void operator ++ ();
};
81
Definições da Função Membro Reset
e do Construtor da Classe Tree::Iter
// pgm09_07.cpp
Tree::Iter::Iter (Tree const& _tree) :
tree (_tree), stack (*new StackAsLinkedList ())
{
stack.RescindOwnership();
Reset();
}
Tree::Iter::~Iter()
{ delete &stack; }
void Tree::Iter::Reset()
{
stack.Purge();
if(!tree.IsEmpty ())
stack.Push(const_cast<Tree&> (tree));
}
82
Definições das Funções Membro
Operador da Classe Tree::Iter (1)
// pgm09_08.cpp
bool Tree::Iter::IsDone() const
{ return stack.IsEmpty(); }
Object& Tree::Iter::operator * () const
{
if(!stack.IsEmpty ())
{
Tree const& top = dynamic_cast<Tree const&> (stack.Top ());
return top.Key ();
}
else
return NullObject::Instance ();
}
83
Definições da Função Membro
Operador da Classe Tree::Iter (2)
void Tree::Iter::operator ++ ()
{
if(!stack.IsEmpty ())
{
Tree const& top = dynamic_cast<Tree const&>
(stack.Pop ());
for(int i = top.Degree () - 1; i >= 0; --i)
{
Tree& subtree = top.Subtree (i);
if(!subtree.IsEmpty ())
stack.Push (subtree);
}
}
}
84
Definição da Classe GeneralTree
// pgm09_09.cpp
class GeneralTree : public Tree
{
protected:
Object* key;
unsigned int degree;
LinkedList<GeneralTree*> list;
public:
GeneralTree(Object&);
~GeneralTree();
Object& Key() const;
GeneralTree& Subtree(unsigned int) const;
virtual void AttachSubtree(GeneralTree&);
virtual GeneralTree& DetachSubtree(GeneralTree&);
// ...
};
85
Definições da Função Membro Purge,
do Construtor e do Destrutor da
Classe GeneralTree
// pgm09_10.cpp
GeneralTree::GeneralTree (Object& _key) :
key (&_key), degree (0), list()
{}
void GeneralTree::Purge()
{
ListElement<GeneralTree*> const* ptr;
if(IsOwner ())
delete key;
for(ptr = list.Head(); ptr != 0; ptr = ptr->Next())
delete ptr->Datum();
key = 0;
list.Purge();
}
GeneralTree::~GeneralTree()
{ Purge (); }
86
Definições das Funções Membro Key,
Subtree, AttachSubtree e DetachSubtree
da Classe GeneralTree (1)
// pgm09_11.cpp
Object& GeneralTree::Key() const
{ return *key; }
GeneralTree& GeneralTree::Subtree(unsigned int i) const
{
if(i >= degree)
throw out_of_range("invalid subtree index");
unsigned int j = 0;
ListElement<GeneralTree*> const* ptr = list.Head();
while(j < i && ptr != 0)
{
++j;
ptr = ptr->Next();
}
if(ptr == 0)
throw logic_error("should never happen");
return *ptr->Datum();
}
87
Definições das Funções Membro Key,
Subtree, AttachSubtree e DetachSubtree
da Classe GeneralTree (2)
// pgm09_11.cpp (Continuação)
void GeneralTree::AttachSubtree(GeneralTree& t)
{
list.Append (&t);
++degree;
}
GeneralTree& GeneralTree::DetachSubtree(GeneralTree& t)
{
list.Extract (&t);
--degree;
return t;
}
88
Definição da Classe NaryTree
// pgm09_12.cpp
class NaryTree : public Tree
{
protected:
Object* key;
unsigned int const degree;
Array<NaryTree*> subtree;
public:
NaryTree(unsigned int);
NaryTree(unsigned int, Object&);
~NaryTree();
Object& Key() const;
NaryTree& Subtree(unsigned int) const;
virtual void AttachKey(Object&);
virtual Object& DetachKey();
virtual void AttachSubtree(unsigned int, NaryTree&);
virtual NaryTree& DetachSubtree(unsigned int);
// ...
89
};
Definições dos Construtores da
Classe NarryTree
// pgm09_13.cpp
NaryTree::NaryTree(unsigned int _degree) :
key (0),
degree(_degree),
subtree(0)
{}
NaryTree::NaryTree(unsigned int _degree, Object& _key):
key(&_key),
degree(_degree),
subtree(_degree)
{
for(unsigned int i = 0; i < degree; ++i)
subtree [i] = new NaryTree(degree);
}
90
Definições das Funções Membro IsEmpty,
Key e AttachKey da Classe NaryTree
// pgm09_14.cpp
bool NaryTree::IsEmpty() const
{ return key == 0; }
Object& NaryTree::Key() const
{
if(IsEmpty ())
throw domain_error("invalid operation");
return *key;
}
void NaryTree::AttachKey(Object& object)
{
if(!IsEmpty ())
throw domain_error("invalid operation");
key = &object;
subtree.SetLength(degree);
for(unsigned int i = 0; i < degree; ++i)
subtree[i] = new NaryTree(degree);
}
91
Definições da Função Membro
DetachKey da Classe NaryTree
Object& NaryTree::DetachKey()
{
if(!IsLeaf ())
throw domain_error("invalid operation");
Object& result = *key;
key = 0;
for(unsigned int i = 0; i < degree; ++i)
delete subtree[i];
subtree.SetLength(0);
return result;
}
92
Definições das Funções Membro Subtree
e AttachSubtree da Classe NaryTree
// pgm09_15.cpp
NaryTree& NaryTree::Subtree(unsigned int i) const
{
if(IsEmpty ())
throw domain_error("invalid operation");
return *subtree[i];
}
void NaryTree::AttachSubtree(unsigned int i, NaryTree& t)
{
if(IsEmpty ())
throw domain_error("invalid operation");
if(!subtree [i]->IsEmpty ())
throw domain_error("non-empty subtree present");
delete subtree[i];
subtree[i] = &t;
}
93
Definições da Função Membro
DetachSubtree da Classe NaryTree
// pgm09_15.cpp (Continuação)
NaryTree& NaryTree::DetachSubtree(unsigned int i)
{
if(IsEmpty ())
throw domain_error("invalid operation");
NaryTree& result = *subtree[i];
subtree[i] = new NaryTree(degree);
return result;
}
94
Definição da Classe BinaryTree (1)
// pgm09_16.cpp
class BinaryTree : public virtual Tree
{
protected:
Object* key;
BinaryTree* left;
BinaryTree* right;
public:
BinaryTree();
BinaryTree(Object&);
~BinaryTree();
95
Definição da Classe BinaryTree (2)
Object&
virtual
virtual
virtual
virtual
virtual
virtual
virtual
virtual
// ...
Key() const;
void AttachKey(Object&);
Object& DetachKey();
BinaryTree& Left() const;
BinaryTree& Right() const;
void AttachLeft(BinaryTree&);
void AttachRight(BinaryTree&);
BinaryTree& DetachLeft();
BinaryTree& DetachRight();
};
96
Definição dos Construtores da Classe
BinaryTree
// pgm09_17.cpp
BinaryTree::BinaryTree() :
key(0),
left(0),
right(0)
{}
BinaryTree::BinaryTree(Object& _key) :
key(&_key),
left(new BinaryTree ()),
right(new BinaryTree ())
{}
97
Definições da Função Membro Purge
e do Destrutor da Classe BinaryTree
// pgm09_18.cpp
void BinaryTree::Purge()
{
if(!IsEmpty ())
{
if(IsOwner ())
delete key;
delete left;
delete right;
key = 0;
left = 0;
right = 0;
}
}
BinaryTree::~BinaryTree()
{ Purge (); }
98
Definição da Função Membro
DepthFirstTraversal da Classe
BinaryTree
// pgm09_19.cpp
void BinaryTree::DepthFirstTraversal( PrePostVisitor&
visitor) const
{
if(visitor.IsDone ())
return;
if(!IsEmpty ())
{
visitor.PreVisit (*key);
left->DepthFirstTraversal(visitor);
visitor.Visit(*key);
right->DepthFirstTraversal(visitor);
visitor.PostVisit(*key);
}
}
99
Definição da Função Membro
CompareTo da Classe BinaryTree
// pgm09_20.cpp
int BinaryTree::CompareTo(Object const& object) const {
BinaryTree const& arg = dynamic_cast<BinaryTree
const&> (object);
if(IsEmpty ())
return arg.IsEmpty() ? 0 : -1;
else
if(arg.IsEmpty ())
return 1;
else {
int result = Key().Compare(arg.Key ());
if(result == 0)
result = Left().CompareTo(arg.Left ());
if(result == 0)
result = Right().CompareTo(arg.Right ());
return result;
}
}
100
REPRESENTAÇÃO DE ÁRVORES POR
ÁRVORES BINÁRIAS
101
REPRESENTAÇÃO DE ÁRVORES POR
ÁRVORES BINÁRIAS
Uma das maneiras mais eficientes de
representar árvores em linguagens de
programação consiste na consideração
dos filhos de cada nó por meio de uma
lista encadeada. Nessa representação os
nós são do tipo
son
info
next
102
Representação de árvores por
árvores binárias
103
Representação de árvores por
árvores binárias
Fazendo uma analogia com árvores binárias
associando o conceito de son com o de left
e o conceito de next com o de right pode-se
obter uma árvore binária equivalente a uma
árvore qualquer. Graficamente o que se faz
é dar uma rotação horária de  /4 rd à
representação
104
Algoritmo de representação de uma árvore por
uma árvore binária equivalente
i) Reproduz-se a raiz da árvore original para
a raiz da árvore binária equivalente;
ii ) Para cada nó na árvore binária
equivalente considerar como filho mais
velho o filho mais velho, ou único, na
árvore original. Considerar como filho mais
novo, na árvore binária equivalente, o irmão
que sucede imediatamente o nó na árvore
original.
105
Representação de uma árvore por uma árvore
binária equivalente
Quando se utiliza uma árvore binária equivalente a
uma árvore qualquer, a correspondência entre
percursos nestas árvores é a seguinte:
O percurso pré-fixo da árvore original coincide
com o percurso pré-fixo da árvore binária
transformada. O percurso pós-fixo na árvore
original coincide com o percurso infixo na árvore
binária equivalente. O percurso infixo não tem
sentido senão em árvores binárias e, portanto, não
existe na árvore original.
106
Árvores binárias equivalentes
107
Árvores Binárias equivalentes
108
Árvores
Binárias
equivalentes
109