Softwaredesign: Beispiel: Binärer Baum mit Besucher
| Softwaredesign: Beispiel: Binärer Baum mit Besucher |
|
|
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;
}
}
|
|
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);
}
}
|
|
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);
}
}
|
|
public
class BinTreeVisitor {
void processEmpty(EmptyTree t) { }
void processNode(Node n) {
n.left .process(this);
n.right.process(this);
}
}
|
|
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
|
| Letzte Änderung: 03.01.2017 | © Prof. Dr. Uwe Schmidt |
