homeSoftwaredesign Softwaredesign: Beispiel: Binärer Baum mit Besucher Prof. Dr. Uwe Schmidt FH Wedel

Beispiel: Binärer Baum mit Besucher

weiter

weiter

die abstrakte Klasse: BinTree

abstract
public
class BinTree {
 
  // der Aufruf eines Besuchers
 
  abstract
  public
  void process(BinTreeVisitor v);
 
  //--------------------
 
  // Besucher fuer die Testausgabe
 
  static
  class PreOrderTrace extends BinTreeVisitor {
 
    void processNode(Node n) {
        System.err.println(n.info);
        super.processNode(n);
    }
  };
 
  public
  void preOrderTrace() {
     process(new PreOrderTrace());
  }
 
  //--------------------
 
  // Besucher zur Berechnung der Kardinalitaet
 
  static
  class NodeCounter extends BinTreeVisitor {
    public
    int res = 0;
 
    void processNode(Node n) {
        ++res;
        super.processNode(n);
    }
  };
 
  public
  int card() {
 
    NodeCounter c = new NodeCounter();
 
    process(c);
 
    return
      c.res;
  }
 
}
weiter

weiter

die Klasse für den leeren Baum: EmptyTree

public
class EmptyTree extends BinTree {
 
  // singleton Erzeugungsmuster
  // da keine Daten in der Klasse sind
  // gibt es nur einen einzigen Wert von dieser Klasse
  // --> Fliegengewicht
 
  public
  static
  BinTree empty = new EmptyTree();
 
  private
  EmptyTree() {}
 
  //--------------------
 
  public
  void process(BinTreeVisitor v) {
    v.processEmpty(this);
  }
}
 
 
weiter

weiter

die Klasse für echte Knoten: Node

public
class Node extends BinTree  {
 
  Object info;
 
  BinTree left;
 
  BinTree right;
 
 
  //--------------------
 
  public
  Node(Object info) {
    this.info  = info;
    this.left  = EmptyTree.empty;
    this.right = EmptyTree.empty;
  }
 
  //--------------------
 
  public
  void process(BinTreeVisitor v) {
    v.processNode(this);
  }
 
}
 
weiter

weiter

die Basis-Besucherklasse: BinTreeVisitor

public
class BinTreeVisitor {
 
  void processEmpty(EmptyTree t) { }
 
  void processNode(Node n) {
    n.left .process(this);
    n.right.process(this);
  }
}
weiter

weiter

der Besucher in Haskell

   1module BinTree where
   2
   3data BinTree a = Empty
   4               | Node (BinTree a) a (BinTree a)
   5
   6-- ----------------------------------------
   7-- Besucher
   8
   9fold :: b ->
  10        (b -> a -> b -> b) ->
  11        BinTree a -> b
  12fold pe pn Empty        = pe
  13fold pe pn (Node l x r) = pn vl x vr
  14  where
  15    vl = fold pe pn l
  16    vr = fold pe pn r
  17
  18-- ----------------------------------------
  19--
  20-- 4 Methoden implementiert mit dem Besucher fold
  21    
  22size :: BinTree a -> Int
  23size = fold 0 (\ vl x vr -> vl + 1 + vr)
  24
  25sum :: Num a => BinTree a -> a
  26sum = fold 0 (\ vl x vr -> vl + x + vr)
  27
  28flatten :: BinTree a -> [a]
  29flatten = fold [] (\ vl x vr -> vl ++ [x] ++ vr)
  30
  31clone :: BinTree a -> BinTree a
  32clone = fold Empty Node
weiter
weiter

Letzte Änderung: 03.01.2017
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel