Java 二叉树/访问者模式

Question

所以我真的能明白这一点，我想知道是否有人可以帮助我，这个程序的目标是使用访问者模式根据给定二叉树中的人名生成字符串列表，如果不是真的的话确定如何使用附加函数来执行此操作。我如何附加这个人及其 parent ？

import tester.Tester;

//Representation for an ancestor tree
interface IAT {
    <R> R accept(IATVisitor<R> visitor);

    //Append two lists
    IList<String> append(IList<String> l);
}
//-------------------------------------------------------------------------------------------------
//Unknown person
class Unknown implements IAT {
    Unknown() {
    }
    public <R> R accept(IATVisitor<R> visitor) {
        return visitor.visitUnknown(this);
    }
    //append two an unknown
    public IList<String> append(IList<String> l) {
        return l;
    }

}    
//-------------------------------------------------------------------------------------------------
//Representation for a person
class Person implements IAT {
    String name;
    int yob;
    boolean isMale;
    IAT mom;
    IAT dad;
    //Constructor
    Person(String name, int yob, boolean isMale, IAT mom, IAT dad) {
        this.name = name;
        this.yob = yob;
        this.isMale = isMale;
        this.mom = mom;
        this.dad = dad;
    }
    public <R> R accept(IATVisitor<R> visitor) {
        return visitor.visitPerson(this);
    }
    //append parent and children of tree
    public IList<String> append(IList<String> l) {
        //
    }

}
//-------------------------------------------------------------------------------------------------
interface IATVisitor<R> {
    R visitUnknown(Unknown u);
    R visitPerson(Person p);
}
//-------------------------------------------------------------------------------------------------
//IAT Visitor that returns a list of the names of all people
class IATVisitGetNames implements IATVisitor<IList<String>> {
    public IList<String> visitUnknown(Unknown u) {
        return new MT<String>();
    }
    public IList<String> visitPerson(Person p) {
        return new Cons<String>(p.name, new MT<String>());
    }
}

//Examples
class ExamplesIATV {
    //persons
    Unknown a = new Unknown();
    Person ralph = new Person("Ralph", 1995, true, a, a);
    Person kevin = new Person("Kevin", 1994, true, a , a);
    Person julia = new Person("Julia", 1991, false, ralph, a);
    Person lily = new Person("Lily", 1990, false, kevin, julia);
    Person who = new Person("?", 1738, false, lily, a);

    //Visitor
    IATVisitor<IList<String>> byName = new IATVisitGetNames(); 


    //test Vistior
    boolean testGetNames(Tester t) {
        return 
                t.checkExpect(who.accept(byName), new MT<String>());
    }
}

Answer 1

首先 - 您想要从树中收集所有名称。你需要遍历函数，例如:

public void traverse(Node root) {
   //do somesing with node
   System.out.println(root.value);
   if (root.left != null) {
      traverse(root.left);
   }
   if (root.right != null) {
      traverse(root.right);
   }
}

第二 - 您想要使用访客模式。维基百科怎么说:

Visitor - is a way of separating an algorithm from an object structure on which it operates.

所以访问者不适合遍历/迭代逻辑。对于访问者，我们只能在节点上封装一些逻辑:

public void traverseWithVisitor(Node root, IVisitor v) {
  root.accept(v);
  if (root.left != null) {
     traverseWithVisitor(root.left, v);
  }
  if (root.right != null) {
     traverseWithVisitor(root.right, v);
  }
}

现在将我们收集名称的逻辑封装在访问者中:

class AggregateNamesVisitor implements IVisitor {

   public List<Integer> names = new ArrayList<>();

   @Override
   public void visit(Node node) {
      names.add(node.value);
   }
}

我们可以这样使用它:

AggregateNamesVisitor aggregateVisitor = new AggregateNamesVisitor();
traverseWithVisitor(root, aggregateVisitor);
aggregateVisitor.names.forEach(name -> System.out.print(" " + name));