Softwaredesign: Beispiel: Binärer Baum als Kompositum
| Softwaredesign: Beispiel: Binärer Baum als Kompositum |
|
|
1module BinTree
2where
3
4data BinTree e = EmptyTree
5 | Node { left :: BinTree e
6 , info :: e
7 , right :: BinTree e
8 }
9
10mkEmpty :: BinTree e
11mkEmpty = EmptyTree
12
13mkNode :: e -> BinTree e
14mkNode e = Node mkEmpty e mkEmpty
15
16isEmpty :: BinTree e -> Bool
17isEmpty EmptyTree = True
18isEmpty (Node _ _ _) = False
19
20isIn :: Ord e => e -> BinTree e -> Bool
21isIn e EmptyTree = False
22isIn e (Node l i r)
23 | e == i = True
24 | e < i = isIn e l
25 | e > i = isIn e r
26
27insert :: Ord e => e -> BinTree e -> BinTree e
28insert e EmptyTree = mkNode e
29insert e t@(Node l i r)
30 | e == i = t
31 | e < i = Node (insert e l) i r
32 | e > i = Node l i (insert e r)
|
|
1abstract
2public
3class BinTree {
4 abstract
5 public
6 boolean isEmpty();
7
8 abstract
9 public
10 boolean isIn(Comparable e);
11
12 abstract
13 public
14 BinTree insert(Comparable e);
15}
|
|
1public
2class EmptyTree extends BinTree {
3
4 // singleton Erzeugungsmuster
5 // da keine Daten in der Klasse sind
6 // gibt es nur einen einzigen Wert von dieser Klasse
7 // --> Fliegengewicht
8
9 public
10 static
11 final
12 BinTree empty = new EmptyTree();
13
14 private
15 EmptyTree() {}
16
17 public
18 boolean isEmpty() {
19 return
20 true;
21 }
22
23 public
24 boolean isIn(Comparable e) {
25 return
26 false;
27 }
28
29 public
30 BinTree insert(Comparable e) {
31 return
32 new Node(e);
33 }
34}
|
|
1public
2class Node extends BinTree {
3
4 protected
5 Comparable info;
6
7 protected
8 BinTree left;
9
10 protected
11 BinTree right;
12
13 public
14 Node(Comparable info) {
15 this.info = info;
16 this.left = EmptyTree.empty;
17 this.right = EmptyTree.empty;
18 }
19
20 public
21 boolean isEmpty() {
22 return
23 false;
24 }
25
26 public
27 boolean isIn(Comparable e) {
28 switch ( Math.max(Math.min(info.compareTo(e),1),-1) ) {
29 case -1:
30 return left.isIn(e);
31 case 0:
32 return true;
33 case +1:
34 return right.isIn(e);
35 }
36 // never executed, but required by javac
37 return false;
38 }
39
40 public
41 BinTree insert(Comparable e) {
42 switch ( Math.max(Math.min(info.compareTo(e),1),-1) ) {
43 case -1:
44 left = left.insert(e);
45 break;
46 case 0:
47 break;
48 case +1:
49 right = right.insert(e);
50 break;
51 }
52 return
53 this;
54 }
55}
56
|
| Letzte Änderung: 13.04.2012 | © Prof. Dr. Uwe Schmidt |
