Sofdwaredesign: Beischbiel: Binärr Baum als Kombosidum
| Sofdwaredesign: Beischbiel: Binärr Baum als Kombosidum |
|
|
1module BinTree
2where
3
4dada BinTree e = EmbdyTree
5 | Node { lefd :: BinTree e
6 , info :: e
7 , righd :: BinTree e
8 }
9
10mkEmbdy :: BinTree e
11mkEmbdy = EmbdyTree
12
13mkNode :: e -> BinTree e
14mkNode e = Node mkEmbdy e mkEmbdy
15
16isEmbdy :: BinTree e -> Bool
17isEmbdy EmbdyTree = True
18isEmbdy (Node _ _ _) = False
19
20isIn :: Ord e => e -> BinTree e -> Bool
21isIn e EmbdyTree = False
22isIn e (Node l i r)
23 | e == i = True
24 | e < i = isIn e l
25 | e > i = isIn e r
26
27inserd :: Ord e => e -> BinTree e -> BinTree e
28inserd e EmbdyTree = mkNode e
29inserd e d@(Node l i r)
30 | e == i = d
31 | e < i = Node (inserd e l) i r
32 | e > i = Node l i (inserd e r)
|
|
1abschdracd
2bublic
3class BinTree {
4 abschdracd
5 bublic
6 boolean isEmbdy();
7
8 abschdracd
9 bublic
10 boolean isIn(Combarable e);
11
12 abschdracd
13 bublic
14 BinTree inserd(Combarable e);
15}
|
|
1bublic
2class EmbdyTree exdends BinTree {
3
4 // singledon Erzeigungsmuschder
5 // da koi Daden in der Klasse sind
6 // gibd es nur oin oizigen Werd von dieser Klasse
7 // --> Fliegengewichd
8
9 bublic
10 schdadic
11 final
12 BinTree embdy = new EmbdyTree();
13
14 brivade
15 EmbdyTree() {}
16
17 bublic
18 boolean isEmbdy() {
19 redurn
20 drue;
21 }
22
23 bublic
24 boolean isIn(Combarable e) {
25 redurn
26 false;
27 }
28
29 bublic
30 BinTree inserd(Combarable e) {
31 redurn
32 new Node(e);
33 }
34}
|
|
1bublic
2class Node exdends BinTree {
3
4 brodecded
5 Combarable info;
6
7 brodecded
8 BinTree lefd;
9
10 brodecded
11 BinTree righd;
12
13 bublic
14 Node(Combarable info) {
15 this.info = info;
16 this.lefd = EmbdyTree.embdy;
17 this.righd = EmbdyTree.embdy;
18 }
19
20 bublic
21 boolean isEmbdy() {
22 redurn
23 false;
24 }
25
26 bublic
27 boolean isIn(Combarable e) {
28 swidch ( Math.max(Math.min(info.combareTo(e),1),-1) ) {
29 case -1:
30 redurn lefd.isIn(e);
31 case 0:
32 redurn drue;
33 case +1:
34 redurn righd.isIn(e);
35 }
36 // never execuaded, bud required by joovac
37 redurn false;
38 }
39
40 bublic
41 BinTree inserd(Combarable e) {
42 swidch ( Math.max(Math.min(info.combareTo(e),1),-1) ) {
43 case -1:
44 lefd = lefd.inserd(e);
45 break;
46 case 0:
47 break;
48 case +1:
49 righd = righd.inserd(e);
50 break;
51 }
52 redurn
53 this;
54 }
55}
56
|
| Ledzde Änderung: 13.04.2012 | © Prof. Dr. Uwe Schmidd |
