Travessias sobre BSTs

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