WS 2002/2003                   Übung 8                          H. Schweppe
                                        

        Ausgabe: 5.12.2002
        Abgabe: 17.12.2002  15.00

Aufgabe 8.1 (  8 P)  

Das folgende Alphabet und die entsprechenden Gewichte wurden zur effizienten Kodierung der Popmusik der sechziger Jahre entwickelt: 

A              2                                NA           16
YEAH      2                                OH             3
GET         2                                LA           10
JOB         1                                SHA         1

Konstruieren Sie den Huffman Kodebaum, und kodieren Sie die folgende Lyrik der sechziger:

Get a job
Sha na na na na na na na
Get a job
Oh na na na na na na na
Yeah la la la la la la
Oh yeah

In welchem Verhältnis steht die Anzahl benötigter Bits zu der Anzahl, die man im 8-Bit-ASCII Code braucht? 
Es bleibt Ihnen überlassen, ob Sie Programme zur Konstruktion des Huffman Baums (s. VL) und zur Kodierung schreiben oder nur auf Papier arbeiten. 

Aufgabe 8.2 ( 8  P)  

Gesucht ist ein Algorithmus, der den "kleinsten gemeinsamen Vorgänger" von zwei Knoten in einem Binärbaum bestimmt. Der kleinste gemeinsame Vorgänger von Knoten a und b ist  a , wenn b Nachfolger von a ist ,  b, wenn a Nachfolger von b sonst der Knoten x  maximaler Tiefe, der Vorgänger sowohl von a als auch von b ist. 
(Trockenübung).

Aufgabe 8.3 ( 8  P)  

Durch Traversierung eines binären Baum entstehen  eindeutige Linearisierungen der Knotenmenge  (Preorder, Inorder, Postorder). 
Umgekehrt gehört z.B. zu einer Preorder-Knotenliste nicht eindeutig ein binärer Baum. 
Dagegen lässt sich aus der Postorder und Inorder-Liste der Binärbaum eindeutig rekonstruieren. Entwickeln Sie einen entsprechenden Algorithmus und implementieren Sie ihn in Haskell. 
Zeigen Sie mit einem Gegenbeispiel. dass die Rekonstruktion nicht möglich ist, wenn man von Postorder- und Preorder-Listen ausgeht. 

Aufgabe 8.4 ( 8  P)  

Schreiben Sie ein Programm, das einen (nicht zu großen) Binärbaum mit der Wurzel oben ausgibt. Z.B. so: 

                                                                10

                                8                                                                    20

                7                            9                                     14                                22

Freiwillig: Ausgabe mit Wurzel unten (5 Bonuspunkte). 

32 Punkte