 Huffmanbaum Delphi |
uhr123
unregistriert
 |
|
Hallo,
ich habe eine Frage: Wie kann ich, wenn ich Buchstaben sortiert in einem BinarySearchTree habe, als einelementige Bäume in eine Liste schreiben und dann jeweils aus der Liste die beiden kleinsten Objekte (also in der Liste sollen die dann aber schon nach Häufigkeit eines Buchstabens einsortiert sein) zusammenfügen und wieder in die Liste tun?
Kommentare in Delphi sind folgende:
// ermittelt die vorkommenden Zeichen und deren Häufigkeiten und erstellt
// als Funktionsergebnis einen alphabetisch geordneten Baum aller im Klartext
// auftretenden Zeichen und deren Häufigkeit. Die Inhaltsobjekte des Baums
// sind vom Typ TZeichenObjekt
//erzeugt aus dem alphabetisch geordneten Zeichenbaum pZeichenBaum durch einen
//inorder-Durchlauf die nach Häufigkeiten geordnete Liste der einelementigen Huffman-Bäume
//und liefert diese als Funktionsergebnis zurück.
//erzeugt aus der nach Häufigkeiten geordneten Lise der einelementigen
//Huffmanbäume pHuffmanBaumListe den endgültigen HuffmanBaum als Funktionsergebnis
Aber irgendwie bekomme ich in die Liste nur TZeichenobjekte rein, keine elementigen Bäume... und das Zusammenfassen der Kleinsten klappt auch nicht.
Kann mir jemand helfen, wie ich das in Delphi schreiben muss?
|
|
03.03.2013 18:56 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
mit Delphi kenne ich mich leider nicht aus. Aber vlt reicht eine methodische Beschreibung um deinem Problem auf die Spur zu kommen.
| Zitat: |
Original von uhr123
Wie kann ich, wenn ich Buchstaben sortiert in einem BinarySearchTree habe, als einelementige Bäume in eine Liste schreiben
|
Ich würde eine Funktion schreiben, welche Huffman-Bäume und eine Liste von Huffman-Bäumen entgegen nimmt schreiben. Dann eine leere Liste anlegen und danach beim in-order-traversieren immer einen neuen Huffman-Baum erstellen, welcher nur den betroffenen Buchstaben enthält.
Ich nehme an, dazu sollte es Baum- und Blattknoten geben. Der Baumknoten hält die Häufigkeit und die Kinder, wobei Kinder entweder 2 Baumknoten sind oder ein Blattknoten. Die Blattknoten beinhalten dann das Zeichen.... Dann jeden Baum und die Liste an die geschriebene Funktion übergeben, welche das geordnete einfügen in die Liste übernimmt.
| Zitat: |
Original von uhr123
und dann jeweils aus der Liste die beiden kleinsten Objekte (also in der Liste sollen die dann aber schon nach Häufigkeit eines Buchstabens einsortiert sein) zusammenfügen und wieder in die Liste tun?
|
Hier müssen einfach die zwei Bäume mit der kleinsten häufigkeit aus der Liste entnommen werden (also nicht nur abrufen, sondern auch wirklich entnehmen) und anschließend wird ein neuen Huffman-Baum erstelllt, welcher als Kinder die beiden kleineren Bäume hat. Diesen dann wieder mit der oben genannten funktion sortiert in die Liste einfügen. Und das so lange, Bis die Liste nur noch ein Element hat.
Wo ist genau das Problem?
VG,
Karlito
|
|
|
04.03.2013 11:55 |
|
|
|
