Root at 08:36, 19 May 2005

2005-05-19T08:36:10Z

New page

== Introdução ==

== Travessias Recursivas ==

=== Travessia ''pre-order'' ===

void '''traverse'''(link h, void (*'''visit''')(link)) {
if (!h) return;
(*'''visit''')(h);
'''traverse'''(h->l);
'''traverse'''(h->r);
}

=== Travessia ''in-order'' ===

void '''traverse'''(link h, void (*'''visit''')(link)) {
if (!h) return;
'''traverse'''(h->l);
(*'''visit''')(h);
'''traverse'''(h->r);
}

=== Travessia ''post-order'' ===

void '''traverse'''(link h, void (*'''visit''')(link)) {
if (!h) return;
'''traverse'''(h->l);
'''traverse'''(h->r);
(*'''visit''')(h);
}

== Travessias Não Recursivas ==

=== Travessia ''pre-order'' ===

Utiliza uma estrutura de dados (pilha) para manter as partes não processadas.

void '''traverse'''(link h, void (*'''visit''')(link)) {
'''STACKinit'''(max);
'''STACKpush'''(h);
while (!'''STACKempty'''()) {
(*'''visit''')(h = '''STACKpop'''());
if (h->r != NULL) '''STACKpush'''(h->r);
if (h->l != NULL) '''STACKpush'''(h->l);
}
}

=== Travessia ''level-order'' ===

Utiliza uma estrutura de dados (fila) para manter as partes não processadas.

void traverse(link h, void (*'''visit''')(link)) {
'''QUEUEinit'''(max);
'''QUEUEput'''(h);
while (!'''QUEUEempty'''()) {
(*'''visit''')(h = '''QUEUEget'''());
if (h->r != NULL) '''QUEUEput'''(h->l);
if (h->l != NULL) '''QUEUEput'''(h->r);
}
}

Travessias sobre BSTs - Revision history

Root at 08:36, 19 May 2005