Besucher für Bäume

(dieses Beispiel sinngemäß aus: Naftalin, Wadler: Java Generics and Collections, O'Reilly 2006.)

binäre Bäume mit:

• Blatt enthält Schlüssel
• innerer Knoten hat zwei Kinder (aber selbst keinen Schlüssel)

(Wdhlg. Kompositum)

interface Tree<K> { }
class Branch<K> implements Tree<K> {
    Tree<K> left; Tree<K> right;
}
class Leaf<K> implements Tree<K> {
    K key;
}

Aufgabe: Konstruktoren, toString, Testmethode

class Trees {
    // vollst. bin. Baum der Höhe h
    static Tree<Integer> full (int h);
}
System.out.println (Trees.full(1))
   ==> Branch{left=Leaf{key=0},right=Leaf{key=0}}

Besucher (mit Resultattyp R, für Bäume mit Schlüsseltyp K)

interface Tree<K> {
  interface Visitor<K, R> {
    R leaf (K key);
    R branch (R left, R right);
  }
  <R> R visit (Visitor<K,R> v);
}

Aufgabe: implementiere visit in Branch und Leaf

Benutzung: Anzahl der Blätter:

class Trees {
  static <K> int leaves (Tree<K> t) {
    return t.visit(new Tree.Visitor<K,Integer>() {
      public Integer branch(Integer left, Integer right) {
        return left + right;
      }
      public Integer leaf(K key) {
        return 1;
      }
    });
  }
}

Hinweis: am 1. 5. keine Vorlesung (Feiertag), am 2. 5. nur eine Übung (9:30) zu Fragen zu Entwurfsmustern.