-
Notifications
You must be signed in to change notification settings - Fork 0
/
Trees.html
1634 lines (1614 loc) · 85.4 KB
/
Trees.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html><html lang="de"><head>
<title>Variationen zum Thema: Algorithmen</title>
<meta name="title" content="Variationen zum Thema: Algorithmen">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta charset="UTF-8">
<meta name="description" content="Eine Einführung anhand von Beispielen">
<meta name="keywords" content="Java,Algorithmen,Datenstrukturen">
<meta name="author" content="Ralph P. Lano">
<meta name="robots" content="index,follow">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" type="text/css" href="book.css">
</head>
<body><center>
<div id="wrap">
<ul class="sidenav">
<p><a href="index.html">Variationen zum Thema</a><a href="index.html">Algorithmen</a></p>
<li><a href="Introduction.html">Introduction</a></li>
<li><a href="Lists.html">Lists</a></li>
<li><a href="Maps.html">Maps</a></li>
<li><a href="Recursion.html">Recursion</a></li>
<li><a href="Algorithms.html">Algorithms</a></li>
<li><a href="Sorting.html">Sorting</a></li>
<li><a href="Trees.html" class="active">Trees</a></li>
<li><a href="Graphs.html">Graphs</a></li>
<li><a href="Text.html">Text</a></li>
<li><a href="Techniques.html">Techniques</a></li>
</ul>
<div class="content"><p>
<img src="images/TreeNice.png" style="display: block; margin-left: auto; margin-right: auto; width: 215px; height: 175px;" /></p>
<h1>
Trees</h1>
<p>
Ich liebe Bäume. In meinem Garten habe ich ein paar Kirschbäume, einen Maulbeerbaum, einen Mispelbaum, natürlich ein paar Äpfelbäume, einen kleinen Pfirsich-, und einen Feigenbaum, der jetzt schon drei Winter überlebt hat. Aber da das hier kein Buch für Hobbygärtner ist sondern für angehende Algorithmiker, geht es in diesem Kapitel um die Datenstruktur Baum, auf Englisch <em>Tree</em>. </p>
<p>
Bei Trees handelt es sich um eine hierarchische Datenstruktur, die wenn man sie ausdruckt etwas an Bäume erinnert, daher der Name. So wie es bei richtigen Bäumen ganz viele Arten von Bäumen gibt, ist das auch bei der Datenstruktur, da gibt es BinaryTrees, QuadTrees, Splay Trees, Red-Black Trees, usw. Und je nachdem welches Obst man essen möchte muss man auch die richtige Baumart auswählen. Darum geht es in diesem Kapitel, um das Hegen und Pflegen von Bäumen.</p>
<p>
.</p>
<h2>
Examples</h2>
<p>
Beginnen wir mit ein paar Beispielen: die Dateien und Verzeichnisse auf unserem Computer sind ein Baum. Wenn wir unsere Erde in Kontinente, Staaten, Bundesländer, usw. unterteilen, dann ist das auch ein Baum. Oder z.B. die Züge in einem Spiel, wie z.B. Tic-Tac-Toe, bilden auch eine Baumstruktur:</p>
<table align="center" border="0" cellpadding="10" cellspacing="10" style="width: 100%;">
<tbody>
<tr>
<td style="text-align: center; vertical-align: top;">
<img src="images/FileSystem.png" style="width: 110px; height: 155px;" /></td>
<td style="text-align: center; vertical-align: top;">
<img src="images/Countries.png" style="width: 255px; height: 99px;" /></td>
<td style="text-align: center; vertical-align: middle;">
<img src="images/TicTacToe.png" style="width: 218px; height: 192px;" /></td>
</tr>
</tbody>
</table>
<p>
Es gibt noch viele weitere Beispiele:</p>
<ul>
<li>
Familienbäume, also gemeint sind Stammbäume.</li>
<li>
Ein Buch bestehend aus Titel, Inhaltsverzeichnis, Kapiteln, Unterkapiteln und Paragraphen.</li>
<li>
Entscheidungsbäume, basierend auf mehreren konsekutiven Ja/Nein Fragen kann man eine Entscheidung oder Diagnose treffen.</li>
<li>
Mathematische arithmetische Ausdrücke haben eine Baumstruktur.</li>
<li>
Und viele Spiele lassen sich in eine Baumstruktur abbilden.</li>
</ul>
<p>
Allerdings nicht alles was wie ein Baum aussieht ist wirklich ein Baum, deswegen wollen wir erst einmal definieren, was wir unter einem Baum verstehen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/a1367c64-6a62-4937-bf05-a9c5cc3e3ede.png" style="width: 200px; height: 130px; float: right;" />Terminology</h2>
<p>
Ein Baum ist wie eine Eltern-Kind Beziehung. Dabei kann das Elternteil mehrere Kinder haben, aber ein Kind kann nie mehr als ein Elternteil haben. Das mag etwas ungewöhnlich erscheinen, aber so ist die Definition. </p>
<p>
Ein Baum besteht aus Knoten, <em>Nodes</em> genannt, und Verbindungen, die man <em>Edges</em> nennt. Des weiteren verwendet man folgende Begriffe:</p>
<ul>
<li>
Root: die Wurzel ist der Knoten der kein Elternteil hat. In jedem Baum kann es nur ein Wurzel geben.</li>
<li>
Internal Node: das sind Knoten die selbst Kinder haben.</li>
<li>
External Node (Leaf): das sind Knoten die keine Kinder haben.</li>
</ul>
<p>
<img alt="" src="images/cda61fe6-0315-497e-88cc-b5d318d8f32f.png" style="width: 200px; height: 158px; float: right;" />In Anlehnung an Familienbäume, werden dann auch die folgenden Bezeichnungen verwendet:</p>
<ul>
<li>
Ancestors: sind die Vorfahren.</li>
<li>
Descendants: sind die Nachfahren, also Kinder und Kinderskinder.</li>
<li>
Siblings: nennt man die Geschwister eines Knotens.</li>
<li>
Subtree: ein Unterbaum oder Teilbaum, ist ein Teil eines größeren Baumes, der selbst wieder ein Baum ist.</li>
<li>
Depth: bezieht sich auf einen Knoten und ist die Distanz dieses Knotens zum Wurzelknoten. Der Wurzelknoten hat Depth von 0.</li>
<li>
Height: ist das Gegenstück zur Depth, und bezieht sich auf die externen Knoten. Externe Knoten haben eine Height von 0. Die Height des Baumes entspricht dann der Height des Wurzelknotens.</li>
</ul>
<p>
Schließlich unterscheidet man noch zwischen geordneten und ungeordneten Bäumen: das bezieht sich auf die Kinder: gibt es da eine Reihenfolge (wie z.B. deren Alter) oder gibt es da keine. Wir werden uns nur mit geordneten Bäumen beschäftigen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Node.png" style="width: 145px; height: 129px; float: right;" />Nodes</h2>
<p>
Die Datenstruktur <em>Node</em> besteht aus folgenden Teilen: es gibt eine Referenz auf das Elternteil, es gibt Referenzen auf mögliche Kinder und es gibt eine Referenz auf das <em>Element</em>, das sind die Daten die im Knoten gespeichert werden. Die Datenstruktur <em>Node</em> unterstützt die folgenden, lesenden Methoden:</p>
<ul>
<li>
<strong>isRoot():</strong> gibt an ob es sich bei dem Knoten um den Wurzelknoten handelt;</li>
<li>
<strong>isInternal():</strong> wenn ein Knoten Kinder hat, dann ist es ein interner Knoten;</li>
<li>
<strong>isExternal():</strong> wenn ein Knoten keine Kinder hat, dann ist es ein externer Knoten;</li>
<li>
<strong>getElement():</strong> gibt das Element zurück, das in diesem Knoten gespeichert ist;</li>
<li>
<strong>getParent():</strong> gibt den übergeordneten Knoten dieses Knotens zurück;</li>
<li>
<strong>getChildren():</strong> gibt die untergeordneten Knoten dieses Knotens zurück.</li>
</ul>
<p>
Darüber hinaus kann ein Knoten auch Schreibmethoden haben:</p>
<ul>
<li>
<strong>setElement(E element):</strong> setzt das Element dieses Knotens auf einen neuen Wert;</li>
<li>
<strong>addChild(Node<E> node):</strong> fügt diesem Knoten ein Kind hinzu;</li>
<li>
<strong>removeChild(Node<E> node):</strong> entfernt das gegebene Kind von diesem Knotens, wenn dieses Kind wiederum Kinder hat, werden diese auch mit entfernt!</li>
</ul>
<p>
Mit diesen Methoden können wir Strukturen von Knoten zusammen bauen, in dem wir Information in ihnen speichern und sie dann in einer Struktur verbinden. Als Beispiel wollen wir den Baum der ersten biblischen Familie aufbauen:</p>
<pre style="margin-left: 40px;">
Node<String> adam = new Node<String>("Adam");
Node<String> abel = new Node<String>("Abel");
adam.addChild(abel);
Node<String> cain = new Node<String>("Cain");
adam.addChild(cain);
System.out.println(adam.isRoot());
System.out.println(adam.getChildren());
adam.removeChild(abel); // Abel was killed by his brother</pre>
<p>
.</p>
<h2>
<img alt="" src="images/OrderedTree.png" style="width: 200px; height: 162px; float: right;" />Ordered Trees</h2>
<p>
Wenn wir anfangen Knoten zu verbinden, bekommen wir Bäume. Bäume bestehen aus Knoten. Obwohl wir im Prinzip schon mit einem Haufen von Knoten ganz gut arbeiten könnten, bietet die übergreifende <em>Tree</em> Datenstruktur einige zusätzliche, nützliche Funktionen:</p>
<ul>
<li>
<strong>root():</strong> gibt den Wurzelknoten des Baums zurück;</li>
<li>
<strong>size():</strong> gibt die Größe des Baumes, d.h. die Anzahl der Knoten im gesamten Baumes;</li>
<li>
<strong>height():</strong> gibt die Höhe eines Baumes;</li>
<li>
<strong>elements():</strong> gibt alle Knoten des Baumes als Collection zurück;</li>
<li>
<strong>preOrder():</strong> eine Art, einen Baum zu durchqueren;</li>
<li>
<strong>postOrder():</strong> eine andere Möglichkeit, einen Baum zu durchlaufen;</li>
<li>
<strong>levelOrder():</strong> noch eine andere Art, durch einen Baum zu iterieren.</li>
</ul>
<p>
Diese Methoden sind ganz praktisch wie wir in Kürze sehen werden. Verwendet wird die Datenstruktur wie folgt:</p>
<pre style="margin-left: 40px;">
Tree<String> humans = new Tree<String>(adam);
System.out.println(humans.size());
System.out.println(humans.elements());
humans.preOrder();</pre>
<p>
Besonders die Traversal, also die Iterationsmethoden werden für uns sehr wichtig werden. Deswegen betrachten wir diese jetzt ein wenig näher.</p>
<p>
.</p>
<h2>
<img alt="" src="images/PreOrderTraversal2.png" style="width: 200px; height: 144px; float: right;" />Pre-Order Traversal</h2>
<p>
Wenn wir durch alle Elemente eines Baumes iterieren wollen, haben wir mehrere Möglichkeiten, eine davon ist das <em>Pre-Order</em> Traversal. Bei dieser Iteration wird der Knoten selbst vor seinen Kindern besucht.</p>
<pre style="margin-left: 40px;">
void preOrder(node) {
<span style="color:#0000ff;">visit(node)</span>
for (child of node) {
preOrder(child)
}
}
</pre>
<p>
Mögliche Anwendungen für dieser Art von Traversal sind:</p>
<ul>
<li>
das Drucken eines strukturierten Dokuments (wie z.B. eines Buchs);</li>
<li>
einen Baum als String auszugeben (z.B. new OrderedTreeParser().createStringFromTree());</li>
<li>
oder einen Baum zu malen (FibonacciTree).</li>
</ul>
<p>
.</p>
<h2>
<img alt="" src="images/PostOrderTraversal.png" style="width: 200px; height: 141px; float: right;" />Post-Order Traversal</h2>
<p>
Wenden wir uns der nächsten Form der Iteration zu, dem <em>Post-Order</em> Traversal. In dieser wird der Knoten erst nach seinen Kinder besucht.</p>
<pre style="margin-left: 40px;">
void postOrder(node) {
for (child of node) {
postOrder(child)
}
<span style="color:#0000ff;">visit(p)</span>
} </pre>
<p>
Mögliche Anwendungen dieser Art von Durchquerung sind:</p>
<ul>
<li>
das Berechnen des Speicherplatzes von Dateien in Verzeichnissen und deren Unterverzeichnissen;</li>
<li>
und das Auswerten von arithmetischen Ausdrücken.</li>
</ul>
<p>
.</p>
<h2>
<img alt="" src="images/LevelOrderTraversal.png" style="width: 200px; height: 142px; float: right;" />Level-Order Traversal</h2>
<p>
Als letzte wichtige Form der Iteration durch geordente Bäume betrachten wir kurz das <em>Level-Order</em> Traversal. Hier wird zu erst der Wurzelknoten besucht, danach all seine Kinder, dann kommen die Enkelkinder, usw.. </p>
<pre style="margin-left: 40px;">
void levelOrder(node, level) {
if (node == null) {
return;
} else if (level == 1) {
<span style="color:#0000ff;">visit(node);</span>
} else if (level > 1) {
for (child of node) {
levelOrder(child, level - 1);
}
}
}</pre>
<p>
Diese Art von Traversal wird verwendet</p>
<ul>
<li>
um z.B. durch einen Baum hierarchisch von oben nach unten durch zu iterieren.</li>
</ul>
<p>
.</p>
<h2>
<img alt="" src="images/BinaryTree.png" style="width: 200px; height: 235px; float: right;" />Binary Trees</h2>
<p>
Eine besondere Form von Bäumen sind binäre Bäume:</p>
<ul>
<li>
Jeder Knoten hat höchstens zwei Kinder und</li>
<li>
die Kinder haben eine Ordnung, d.h. es gibt ein linkes und ein rechtes Kind.</li>
</ul>
<p>
Wenn ein binärer Baum keine oder genau zwei Kinder hat, dann nennt man ihn auch Proper Binary Tree.</p>
<p>
Ein binärer Baum, <em>BinaryTree</em>, besteht aus binären Knoten, <em>BinaryNode</em>. Binäre Knoten haben die gleichen Operationen wie normale Knoten, nur zusätzlich haben sie noch folgende Methoden:</p>
<ul>
<li>
<strong>hasLeft():</strong> true, wenn dieser Knoten ein Kind auf der linken Seite hat;</li>
<li>
<strong>hasRight():</strong> true, wenn dieser Knoten ein Kind auf der rechten Seite hat;</li>
<li>
<strong>getLeft():</strong> gibt das Kind auf der linken Seite dieses Knotens zurück;</li>
<li>
<strong>getRight():</strong> gibt das Kind auf der rechten Seite dieses Knotens zurück;</li>
<li>
<strong>setLeft(BinaryNode<E> node):</strong> fügt ein Kind auf der linken Seite ein;</li>
<li>
<strong>setRight(BinaryNode<E> node):</strong> fügt ein Kind auf der rechten Seite ein;</li>
<li>
<strong>removeLeft():</strong> löscht das Kind auf der linken Seite;</li>
<li>
<strong>removeRight():</strong> löscht das Kind auf der rechten Seite.</li>
</ul>
<p>
Zusätzlich zu den Methoden, die für generische Bäume definiert sind, haben binäre Bäume die folgende Operation,</p>
<ul>
<li>
<strong>inOrder():</strong> eine vierte Möglichkeit, einen Baum zu durchqueren, funktioniert aber nur für binäre Bäume.</li>
</ul>
<p>
Um zu sehen, wie wir mit binären Bäumen arbeiten, können wir wieder unsere erste Familie betrachten:</p>
<pre style="margin-left: 40px;">
BinaryNode<String> adam = new BinaryNode<String>("Adam");
BinaryNode<String> cain = new BinaryNode<String>("Cain");
cain.setLeft(new BinaryNode<String>("Enoch"));
adam.setLeft(cain);
BinaryNode<String> abel = new BinaryNode<String>("Abel");
adam.setRight(abel);
BinaryTree<String> humans = new BinaryTree<String>(adam);
System.out.println(humans);
System.out.println(humans.size());
System.out.println(humans.height());
humans.inOrder();</pre>
<p>
Wie wir sehen werden, haben binäre Bäume viele Anwendungen:</p>
<ul>
<li>
Arithmetische Ausdrücke,</li>
<li>
Entscheidungsprozesse und</li>
<li>
Suchen.</li>
</ul>
<p>
Binäre Bäume sind so wichtig, denn sie haben viele schöne Eigenschaften. Darüber hinaus gibt es einen Satz der besagt, dass alle Bäume in binäre Bäume umgewandelt werden können [16]. Das ist ganz praktisch.</p>
<p>
.</p>
<h2>
<img alt="" src="images/1520c4d0-2081-4fb5-80c9-829f4c100d22.png" style="width: 200px; height: 144px; float: right;" />In-Order Traversal</h2>
<p>
Das <em>In-Order</em> Traversal funktioniert nur mit binären Bäumen. Bei ihm wird zuerst die linke Seite besucht, dann wird der Knoten selbst besucht, und danach die rechte Seite. D.h. ein Knoten wird nach seinem linken Teilbaum, aber vor seinem rechten Teilbaum besucht:</p>
<pre style="margin-left: 40px;">
void inOrder(p) {
if hasLeft(p) {
inOrder( left(p) );
}
<span style="color:#0000ff;"> visit(p);</span>
if hasRight(p) {
inOrder( right(p) );
}
}
</pre>
<p>
Mögliche Anwendungen dieser Art von Durchquerung sind:</p>
<ul>
<li>
Das Drucken arithmetischer Ausdrücke und andere Binärbäume in einer hübschen Form;</li>
<li>
Wenn man mit diesem Traversal binäre Suchbäume durchläuft, werden die Elemente in sortierter Reihenfolge ausgegeben (BinarySearchTree.main()).</li>
</ul>
<p>
.</p>
<h2>
<img alt="" src="images/b2d59ce0-48eb-4d9a-82ab-8a4e93035194.png" style="width: 200px; height: 154px; float: right;" />Arithmetic Expression Tree</h2>
<p>
Eine wichtige Anwendung von binären Bäumen ist der arithmetische Ausdruck. Hier repräsentieren interne Knoten Operatoren und externe Knoten entsprechen den Operanden. Zum Beispiel, aus dem Ausdruck</p>
<pre>
5 + ( 3 - 4 ) * 2 - 3 * 4
</pre>
<p>
wird der binäre Baum rechts. Für arithmetische Ausdrucksbäume haben zwei Arten von Traversals eine besondere Bedeutung:</p>
<ul>
<li>
Post-Traversal kann verwendet werden, um arithmetische Ausdrücke zu berechnen;</li>
<li>
In-Order-Traversal kann verwendet werden, um arithmetische Ausdrücke schön darzustellen oder zu drucken.</li>
</ul>
<p>
.</p>
<h2>
<img alt="" src="images/PilotChecklist.png" style="width: 200px; height: 130px; float: right;" />Decision Trees</h2>
<p>
Eine weitere schöne Anwendung eines binären Baumes ist der Entscheidungsbaum [15]. Bei einem Entscheidungsbaum sind interne Knoten Fragen. Bei einer Ja-Antwort folgt man dann der Frage auf der linken Seite, bei einer Nein-Antwort folgt man der Frage auf der rechten Seite. Externe Knoten entsprechen dann den Entscheidungen die zu treffen sind. Beispiele beinhalten:</p>
<ul>
<li>
Checkliste für ein Flugzeug vor dem Start;</li>
<li>
Was man essen soll;</li>
<li>
Welchen Sortieralgorithmus man verwenden soll;</li>
<li>
Welche Programmiersprache sich für ein bestimmtes Problem am besten eignet.</li>
</ul>
<p>
.</p>
<h2>
<img alt="" src="images/07b4edea-c3d4-40f4-8ddb-871ccacc84e0.png" style="width: 200px; height: 215px; float: right;" />Binary Search Trees</h2>
<p>
Eine sehr prominenten Anwendung von Bäumen ist die der Suche. Der <em>Binary Search Tree</em> ist dabei ein Beispiel das einen binären Baum als Datenstruktur verwendet. Dabei werden:</p>
<ul>
<li>
interne Knoten verwendet um Einträge zu speichern;</li>
<li>
neue Einträge, je nachdem ob sie größer oder kleiner sind, in den rechten oder linken Teilbaum eingefügt.</li>
</ul>
<p>
Bei dieser Baumart werden die "Blätter", also die externen Knoten, gar nicht genutzt. Betrachten wir folgendes Beispiel:</p>
<ul>
<li>
<b>Create:</b> Beginnend mit einem leeren Suchbaum, fügen wir nacheinander die folgenden Zahlen ein: 44, 88, 17, 32, 97, 65, 28, 82, 29, 76, 54, 80. Es entsteht der Baum rechts.</li>
<li>
<b>Find:</b> Wir versuchen nach den Einträgen 76 und 25 zu suchen indem wir den Baum von oben nach unten durchgehen. Dabei vergleichen wir unsere Suchzahl, z.B. die 76 jeweils mit dem momentanen Knoten, und folgen der linken Seite wenn unsere Suchzahl größer ist und der rechten Seite wenn sie kleiner ist.</li>
<li>
<b>Insert:</b> Als nächstes fügen wir die Zahl 78 in den Baum ein.</li>
<li>
<b>Remove:</b> Das Entfernen von Elemente ist die schwierigste Operation. Versuchen wir die Zahlen 32 und 65 zu entfernen. Erst müssen wir die Zahl die wir suchen im Baum finden. Wenn die Suchzahl gar nicht im Baum ist dann ist das einfach. Auch wenn die Suchzahl ganz unten ist, dann löschen wir einfach diesen Knoten aus unserem Baum. Wenn unsere Suchzahl allerdings irgendwo mitten im Baum ist, und vielleicht auch linke und rechte Teilbäume unter sich hat, dann wird das etwas schwieriger. Die einfache Lösung ist einfach diese Teilbäume zu nehmen und ganz neu in den Baum einzufügen. Das ist allerdings nicht besonders schnell.</li>
</ul>
<p>
Was die Laufzeiten angeht kann man zeigen, dass das Suchen, Einfügen und Entfernen proportional zur Höhe des Baumes dauert, für einen ausgewogenen (well-balanced) Baum bedeutet dies O(log n).</p>
<p>
Es müsste eigentlich klar sein, dass eine der effektivsten Lösungen für das NumberGuessGame nichts anderes als ein binärer Suchbaum ist.</p>
<p>
.</p>
<h2>
<img alt="" src="images/BinarySearchUsingTreeSet.png" style="width: 200px; height: 100px; float: right;" />TreeSet</h2>
<p>
Wir können zwar unsere eigene Klasse schreiben um die Binäre Suche umzusetzen (was wir später auch tun werden), aber warum das Rad neu erfinden, wenn es schon jemand anderes erfunden hat? In Java gibt es eine Klasse namens <em>TreeSet</em>. Und die macht genau was wir eigentlich wollen. Hier eine Umsetzung der Aufgabe von gerade eben:</p>
<pre style="margin-left: 40px;">
int[] nrs = { 44, 88, 17, 32, 97, 65, 28, 82, 29, 76, 54, 80 };
// create tree and insert
TreeSet<Integer> searchTree = new TreeSet<Integer>();
for (int i = 0; i < nrs.length; i++) {
searchTree.add(nrs[i]);
}
// find the entries: 76 and 25
println("Contains 76: " + searchTree.contains(76));
println("Contains 25: " + searchTree.contains(25));
// insert the number 78
searchTree.add(78);
// remove numbers 32 and 65
searchTree.remove(32);
searchTree.remove(65);
// print whole tree
println("List content of tree: ");
for (Integer nr : searchTree) {
print(nr + ",");
}
</pre>
<p>
Der Vorteil des TreeSets ist, dass seine Einträge sortiert sind. Dabei passiert das Sortieren beim Einfügen neuer Elemente. Wenn wir nach einem Eintrag suchen, dann dauert das O( log n ), ist also langsamer als beim HashSet, dafür ist es aber sortiert. Intern verwendet das TreeSet die <em>Red-BlackTrees</em> als Datenstruktur. Das Gleiche gilt auch für die TreeMap.</p>
<p>
.</p>
<h2>
Other Trees</h2>
<p>
Wir haben uns bisher nur mit Trees beschäftigt die auf einer Verlinkung der Knoten beruhen. In den Projekten werden wir noch ein Beispiel sehen, das auf Arrays beruht. Es gibt aber noch ganz viele andere Implementierungen für die Tree Datenstruktur, z.B. sind das:</p>
<ul>
<li>
QuadTrees</li>
<li>
AVL Trees</li>
<li>
Splay Trees</li>
<li>
(2,4) Trees</li>
<li>
Red-Black Trees</li>
<li>
B-Trees</li>
</ul>
<p>
Ähnlich wie bei den Sortierverfahren hat jede so ihre Stärken und Schwächen. Aber was der QuickSort für die Sortieralgorithmen ist, das ist der Red-Black Tree für Bäume.</p>
<p>
.</p>
<hr />
<h1>
Review</h1>
<p>
In diesem Kapitel haben wir uns mit Bäumen angefreundet. Dabei haben wir geordnete Bäume und binäre Bäume gesehen und wir haben von den verschiedenen Traversal-Methoden gehört. Und der Binary Search Tree ist uns kurz über den Weg gelaufen.</p>
<p>
.</p>
<hr />
<h1>
Projekte</h1>
<p>
Es gibt überraschend viele Anwendungen für Bäume. Sie lassen sich sehr gut dazu verwenden um hierarchische Strukturen abzubilden. Man kann sie für Entscheidungsbäume nutzen. Häufig sind sie das Resultat von Parsern, man kann mit ihnen suchen und sortieren, und sowohl für die Auswertung von arithmetischen Ausdrücken, als auch für Programmiersprachen stellen sie sich als äusserst nützlich heraus.</p>
<p>
.</p>
<h2>
<img alt="" src="images/UniversityHierarchy.png" style="width: 200px; height: 114px; float: right;" />University</h2>
<p>
Mit Bäumen kann man z.B. Hierarchien in Unternehmen abbilden. Nehmen wir eine Hochschule. Dort gibt es einen Präsidenten, für jede Fakultät einen Dekan, und dann gibt es da noch Professoren und Tutoren. Zunächst legen wir für jedes Mitglied der Hierarchie einen Knoten an.</p>
<pre style="margin-left: 40px;">
OrderedNode<String> president = new OrderedNode<String>("president");
OrderedNode<String> dean_A = new OrderedNode<String>("dean_A");
OrderedNode<String> dean_B = new OrderedNode<String>("dean_B");
OrderedNode<String> prof_A = new OrderedNode<String>("prof_A");
...
</pre>
<p>
Dann verbinden wir die Knoten miteinander:</p>
<pre style="margin-left: 40px;">
dean_A.setParent(president);
...
prof_B.setParent(dean_A);
...
tutor_B.setParent(prof_B);
tutor_C.setParent(prof_B);</pre>
<p>
<img alt="" src="images/University2.png" style="width: 200px; height: 250px; float: right;" />Und schließlich machen wir daraus einen Baum:</p>
<pre style="margin-left: 40px;">
OrderedTree<String> university = new OrderedTree<String>(president);</pre>
<p>
An den Baum können wir jetzt ein paar Fragen stellen. Z.B. wieviele Angestellte gibt es an der Uni:</p>
<pre style="margin-left: 40px;">
println("Number of employees: " + university.<span style="color:#0000ff;">size()</span>);</pre>
<p>
Oder wieviele Hierarchieebenen gibt es:</p>
<pre style="margin-left: 40px;">
println("Number of hierarchy levels: " + university.<span style="color:#0000ff;">height()</span>);</pre>
<p>
Wir können auch alle Angestellten auflisten die es an der Hochschule gibt:</p>
<pre style="margin-left: 40px;">
println("List of all employees: " + university.elements());</pre>
<p>
Wir können auch fragen, wer der Chef von <em>prof_B</em> ist:</p>
<pre style="margin-left: 40px;">
println("Boss of prof_B: " + prof_B.<span style="color:#0000ff;">getParent()</span>.getElement());</pre>
<p>
oder wer die Angestellten von <em>dean_B</em> sind:</p>
<pre style="margin-left: 40px;">
println("Employees of dean_B: " + dean_B.getChildren());</pre>
<p>
wobei hier allerdings nur die direkten Kinder aufgelistet werden, die Enkelkinder, sprich Tutoren sind nicht dabei. </p>
<p>
Wer der Oberboss ist könnten wir mit der <em>isRoot()</em> Methode herausfinden:</p>
<pre style="margin-left: 40px;">
println("Big boss is president: " + president.isRoot());</pre>
<p>
Wenn wir noch alle Angestellten nach Hierarchieebenen sortiert ausgeben wollen, dann verwenden wir den Level-Order Traversal:</p>
<pre style="margin-left: 40px;">
university.levelOrder(new VisitorInterface<String>() {
public void visit(AbstractNode<?> node) {
print(node.getElement() + ", ");
}
});</pre>
<p>
.</p>
<h2>
<img alt="" src="images/PilotChecklist.png" style="width: 200px; height: 130px; float: right;" />PilotCheckList</h2>
<p>
Bei Entscheidungsbäumen (decision trees) handelt es sich immer um Binärbäume. Als einfaches Beispiel beginnen wir mit einer Pilotencheckliste, die jeder Pilot durchgehen sollte bevor er abhebt. Zunächst legen wir wieder den Baum an, dieses mal mit Hilfe der <em>BinaryTree</em> und <em>BinaryNode</em> Klassen:</p>
<pre style="margin-left: 40px;">
BinaryNode<String> root = new BinaryNode<String>("Wings attached?");
BinaryNode<String> wheels = new BinaryNode<String>("Wheels attached?");
root.setLeft(wheels);
...
BinaryTree<String> decisions = new BinaryTree<String>(root);</pre>
<p>
Dann folgt der sogenannt "Pilot Walk Through": beginnend von der Wurzel des Baums, gehen wir eine Frage nach der anderen durch, und je nachdem ob der Nutzer mit Ja oder Nein antwortet, navigieren wir durch den Baum nach links oder rechts:</p>
<p>
<img alt="" src="images/PilotCheckList.png" style="width: 200px; height: 100px; float: right;" />.</p>
<pre style="margin-left: 40px;">
private void pilotWalkThrough() {
println("Welcome to the pilot check list.");
println("Answer the following questions with yes or no.");
// start with the root:
BinaryNode<String> currentNode = (BinaryNode<String>) decisions.root();
while (currentNode.isInternal()) {
String answer = readLine(currentNode.getElement() + "(yes/no)");
if (answer.equals("yes")) {
currentNode = currentNode.getLeft();
} else {
currentNode = currentNode.getRight();
}
}
println(currentNode.getElement());
}
</pre>
<p>
Am Ende geben wir dann die Empfehlung zu fliegen oder nicht zu fliegen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/SortAlgorithm.png" style="width: 200px; height: 150px; float: right;" />SortAlgorithm</h2>
<p>
Machen wir noch ein weiteres Beispiel für einen Entscheidungsbaum: Eine Empfehlung für die richtige Wahl eines Sortieralgorithmuses. Vor ein oder zwei Kapiteln haben wir folgendes gelernt:</p>
<ul>
<li>
BubbleSort dauert sehr lange, also nehmen wir es nur, wenn wir viel Zeit haben.</li>
<li>
Wenn wir die Anzahl der Swaps minimieren müssen, dann verwenden wir SelectionSort.</li>
<li>
Wenn unsere Eingabedaten fast sortiert sind, dann ist InsertionSort die beste Wahl.</li>
<li>
Für alles andere verwenden wir QuickSort.</li>
</ul>
<p>
Daraus machen wir jetzt einen Entscheidungsbaum. Allerdings wollen wir dieses Mal einen Parser verwenden, genauer gesagt den <em>BinaryTreeParser</em>:</p>
<pre style="margin-left: 40px;">
decisions = new BinaryTreeParser().parseTree(new File("sort_algorithm.txt"));</pre>
<p>
Der macht aus einer Textdatei einen Baum. Dabei muss die Textdatei aber gewissen Regeln folgen. Hier ist die Datei für unsere Sortieralgorithmen:</p>
<pre style="margin-left: 40px;">
You have time? {
BubbleSort,
Do you need to minimize the number of swaps? {
SelectionSort,
Data is almost sorted? {
InsertionSort,
QuickSort
}
}
}</pre>
<p>
Das Wurzel-Element ist die erste Frage, also "You have time?". Kinder beginnen mit einer geschweiften Klammer '{' und werden danach aufgelistet, mehrere Kinder werden durch Komma ',' getrennt. Bei Binärbäumen kann es höchstens zwei Kinder geben, dabei ist das erste Kind für den Ja-Fall und das zweite Kind für den Nein Fall. Natürlich muss jede geöffnete Klammer wieder geschlossen werden. Der Walk-Through selbst ist komplett identische wie im vorherigen Beispiel.</p>
<p>
.</p>
<h2>
Noch mehr Decision Trees</h2>
<p>
Man kann aus fast allem Entscheidungsbäume machen. Hier sind ein paar Vorschläge:</p>
<ul>
<li>
"So You Need A Typeface" von Julian Hansen ist ein Entscheidungsbaum mit dessen Hilfe man die richtige Schriftart für seine Anwendung findet. [1]</li>
<li>
Sollte eine Person einen Kredit bekommen? [2]</li>
<li>
Welche Programmiersprache soll ich für mein Projekt verwenden? [3]</li>
<li>
Für die Datenvisualisierung können wir zwischen Balkendiagramm, Kreisdiagramm, Baumdiagramm, Linienplot, Streudiagramm, etc. wählen. In dem Buch <em>Data Points</em> von Nathan Yau [4] kann man ab Seite 137 Kriterien nachlesen, wie man die passende Visualisierung auswählt. Daraus kann man einen Entscheidungsbaum machen.</li>
<li>
Welche Game-Engine soll ich verwenden? Man könnte Kosten, Lizenz, Support, Anzahl der Projekte, etc. als Kriterien verwenden.</li>
<li>
Was soll ich studieren? Überlegen Sie sich Fragen, die es einem Benutzer helfen zu entscheiden, was er oder sie studieren sollte.</li>
<li>
Sogar Schach kann man als Entscheidungsbaum darstellen. [5]</li>
</ul>
<p>
<br />
Man könnte sich auch Fragen überlegen mit denen man z.B. Vögel, Bäume, Tiere, Pflanzen, Krankheiten, usw. klassifizieren könnte. Weiter unten werden wir uns damit beschäftigen wie man Wildbienen identifiziert.</p>
<p>
.</p>
<h2>
<img alt="" src="images/FileSizes.png" style="width: 200px; float: right; height: 100px;" />FileSizes</h2>
<p>
Im Kapitel über Rekursion haben wir schon einmal die Summe der Größe aller Dateien in einem Verzeichnis ermittelt. Wir wollen das jetzt noch einmal machen aber dieses mal mit Hilfe eines Baumes. Wir beginnen damit, dass wir die Verzeichnisse rekursiv durchlaufen:</p>
<pre style="margin-left: 40px;">
private void buildFileTreeRecursive(OrderedNode<File> node) {
File file = node.getElement();
if (file.listFiles() != null) {
for (File child : file.listFiles()) {
// we are only interested in directories
if (child.isDirectory()) {
OrderedNode<File> newDir = new OrderedNode<File>(child);
node.addChild(newDir);
<span style="color:#0000ff;">buildFileTreeRecursive</span>(newDir);
}
}
}
}</pre>
<p>
Unser <em>OrderedNode<File></em> enthält dieses Mal <em>Files</em> anstelle von Strings. Das ist ganz praktisch wie wir gleich sehen werden. Diese Methode rufen wir von der <em>createFileTree()</em> Methode auf:</p>
<pre style="margin-left: 40px;">
private OrderedTree<File> createFileTree(File startFile) {
OrderedNode<File> directories = new OrderedNode<File>(startFile);
buildFileTreeRecursive(directories);
return new OrderedTree<File>(directories);
}</pre>
<p>
<img alt="" src="images/PostOrderTraversal.png" style="width: 200px; height: 141px; float: right;" />So jetzt haben wir den Baum, was machen wir damit? Oben beim Post-Order Traversal haben wir gehört, dass man damit die Gesamtgröße aller Dateien in einem Verzeichnis, aber auch jeweils aller seiner Unterverzeichnisse ermitteln kann. Das machen wir jetzt:</p>
<pre style="margin-left: 40px;">
OrderedTree<File> fileTree = createFileTree(new File("/home/ralph/"));
fileTree.<span style="color:#0000ff;">postOrder</span>(new VisitorInterface<File>() {
@Override
public void visit(AbstractNode<?> node) {
long sizeOfFilesInDir = 0;
File f = (File) node.getElement();
if (f.isDirectory()) {
for (File ff : f.listFiles()) {
if (ff.isFile()) {
sizeOfFilesInDir += ff.length();
}
}
} else {
println("we should never get here!");
}
totalSize += sizeOfFilesInDir;
//println(node +": "+sizeOfFilesInDir);
}
});</pre>
<p>
Mit der postOrder() Methode gehen wir also den ganzen Baum rekursiv durch. Wir ermitteln also zunächst die Größe von Knoten '1', dann die von '2', danach können wir die von '3' ausrechnen. Das machen wir solange bis wir bei der Wurzel angekommen sind.</p>
<p>
.</p>
<h2>
<img alt="" src="images/FileSizesGraphical.png" style="width: 200px; float: right; height: 200px;" />FileSizesGraphical</h2>
<p>
Dass sich die ganze Arbeit lohnen kann, sehen wir jetzt: wir wollen alle Verzeichnisse und ihre Größen in einer Art Kuchendiagramm graphisch darstellen. Im Prinzip haben wir im Projekt <em>FileSizes</em> schon fast alles was wir brauchen. Was fehlt ist, dass wir uns irgendwie merken können was denn die Größe aller Dateien in einem gewissen Unterverzeichnis war. Im Projekt <em>FileSizes</em> haben wir die einfach weggeschmissen. Der Trick ist anstelle der Klasse File eine eigene Klasse zu definieren:</p>
<pre style="margin-left: 40px;">
class FileAndSize {
public File file;
public long size;
public FileAndSize(File file, long size) {
this.file = file;
this.size = size;
}
}</pre>
<p>
Das ist jetzt nicht ganz koscher, weil die Instanzvariablen public sind, da das aber eine lokale Klasse ist, geht das schon in Ordnung. Damit sind die beiden Methoden <em>buildFileTreeRecursive()</em> und <em>createFileTree()</em> vom obigen Beispiel fast identisch, wir müssen lediglich <em>File</em> durch <em>FileAndSize</em> ersetzen und den Konstruktoraufruf durch</p>
<pre style="margin-left: 40px;">
OrderedNode<FileAndSize> directories =
new OrderedNode<FileAndSize>(<span style="color:#0000ff;">new FileAndSize(startFile, -1)</span>);</pre>
<p>
Wir erhalten dann also einen Tree der aus Verzeichnissen mit ihren jeweiligen Größen besteht:</p>
<pre style="margin-left: 40px;">
OrderedTree<FileAndSize> fileTree = createFileTree(new File("/home/ralph/"));
traverseAndDrawArcs(fileTree.root(), 0, 360, 0);</pre>
<p>
<img alt="" src="images/FileSizesGraphical2.png" style="width: 200px; height: 200px; float: right;" />Diesen Baum durchlaufen wir jetzt rekursiv und zeichnen GArcs mit einer Breite die jeweils proportional zur Verzeichnisgröße ist. Das geht automatisch von außen nach innen, da es ja ein rekusiver Algorithmus ist.</p>
<pre style="margin-left: 40px;">
private void <span style="color:#0000ff;">traverseAndDrawArcs</span>(AbstractNode<FileAndSize> tree,
double alpha, double sweep, int depth) {
// base case
if (depth > 8)
return;
// recursive case
depth++;
long parentSize = tree.getElement().size;
for (AbstractNode<FileAndSize> child : tree.getChildren()) {
long childSize = child.getElement().size;
double deltaAlpha = sweep * childSize / parentSize;
if (deltaAlpha > 1) {
<span style="color:#0000ff;">traverseAndDrawArcs</span>(child, alpha, deltaAlpha, depth);
int radius = depth * DISK_THICKNESS;
GArc arc = new GArc(centerX - radius / 2, centerY - radius / 2,
radius, radius, alpha, deltaAlpha);
arc.setFilled(true);
arc.setColor(rgen.nextColor());
add(arc);
}
alpha += deltaAlpha;
}
}</pre>
<p>
Schaut ganz hübsch aus. Man kann das auch mit GRects machen, ist aber nicht ganz so hübsch.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Fibonacci.png" style="width: 200px; float: right; height: 100px;" />Fibonacci</h2>
<p>
Wir haben ja vor ein paar Kapiteln die Bekanntschaft des Herren Fibonacci gemacht. Das man seine Zahlen auch als Baum darstellen kann wollen wir jetzt zeigen. Wobei das mit dem Baum sehr wörtlich gemeint ist. Der Fibonacci Baum ist ein binärer Baum, und er besteht aus Zahlen, deswegen verwenden wir <em>BinaryNode<Integer></em> für unsere Knoten als Datentyp. Wir verwenden wieder unsere rekursive Methode <em>fibu()</em> übergeben aber anstelle von Zahlen einen BinaryNode:</p>
<pre style="margin-left: 40px;">
private int fibo(BinaryNode<Integer> node) {
int n = node.getElement();
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
BinaryNode<Integer> left = new BinaryNode<Integer>(n - 2);
node.setLeft(left);
BinaryNode<Integer> right = new BinaryNode<Integer>(n - 1);
node.setRight(right);
return fibo(right) + fibo(left);
}
}</pre>
<p>
Daraus machen wir dann einen BinaryTree:</p>
<pre style="margin-left: 40px;">
BinaryNode<Integer> root = new BinaryNode<Integer>(n);
fibo(root);
BinaryTree tree = new BinaryTree<Integer>(root);</pre>
<p>
Wie stellen wir nun den Baum dar? Dafür verwenden wir die Hilfsklasse <em>TreePrinter</em>, die uns ein String Array zurückgibt,</p>
<pre style="margin-left: 40px;">
String tmp[][] = new tree.TreePrinter().prettyPrintSimple(tree);
printTreeVertical(tmp);</pre>
<p>
welches wir dann einfach nur noch in unserem ConsoleProgram ausgeben müssen:</p>
<pre style="margin-left: 40px;">
private void printTreeVertical(String[][] tmp) {
for (int i = 0; i < tmp.length; i++) { // 4
for (int j = 0; j < tmp[0].length; j++) { // 7
System.out.println();
if (tmp[i][j] != null) {
print(tmp[i][j] + " ");
} else {
print(" ");
}
}
println();
}
}</pre>
<p>
.</p>
<h2>
<img alt="" src="images/FibonacciGraphical.png" style="width: 200px; float: right; height: 125px;" />FibonacciGraphical</h2>
<p>
Die Textausgabe von Bäumen, so wie wir es oben gemacht haben ist nicht sehr befriedigend. Viel schöner wäre es wenn man Bäume graphisch ausgeben könnte. Mit dem <em>BinaryTreeDrawerCanvas</em> geht das sogar relativ einfach. Der Code ist fast identisch mit dem obigen. Natürlich muss unser Programm jetzt ein <em>Program</em> sein, also</p>
<pre style="margin-left: 40px;">
public class FibonacciGraphical extends <span style="color:#0000ff;">Program</span> { ... }</pre>
<p>
und wir müssen den Baum der <em>BinaryTreeDrawerCanvas</em> Klasse übergeben, die wir dann wie aus dem ersten Semester gewohnt zu unserer UI hinzufügen:</p>
<pre style="margin-left: 40px;">
BinaryTree<Integer> tree = new BinaryTree<Integer>(root);
canvas = new <span style="color:#0000ff;">BinaryTreeDrawerCanvas</span>(tree);
canvas.setShapeNode(BinaryTreeDrawerCanvas.SHAPE_ROUNDRECT);
canvas.setOrientation(BinaryTreeDrawerCanvas.VERTICAL);
canvas.setEdgeStyle(BinaryTreeDrawerCanvas.EDGE_STYLE_DIRECT);
canvas.setFont("Courier new-bold-18");
add(canvas, CENTER);</pre>
<p>
Auch wieder viel hübscher.</p>
<p>
.</p>
<h2>
<img alt="" src="images/FibonacciTree_Simple.png" style="width: 200px; float: right; height: 200px;" />FibonacciTree</h2>
<p>
Dass man mit den Fibonacci Zahlen und dem Pre-Order Traversal wirklich Bäume zeichnen kann, wollen wir jetzt zeigen. Wir verwenden wieder unsere <em>fibu()</em> Methode von oben, um unseren Binärbaum zu erzeugen.</p>
<pre style="margin-left: 40px;">
private double len = 80;
private double leftAngle = -40;
private double rightAngle = 20;
public void run() {
int n = 5;
BinaryNode<Integer> root = new BinaryNode<Integer>(n);
fibo(root);
preOrderSimple(root, SIZE/2-40, SIZE-44, -Math.toRadians(90));
}</pre>
<p>
.</p>
<p>
<img alt="" src="images/FibonacciTree_Pretty.png" style="width: 200px; float: right; height: 200px;" />Wir haben auch noch drei Instanzvariablen eingeführt, eine für die Länge der "Zweige", eine für den Winkel um den sich die Äste nach links lehnen sollen, und einen Winkel für die rechten Äste. Der Pre-Order Traversal sieht dann wie folgt aus:</p>
<pre style="margin-left: 40px;">
private void preOrderSimple(BinaryNode<Integer> node, int x0, int y0, double alpha) {
//visit
GLine line = new GLine(x1, y1, x1 + len * Math.cos(alpha), y1 + len * Math.sin(alpha));
add(line);
x0 += len * Math.cos(alpha);
y0 += len * Math.sin(alpha);
// recurse
if (node.hasLeft()) {
preOrderSimple(node.getLeft(), x0, y0, alpha+Math.toRadians(leftAngle));
}
if (node.hasRight()) {
preOrderSimple(node.getRight(), x0, y0,alpha+Math.toRadians(rightAngle));
}
}
</pre>
<p>
Mit ein paar kleinen Modifikationen wird das dann ganz ansehnlich und man kann sogar eine gewisse Ähnlichkeit mit Bäumen nicht verleugnen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/DrawBinaryTree.png" style="width: 200px; float: right; height: 100px;" />DrawBinaryTree</h2>
<p>
Um Bäume einigermaßen ansprechend darzustellen gibt es die TreeDrawerCanvas und zwar in zwei Versionen, einmal für binären Bäume, <em>BinaryTreeDrawerCanvas</em>, und dann auch für beliebige Bäume, <em>OrderedTreeDrawerCanvas</em>. Verwendet werden beide fast identisch,</p>
<pre style="margin-left: 40px;">
public class DrawBinaryTree extends Program {
public void init() {
BinaryTree<String> tree =
new BinaryTreeParser().parseTree(new File("eat.txt"));
BinaryTreeDrawerCanvas canvas = new BinaryTreeDrawerCanvas(tree);
canvas.setNodeSeparationX(98);
add(new JScrollPane(canvas), CENTER);
}
}</pre>
<p>
<img alt="" src="images/DrawBinaryTree2.png" style="width: 200px; height: 100px; float: right;" />Das Beispiel zeigt einen binären Bäum an, der aus der Datei "eat.txt" erzeugt wurde. Wir können verschiedene Parameter variieren, z.B., können wir bei den Shapes wählen zwischen</p>
<ul>
<li>
SHAPE_OVAL</li>
<li>
SHAPE_RECT</li>
<li>
SHAPE_ROUNDRECT</li>
</ul>
<p>
Ausserdem können wir die Farben der internen und externen Knoten setzen, auch deren Hintergrundfarbe:</p>
<pre style="margin-left: 40px;">
canvas.setShapeNode(BinaryTreeDrawerCanvas.SHAPE_OVAL);
canvas.setColorExternalNodes(Color.BLUE);
canvas.setColorExternalNodesFill(Color.LIGHT_GRAY);
canvas.setColorInternalNodes(Color.RED);
canvas.setGridOn(true);</pre>
<p>
Wir können auch ein Hintergrundgitter anzeigen lassen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/DrawOrderedTree_University.png" style="width: 200px; float: right; height: 300px;" />DrawOrderedTree</h2>
<p>
Geordnete Bäume können im Unterschied zu binären Bäume auch mehr als zwei Kinder haben. Ein Beispiel ist unser Hochschulbeispiel vom Anfang des Kapitels. Es macht Sinn diesen Baum von links nach rechts, also horizontal darzustellen. Und für die Verbindungslinien, Edges, haben wir einen anderen Stil gewählt:</p>
<pre style="margin-left: 40px;">
canvas.setOrientation(OrderedTreeDrawerCanvas.HORIZONTAL);
canvas.setEdgeStyle(OrderedTreeDrawerCanvas.EDGE_STYLE_SQUARE);</pre>
<p>
.</p>
<p>
Wenn wir die Verbindungen zwischen den Knoten lieber mit sogenannten "Quad-Line" Segmenten verbinden möchten,</p>
<pre style="margin-left: 40px;">
canvas.setEdgeStyle(OrderedTreeDrawerCanvas.EDGE_STYLE_QUAD);</pre>
<p>
dann eignet sich das recht gut für die Darstellung von Büchern:</p>
<h2 style="margin-left: 40px;">
<img alt="" src="images/DrawOrderedTree_Book.png" style="width: 500px; height: 100px;" /></h2>
<p>
.</p>
<p>
<img alt="" src="images/DrawOrderedTree_Abraham.png" style="width: 200px; float: right; height: 400px;" />Für Genealogien, eignet sich vielleicht wieder die horizontale Auflistung, allerdings machte es hier Sinn, das Alignment anzupassen:</p>
<pre style="margin-left: 40px;">
canvas.setOrientation(OrderedTreeDrawerCanvas.HORIZONTAL);
canvas.setAlignment(OrderedTreeDrawerCanvas.ALIGN_LEFT);
canvas.setEdgeStyle(OrderedTreeDrawerCanvas.EDGE_STYLE_QUAD);</pre>
<p>
.</p>
<p>
Möchte man aber z.B. phylogenetische Beziehungen zwischen Säugetieren darstellen, dann will man nur die externen Knoten darstellen, interne Knoten sollen unsichtbar bleiben. Die Verbindungslinien sollen wieder rechtwinklig sein, und man möchte keine Umrandung sehen. </p>
<pre style="margin-left: 40px;">
canvas.setEdgeStyle(OrderedTreeDrawerCanvas.EDGE_STYLE_SQUARE);
canvas.setShowInternalNodes(false);
canvas.setColorExternalNodes(Color.WHITE);</pre>
<p>
Das sieht dann so aus:</p>
<h2 style="margin-left: 40px;">
<img alt="" src="images/DrawOrderedTree_CamelsAndWhales.png" style="width: 200px; height: 200px;" /></h2>
<p>
Ich denke das dürfte genügen, um zu sehen, dass wir wahrscheinlich 80% aller Bäume halbwegs o.k. aussehend darstellen können.</p>
<p>
.</p>
<h2>
Traversals</h2>
<p>
Ein anderes hübsches Beispiel ist es einmal alle different Traversals auszuprobieren. Der folgende Code erlaubt das an einem einfachen Beispiel:</p>
<pre style="margin-left: 40px;">
String str = "A{B{C,D},E{F,G,H},I}";
OrderedTree<String> tree = new OrderedTreeParser().parseTree(str);
//tree.levelOrder(new VisitorInterface<String>() {
//tree.postOrder(new VisitorInterface<String>() {
tree.preOrder(new VisitorInterface<String>() {
int counter = 1;
public void visit(AbstractNode<?> node) {
((OrderedNode<String>)node).setElement(""+counter++);
}
});</pre>
<p>
Die Zahl gibt die Reihenfolge an in der die jeweiligen Knoten besucht wurden, als erstes für Pre-Order, gefolgt von Post-Order und schließlich Level-Order Traversal:</p>
<table align="center" border="0" cellpadding="10" cellspacing="10" style="width: 100%;">
<tbody>
<tr>
<td style="text-align: center; vertical-align: middle;">
<p>
<img alt="" src="images/Traversal_PreOrder.png" style="width: 200px; height: 100px;" /></p>
<p>
Pre-Order</p>
</td>
<td style="text-align: center; vertical-align: middle;">
<p>
<img alt="" src="images/Traversal_PostOrder.png" style="width: 200px; height: 100px;" /></p>
<p>
Post-Order</p>
</td>
<td style="text-align: center; vertical-align: middle;">
<p>
<img alt="" src="images/Traversal_LevelOrder.png" style="width: 200px; height: 100px;" /></p>
<p>
Level-Order</p>
</td>
</tr>
</tbody>
</table>
<p>
.</p>
<h2>
Parsing</h2>
<p>
In dem <em>SortAlgorithm</em> Projekt haben wir einen Parser verwendet, genauer gesagt den <em>BinaryTreeParser</em>:</p>
<pre style="margin-left: 40px;">
decisions = new BinaryTreeParser().parseTree(new File("sort_algorithm.txt"));</pre>
<p>
Wie funktioniert der? Eigentlich haben wir schon einige Parser selbst geschrieben, denn jedesmal wenn wir den <em>StringTokenizer</em> verwendet haben, haben wir irgendetwas geparst. Schauen wir uns erst einmal an was wir parsen wollen:</p>
<pre style="margin-left: 40px;">
Are_you_vegetarian? {
Eat_vegetables!,
Eat_meat!
}</pre>
<p>
Daraus wollen wir einen Binärbaum parsen. Die Trennzeichen sind die geschweiften Klammer '{' und '}' und das Komma ','. Also verwenden wir</p>
<pre style="margin-left: 40px;">
StringTokenizer st = new StringTokenizer(line, "{},", true);</pre>
<p>
dabei ist das letzte <em>true</em> ganz wichtig, denn es besagt, dass auch die Trennzeichen in Tokens verwandelt werden. Wir schleifen dann einfach durch</p>
<pre style="margin-left: 40px;">
while (st.hasMoreTokens()) {
String token = st.nextToken().trim();
if (token.length() > 0) {
...
}
}
</pre>
<p>
und den Rest der Arbeit erledigen wir mit einem <em>switch</em>:</p>
<pre style="margin-left: 40px;">
switch (token) {
case "{":
...
break;