Binären Baum

[Stillmatic]

Kann mir einer von euch einen tip geben wie ich einen Binären Baum mit Buchstaben füllen könnte!!

Aber nicht einfach füllen sondern nach einem bestimmten Kriterium!
Ich habe einen Array in dem ein Buchstabe(A-Z) einem Zeichen zugewiesen wird z.B (.) (-)!

Also soll zum Beispiel der Buchstabe mit einem (.) rechts und der Buchstabe mit einem (-) links dargestellt werden!!

Das ist bissher auch kein Problem, das Problem ist das manchen Buchstaben dann diese Zeichenfolge zugewiesen ist ...-!!

Könnte mir da einer nen Tip geben????

[marabu]

Hallo,

wenn ich deine Frage richtig verstehe, dann bedeutet die Wegbeschreibung ...- dass du im Binärbaum dreimal rechts und einmal links abzweigen sollst um an den fraglichen Buchstaben zu gelangen. Du musst also alle gegebenen Wegbeschreibungen nach ihrer Länge sortieren und kannst dann deinen Baum aufbauen.

Grüße vom marabu

[Stillmatic]

Ne ich muss das irgendwie anders lösen!

Das sortieren kann ich nicht machen da ich dann die Liste veränder und das darf nicht sein!

Es muss noch eine andere Möglichkeit geben!

Meine Idee ist das ich irgendwie abfrage ob das Zeichen . oder - ist um dann den Buchstaben an die Stelle zu schreiben!
Aber das bekomme ich noch nicht so ganz hin??

[edosoft]

also ich versteh nicht was du willst

[Stillmatic]

Ich muss einen Binären Baum mit Buchstaben füllen!
Ich habe einen Array von A-Z mit (.) (-) kombinationen!
Also trägt Array[D] Z.B -...!!
Jetzt muss der Binäre Baum aber aufgrund von den (.) (-) Kombinationen gefüllt werden wobei ein Punkt in die linke und ein - in die rechte Verzweigung geht!!

Nur komme ich da nicht recht hinter wie ich dann Festelle wie weit ich in den Baum gehen muss!
Wenn ich nur ein Zeichen habe ist es ja einfach nur was macht man bei 2 oder merh Zeichen???

[Relicted]

hört sich nach huffman komprimierung an oder?

gruß
reli

[alzaimar]

marabu hat schon Recht: Natürlich kann man das Array nicht einfach so sortieren, denn der Index enthält ja die Information des Pfades für den Buchstaben. Sein Vorschlag ist hinsichtlich der Laufzeit optimal, aber es geht auch so (die Funktion fügt ein Zeichen anhand des Pfades in einen Baum ein):

Delphi-Quellcode:

Procedure BildeBaum (aChar : Char; aPfad : String; aBaum : TBinaerBaum);
Begin
  If aPfad='' Then
     aBaum.Zeichen := aChar
  Else If aPfad[1]='.' Then Begin
    If not Assigned (aBaum.Links) Then aBaum.Links := TBinaerbaum.Create;
    BildeBaum (aChar, Copy (aPfad,2, maxint), aBaum.Links)
  End 
  Else If aPfad[1]='-' Then Begin
    If not Assigned (aBaum.Rechts) Then aBaum.Rechts := TBinaerbaum.Create;
    BildeBaum (aChar, Copy (aPfad,2, maxint), aBaum.Rechts)
  End 
  Else Raise Exception.Create('Ungültige Pfadangabe');
End;

Ist es eine Hausaufgabe? Dann musst Du das auch verstehen!

@Relicted: Nee, nur weil Buchstaben in einem binären Baum sind, muss das noch kein Huffman sein (kann aber).

[marabu]

Guten Morgen,

Zitat von Stillmatic:

... Das sortieren kann ich nicht machen da ich dann die Liste veränder und das darf nicht sein! ...

selbstverständlich darfst du die Liste sortieren - du musst es sogar. Wie willst du sonst deinen Morse-Code in einen Binärbaum verwandeln? Die Ordnung im Baum bleibt ja stets dieselbe und ist nur von der Interpretation der beiden Zeichen abhängig. alzaimar hat dich ja schon darauf gestoßen: Der Sort muss ja kein inplace sort sein:

Delphi-Quellcode:

procedure TDemoForm.Button2Click(Sender: TObject);
var
  i: Integer;
  c: Char;
  a: array['A'..'E'] of String;
  sl: TStringList;
begin
  sl := TStringList.Create;
  a['A'] := '.-';
  a['B'] := '-...';
  a['C'] := '-.-.';
  a['D'] := '-..';
  a['E'] := '.';
  for c := Low(a) to High(a) do
    sl.AddObject(a[c], Pointer(Ord(c)));
  sl.Sort;
  for i := 0 to Pred(sl.Count) do
  begin
    c := Chr(Integer(sl.Objects[i]));
    ListBox.Items.Add(c + '=' + sl[i]);
  end;
end;

Freundliche Grüße

[Stillmatic]

@
alzaimar

Was ist was??
aChar : Char ----> Der Buchstabe??
aPfad : String ----> Das Zeichen zum gehörigen Buchstaben??
aBaum : TBinaerBaum ----> Der Baum !