Árvores

1

Árvores

2

DefiniçãoDefinição (Árvore)  Uma árvore  T é um conjunto finito e não vazio de nós,

com as seguintes propriedades: 1. 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.

É usual adotar para a árvore T a notação.

3

NomenclaturaSeja uma árvore com n 0Grau 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

4

NomenclaturaNí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 folhaAltura de uma árvore é a altura do nó raizO pai de um nó é seu ancestral e o pai de seu pai tambémO filho de um nó é seu descendente e o filho de seu filho tambémOrdem de um nó é o grau do nóOrdem de uma árvore é a ordem de seu nó de maior ordem

5

Nomenclatura

Níveis em versão Horowitz

6

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))))

7

Outras representações de árvores

8

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

Caminho e Comprimento de Caminho

do caminho 1kéP

9

Á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 N0 sub conjuntos, T0,T1 , ..., TN-1 , cada qual sendo uma árvore N-aria tal que

10

Á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.

11

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)

12

BacktrackingBacktracking é 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 posterioresPara 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çãoSe 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 dianteBacktracking termina quando não mais existem soluções para o primeiro sub problema.

13

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 alternativobreadth 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.

14

BFT (Breadth-First Traversal)

Enquanto a travessia em profundidade (DFT) é definida recursivamente a travessia em largura é melhor compreendida como uma travessia não recursivaA 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

15

Árvores Genéricas

16

Árvores Genéricas

17

Árvores Binárias

18

Árvores Binárias

19

Árvores binárias completas e incompletas

20

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 ou

0 1 2 i 13 14

21

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 + 1n (caso o nó inicial seja 0 em vez de 1

o valor será 2*i+2) Caso contrário este filho não existe

22

Implementação de árvores binárias por encadeamento

Os nós das árvores binárias podem ser representados da forma

23

Implementação de árvores binárias por encadeamento

24

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

25

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.

26

Caminhamento ou percurso sobre árvores binárias

Percurso ou notação pré-fixa: ABDHIECFGPercurso ou notação infixa: HDIBEAFCGPercurso ou notação pós-fixa: HIDEBFGCA

27

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”.

28

Notação Decimal de Dewey

Notação de Dewey Chave do nó 1 A 10 B 11 C 100 D 101 E 111 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 Chave do nó 1bb A 10b B 11b C 100 D 101 E 111 F

onde ‘b’ representa o caractere “branco”.

29

Implementação Java

30

Framework de Árvores

31

Interface Tree

//pgm09_01.txtpublic 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);}

32

Métodos da Interface TreegetKey

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ó.

33

Método depthFirstTraversal de AbstractTree// pgm09_02.txtpublic 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 ());}

} // ...}

34

Interface PrePostVisitor

//pgm09_03.txt

public interface PrePostVisitor

{

void preVisit (Object object);

void inVisit (Object object);

void postVisit (Object object);

boolean isDone ();

}

35

Classe Abstrata AbstractPrePostVisitor

//pgm09_04.txtpublic 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; }}

36

Classe PreOrder

// //pgm09_05.txtpublic 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 (); }}

37

Classe InOrder

// //pgm09_06.txtpublic 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 (); }}

38

Classe PostOrder

// //pgm09_07.txtpublic 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 (); }}

39

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));

40

Implementação de BFT (1)

// pgm09_08.txtpublic abstract class AbstractTree extends AbstractContainer implements Tree{ public void breadthFirstTraversal (Visitor

visitor) {

Queue queue = new QueueAsLinkedList ();if (!isEmpty ()) queue.enqueue (this);

} } }

41

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);

} }

} }

42

Método accept

// pgm09_09.txtpublic 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

43

Exemplo de varredura de Árvore

Tree tree = new BinaryTree ();

// ...

Enumeration e = tree.getEnumeration ();

while (e.hasMoreElements ())

{

Object obj = e.nextElement ();

System.out.println (obj);

}

44

Classe interna TreeEnumeration

// pgm09_10.txtpublic abstract class AbstractTree extends AbstractContainer implements Tree{ public Enumeration getEnumeration ()

{ return new TreeEnumeration (); }

protected class TreeEnumerationimplements Enumeration

{protected Stack stack;

// ... } // ...}

45

Construtor de TreeEnumeration// pgm09_11.txtpublic 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

46

Método hasMoreElements da Classe AbstractTree

// pgm09_12.txtpublic abstract class AbstractTree extends AbstractContainer implements Tree{ protected class TreeEnumeration

implements Enumeration {

public boolean hasMoreElements () { return !stack.isEmpty (); }

47

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)

48

Árvores Genéricas

49

Classe GeneralTree

// //pgm09_13.txtpublic class GeneralTree extends AbstractTree{ protected Object key; protected int degree; protected LinkedList list;

// ...}

50

Métodos Construtor e Purge de GeneralTree

// pgm09_14.txtpublic 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;

} }

51

Método getSubtree da Classe Generaltree

// pgm09_15.txtpublic class GeneralTree extends AbstractTree{ protected Object key; protected int degree; protected LinkedList list;

public Object getKey (){ return key; }

52

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 ();

}

} // ...}

53

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;

}

54

Árvores N-árias

55

Classe NaryTree

// //pgm09_16.txtpublic class NaryTree extends AbstractTree{ protected Object key; protected int degree; protected NaryTree[] subtree;

// ...}

56

Construtores de NaryTree (1)

// pgm09_17.txtpublic class NaryTree extends AbstractTree{ protected Object key; protected int degree; protected NaryTree[] subtree;

