Progettazione per un albero utilizzando un modello di visitatore, come implementare diversi tipi di attraversamento?

7

Mi è stata posta una domanda di progettazione teorica con un occhio sui modelli GoF.:

"Dato un progetto per un albero che utilizza un modello di visitatore standard, come apparirà il tuo design per consentire all'utente di scegliere tra om pre-order, in-order o traversali post-ordine?"

Sto pensando di lasciare che sia il visitatore, ma di dare l'attraversamento a un oggetto Iterator seguendo il Pattern Iterator.

L'idea sarebbe quella di implementare 3 iteratori che consentano l'attraversamento desiderato. Hanno un'interfaccia e il visitatore ha solo bisogno di interagire con questa interfaccia, fornendosi come argomento per l'iteratore che fornisce l'attraversamento. L'utente può scegliere quale iteratore usare quando ne dà uno al visitatore.

Questo suona come una soluzione elegante? Qualche idea migliore?

    
posta Sven 17.01.2014 - 21:17
fonte

2 risposte

11

Una cosa su Visitor Patterns è l'idea sbagliata, che è in qualche modo legata alla struttura ad albero. Il che è assolutamente sbagliato. La domanda sembra come se stesse facendo proprio questo. Quindi la prima cosa sarebbe risolvere questo malinteso. E poi vorrei esattamente come hai detto tu. Crea 3 diversi iteratori per ogni tipo di attraversamento.

Ma questo dipende dalla complessità dell'albero. Se ogni nodo ha la stessa collezione di bambini specificata, allora è facile. I problemi iniziano quando diversi tipi di nodi hanno una diversa struttura di bambini. Allora il visitatore inizia a dare un senso. Ma i diversi tipi di ordine trasversale non hanno più senso, perché funzionano solo per gli alberi n-arry, non per gli alberi con tipi arbitrari di bambini in ciascun nodo.

    
risposta data 17.01.2014 - 21:37
fonte
5

Forse mi manca qualcosa ma non hai semplicemente bisogno di visitatori diversi per ognuno dei tipi di attraversamento, PreOrderTreeVisitor, InOrderTreeVisitor, PostOrderTreeVisitor con il metodo di visita specifico per il tipo di attraversamento. Probabilmente vuoi che eseguano un'azione che possa essere applicata a un nodo in modo che diventino effettivamente gli iteratori sopra l'albero.

interface ITreeVisitor {
   void visit(ITreeNode node);
}

interface ITreeNode {
   ITreeNode getLeft();
   ITreeNode getRight();
   int getValue();
   void accept(ITreeVisitor visitor);
}

interface IAction {
   void do(ITreeNode);
}

class TreeNode implements ITreeNode {
   ...
   public void accept(ITreeVisitor vistor) {
      visitor.visit(this);
   }
}

class PreOrderTreeVisitor implements ITreeVisitor {

   private IAction action;

   public PreOrderTreeVisitor(IAction action) {
        this.action = action;
   }

   public void visit(ITreeNode node) {

       action.do(node);

       ITreeNode left = node.getLeft();
       if (left != null) left.accept(this);

       ITreeNode right = node.getRight();
       if (right != null) right.accept(this);
   }
}
    
risposta data 17.01.2014 - 22:02
fonte

Leggi altre domande sui tag