¿Diseñar para un árbol usando un patrón de visitante, cómo implementar diferentes tipos de recorrido?

7

Me han formulado una pregunta de diseño teórico con un ojo puesto en los patrones de GoF:

"Dado un diseño para un árbol que usa un patrón de visitante estándar, ¿cómo se vería su diseño para permitir que un usuario elija entre om pre-order, in-order o post-order transversales?"

Estoy pensando en simplemente dejar que el visitante sea, pero ceder el paso a un objeto Iterator siguiendo el patrón Iterator.

La idea sería implementar 3 iteradores que permitan el recorrido deseado. Tienen una interfaz y el Visitador solo necesita interactuar con esta interfaz, dándose a sí mismo como un argumento para el iterador que proporciona el recorrido. El usuario puede elegir qué iterador usar cuando le da uno al visitante.

¿Esto suena como una solución elegante? ¿Alguna idea mejor?

    
pregunta Sven 17.01.2014 - 21:17

2 respuestas

11

Una cosa acerca de los patrones de visitante es la idea errónea de que, de alguna manera, está ligada a una estructura similar a un árbol. Lo que está bastante mal. La pregunta suena como si estuviera haciendo eso. Así que lo primero sería arreglar este error. Y luego me gustaría exactamente como dijiste. Cree 3 iteradores diferentes uno para cada tipo de recorrido.

Pero esto depende de la complejidad del árbol. Si cada nodo tiene la misma colección específica de hijos, entonces es fácil. Los problemas comienzan cuando diferentes tipos de nodos tienen diferentes estructuras de hijos. Entonces el visitante comienza a tener sentido. Pero los diferentes tipos de orden de recorrido dejan de tener sentido, ya que solo funcionan para árboles n-arry, no para árboles con tipos arbitrarios de niños en cada nodo.

    
respondido por el Euphoric 17.01.2014 - 21:37
5

Tal vez me esté perdiendo algo, pero no necesita simplemente visitantes diferentes para cada uno de los tipos de recorrido, PreOrderTreeVisitor, InOrderTreeVisitor, PostOrderTreeVisitor con el método de visita específico para el tipo de recorrido. Probablemente desee que realicen alguna acción que pueda aplicarse a un nodo para que, en efecto, se conviertan en los iteradores del árbol.

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);
   }
}
    
respondido por el tvanfosson 17.01.2014 - 22:02

Lea otras preguntas en las etiquetas