Ada95 - Breite eines Baumes bestimmen

[Moch]

Hallo,
Ich stehe vor einem Problem.
Derzeit arbeiten wir wieder mit Ada95 (Delphi sehr ähnlich) und sollen in einer größeren Aufgabe einen String in einen Huffman-Baum verwandeln. Die "Blätter" jenes Baumes beinhalten jeweils einen Character und die zugehörige Häufigkeit (wie oft das Ding im String vorkommt). Der Baum selbst ist nicht gleichmäßig aufgebaut.

Im AdaCode sieht der Baum wie folgt aus:

type HuffmanTreeNode;
type HuffmanTree is access HuffmanTreeNode; -- erzeugt einen Pointer

type HuffmanTreeNode is record
Char: Character;
Count: Natural;
Left: HuffmanTree;
Right: HuffmanTree;
end record;

Zur Erklärung, was hier passiert. Es wird zunächst ein nutzbarer Pointer erzeugt (siehe Kommentar), um damit den Baum rekursiv aufzubauen (left und right verweisen wieder auf einen solchen baum).
Man könnte es mit einem Objekt in Java vergleichen(!), wobei unser Ansatz hier nicht objektorientiert, sondern imperativ sein soll.

Im Laufe meines Programms werden mehrere HuffmanTrees erzeugt und später zu einem großen HuffmanTree zusammengefügt. Wie das ganze aussieht, ist jetzt hinfällig, da es gut 100 Zeilen Code beansprucht.

Mein Problem ist jetzt, dass ich eine Function schreiben soll, die die Breite eines solches Baumes berechnet... leider habe ich absolut keinen Ansatz

bisher implementierte Funktionen (Ada unterscheidet im gegensatz zu Java noch in Functions und Procedures). Alle hier wurden von mir gestest und funktionieren... wer sie sich sparen will, kann den teil auch überspringen - ist nur für denn fall, dass man eine der funktionen dafür nutzen könnte.

--Erzeugt ein Array, das jedem Character eine Häufigkeit zuweist
function countCharFrequency(stringToCount String : String) return Frequency_Array;

--Erzeugt ein Array aus oben beschrieben Blättern
function createLeafArray(freqArray : Frequency_Array) Return Leaf_Array;

--Fügt einen HuffmanTree in eine verkettete Liste ein (arbeitet mit Pointern)
function insert(treeList : HuffmanTreeList; insertTree : HuffmanTree) return HuffmanTreeList;

--Gibt das erste Element einer HuffmanTreeList zurück
function getFirst(treeList : HuffmanTreeList) return HuffmanTree;

--Löscht das erste Element einer solchen Liste (Pointer wird zu null)
function withoutFirst(treeList : HuffmanTreeList) return HuffmanTreeList;

--Vereinigt zwei HuffmanTrees zu einem
function buildTreeOfSubTrees(left: HufmanTree; right: HuffmanTree) return HuffmanTree;

--macht aus einer leaf_array eine Huffmantreelist und daraus einen großen Huffmantree
function createHuffmanTree(leafArray : Leaf_array) return huffmanTree;

--bestimmt die Tiefe eines HuffmanTrees:
function getDepth(huff : huffmantree; counter : integer) return integer;

nun stehe ich hier und weiß nicht, wie ich es schaffen sollen, die breite des baumes rekursiv zu bestimmen -.- - kann mir da einer einen Ansatz nenne, wie ich die Breite eines ungleichmäßigen Baumes rausbekomme?

liebe Grüße
Moch

 

[Moch]

Okay, ich brauchte nur ne weitere Kanne Kaffee, bis ich des Problems Lösung fand... nur der Formhalber möchte ich es hier noch posten, falls noch wer zufällig mal dieses Problem haben sollte:

function getWidth (huff: HuffmanTree) return integer is
Counter : Integer := 0;
runTree := HuffmanTree := huff;
bacTree := HuffmanTree := huff;     -- hier zum Speichern des Pointers auf dem obersten Element

begin
while(runTree =/ null) loop
Counter := counter+1;
runTree := runTree.left;
end loop;

runTree := bacTree -- hier zurücksetzen des Pointers auf ersten Knoten

while(runTree =/ null) loop
counter := counter+1;
runTree := runTree.right;
end loop;

Counter := Counter -1;   -- notwendig, da der erste Knoten (die Wurzel) doppelt gezählt wurde
return counter;
end getWidth;

Der Hinweis, man solle die Breite rekursiv bestimmt, wurde hier von mir ignoriert, da ich von rekursion nicht viel halte... immerhin ist der Baum selbst schon rekursiv aufgebaut und ich sehe keinen Grund unnötigerweise hier auch noch rekursiv durchzugehen, wenn es hier ganz offensichtlich auch iterativ geht.

lieben Gruß
Moch

 

[Landei]

Rekursion ist konzeptionell einfacher und vielseitiger, und es gibt Sprachen ganz ohne Schleifen (wie z.B. Haskell). Es wird beispielsweise schon schwierig, folgende Rekursion in eine Iteration zu übersetzen, ohne die Struktur der Definition stark zu verändern:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

 

[Moch]

Nun, das war mir schon bewusst. Ada95 allerdings hat eben die Möglichkeit einer For-Schleife und einer While-Schleife. Ohne Not nutze ich normalerweise keine Rekursion, wenn mir die Sprache andere Wege anbietet.
Natürlich gibt es auch hier Dinge wie Backtracking, die einer Rekursion bedürfen.
Eine Schleife bietet aber, wenn auch manchmal komplexer zu schreiben, eine gewisse Sicherheit, dass mir der Stack nicht direkt überlaufen kann, was bei einer Rekursion recht schnell auftreten kann, wenn man nicht aufpasst.

Mit Haskell habe ich hier im Studium selbst schon gearbeitet (das war unsere funktionale Sprache, bevor wir mit imperativen Sprachen wie Ada95 und später mit Java als objektorientierte Sprache angefangen haben).

Im Falle dieses Problems unter Verwendung der angegeben Sprache jedoch sehe ich keine notwendigkeit eines rekursiven Ansatzes, da es hier zwei simple Schleifen auch tun und hier sogar meiner Meinung nach, einen einfacherer Weg anbieten.

lg
Moch