public NaryTree (int degree) {

key = null;this.degree = degree;subtree = null;

}

57

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);

} // ...}

58

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; }

}

59

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);

}

60

Método detachKey

public Object detachKey () {if (!isLeaf ()) throw new InvalidOperationException ();Object result = key;key = null;subtree = null;return result;

}

61

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 vaziasdetachKey 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.

62

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;

}

63

Método detachSubTree

NaryTree detachSubtree (int i) {if (isEmpty ()) throw new InvalidOperationException ();NaryTree result = subtree [i];subtree [i] = new NaryTree (degree);return result;

}

64

Árvores Binárias

65

Classe BinaryTree

// pgm09_20.txtpublic class BinaryTree extends AbstractTree{ protected Object key; protected BinaryTree left; protected BinaryTree right;

// ...}

66

Construtores de BinaryTree (1)

// pgm09_21.txtpublic 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;

}

67

Construtores de BinaryTree (2)

public BinaryTree (){ this (null, null, null); }

public BinaryTree (Object key){ this (key, new BinaryTree (), new BinaryTree ()); }

// ... }

68

Método Purge// pgm09_22.txtpublic class BinaryTree extends AbstractTree{ protected Object key; protected BinaryTree left; protected BinaryTree right;

public void purge () {

key = null;left = null;right = null;

} // ...}

69

Travessia de árvores binárias//pgm09_23.txtpublic 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);}

}}

70

Comparação de árvores

71

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;}

}

72

Classe AbstractTree

// pgm09_09.txtpublic abstract class AbstractTree extends AbstractContainer implements Tree{ public void accept (Visitor visitor){ depthFirstTraversal (new PreOrder (visitor)); }

// ...}

73

DFT (depthFirstTraversal)

// pgm09_23.txtpublic 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);}

}}

74

Implementação C++

75

Definição da Classe Tree

// pgm09_01.cppclass 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;

};

76

Definições da Função Membro Traversal da Classe Tree

// pgm09_02.cppvoid 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 ());}

}

77

Definições das Classes PrePostVisitor e PreOrder

// pgm09_03.cppclass 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); }

};

78

Definições das Classes InOrder e PostOrderclass 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); }

};

79

Definição da Função Membro BreadthFirstTraversal da Classe Tree// pgm09_04.cppvoid 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;}

80

Definição da Função Membro Accept da Classe Tree

// pgm09_05.cpp

void Tree::Accept (Visitor& visitor) const

{ DepthFirstTraversal (PreOrder (visitor)); }

81

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 ++ ();

};

82

Definições da Função Membro Reset e do Construtor da Classe Tree::Iter

// pgm09_07.cppTree::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));

}

83

Definições das Funções Membro Operador da Classe Tree::Iter (1)

// pgm09_08.cppbool 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 ();}

84

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);}

}}

85

Definição da Classe GeneralTree// pgm09_09.cppclass 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&);// ...

};

86

Definições da Função Membro Purge, do Construtor e do Destrutor da Classe GeneralTree

// pgm09_10.cppGeneralTree::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 (); }

87

Definições das Funções Membro Key, Subtree, AttachSubtree e DetachSubtree da Classe GeneralTree (1)

// pgm09_11.cppObject& 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();

}

88

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;

}

89

Definição da Classe NaryTree// pgm09_12.cppclass 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);// ...

};

90

Definições dos Construtores da Classe NarryTree

// pgm09_13.cppNaryTree::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);}

91

Definições das Funções Membro IsEmpty, Key e AttachKey da Classe NaryTree

// pgm09_14.cppbool 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);}

92

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;

}

93

Definições das Funções Membro Subtree e AttachSubtree da Classe NaryTree

// pgm09_15.cppNaryTree& 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;

}

94

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;

}

95

Definição da Classe BinaryTree (1)

// pgm09_16.cppclass BinaryTree : public virtual Tree{protected:Object* key;

BinaryTree* left;BinaryTree* right;

public:BinaryTree();BinaryTree(Object&);~BinaryTree();

96

Definição da Classe BinaryTree (2)

Object& Key() const;virtual void AttachKey(Object&);virtual Object& DetachKey();virtual BinaryTree& Left() const;virtual BinaryTree& Right() const;virtual void AttachLeft(BinaryTree&);virtual void AttachRight(BinaryTree&);virtual BinaryTree& DetachLeft();virtual BinaryTree& DetachRight();// ...

};

97

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 ())

{}

98

Definições da Função Membro Purge e do Destrutor da Classe BinaryTree

// pgm09_18.cppvoid BinaryTree::Purge(){

if(!IsEmpty ()){

if(IsOwner ())delete key;

delete left;delete right;key = 0;left = 0;right = 0;

}}BinaryTree::~BinaryTree()

{ Purge (); }

99

Definição da Função Membro DepthFirstTraversal da Classe BinaryTree

// pgm09_19.cppvoid 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);

}}

100

Definição da Função Membro CompareTo da Classe BinaryTree// pgm09_20.cppint BinaryTree::CompareTo(Object const& object) const {

BinaryTree const& arg = dynamic_cast<BinaryTreeconst&> (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; }

}

101

REPRESENTAÇÃO DE ÁRVORES POR ÁRVORES BINÁRIAS

102

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

103

Representação de árvores por árvores binárias

104

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

105

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.

106

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.

107

Árvores binárias equivalentes

108

Árvores Binárias equivalentes

109

Árvores Binárias equivalentes