4. Binärer Baum verkehrt beginnen?

Binärer Baum verkehrt beginnen?

  • ?

    Moin zusammen,

    Ich will mir einen binären Baum basteln(keine hausaufgaben, eigenständiges Interesse 🙂 )
    Darauf bin ich gekommen weil ich eine Datei selber komplett von Hand komprimieren will und zu diesem Thema einen Algorythmus von einem Herren Huffman gefunden habe.
    Zuerst sollte ich das ganze File lesen bzw. scannen und alle Zeichen bzw. derren Anzahl speichern, sowie auch die Gesamtanzahl. Dann das vorkommen jedes Zeichens bewerten: wert=zeichenAnzahl/alleZeichen. Zusammen sollten die dann alle 1 ergeben.
    Soweit so gut.
    Nun soll man aber die schlechtesten(kleinster Wert) beiden Zeichen nehmen und als Blätter speichern und gleich einen Knoten machen. Dann die naechsten usw usw. Bis ich alle Zeichen irgendwo im Baum habe. Der Root-Knoten sollte wieder den Wert 1 haben.

    Jetzt würde ich gerne wissen wie man das so macht. Irgendwie fühlt es sich so an als ob man mal n paar Ziegel in die Luft legt, dann ein Dach darunter baut und irgendwann ist dann das Haus fertig.

    Thnx!

    0
  • M

    So ein Versuch läuft grad und nennt sich Pile Maschine oder so. Nur das die ein Filesystem entwickeln. Denn für eine Datei dürfte das keine allzu gute Komprimierung bringen. Da das ganze erst bei sehr großen Dateien vorteile bringen kann.

    0
  • C

    binaerer baum? viel schiesserei mit pointern und structs.

    was genau willst du wissen?

    0
  • ?

    Ohhh... so konkret gefragt... hmm... gute Frage.
    Vielleicht ob ich das richtig verstehe dass ein binärer Baum so in etwa eine verkettete Liste ist, aber immer 2 Nachfolger hat?

    Ich habe meine ganzen Bücher mal durch geschaut und irgendwie wird mehr Wert auf Listen als auf Baeume gelegt. Baeume werden immer nur angerissen und beschrieben, aber irgendwie nie so ganz konkret erklärt wie die Listen. Mit anderen Worten ich habe zwar verstanden was Baeume machen, sind, wo man sie brauchen kann, bin aber ziemlich unsicher was die Implementierung angeht...

    ---

    Für die Kompriemierung sollte der binäre Baum eigentlich ganz gut sein, da man nach dem erstellen des Baumes für jedes Zeichen einen binären String zusammen setzt, Zeichen die haeufig vorkommen werden sehr kurz. Je schlechter der Wert ist, desto länger werden die binären Strings. Sollten aber nie grösser als 8bit werden(wäre ja auch irgendwie sinnlos).

    0
  • C
     

    struct node {
    int value;
    struct node *child_a;
    struct node *child_b;
};

    damit baust du dann einen baum. entweder sind die child nodes benutzt, oder beide sind null und value ist benutzt.
    damit unterscheidest du zwischen "node" und "leaf", also zweig und blatt.

    http://de.wikipedia.org/wiki/Binärbaum

    0
  • ?

    Hi und danke. Wie das Struct aussehen muss wusste ich schon...

    Mir fehlt der naechste Step. Woher soll ich wissen ob ich etwas "links" od. "rechts" anfügen soll? Ich weiss ja auch noch nicht wo im Baum das Blatt sein soll.

    Nehmen wir an ich habe folgenden String:"ABBC"
    Die Wertigkeiten sind:
    A -> 0.25
    B -> 0.5
    C -> 0.25

    Ich packe also A und C und mache einen Knoten über die beiden. Zusammen haben sie eine Wertigkeit von 0.5, als kommt nun B dran. B und der vorherige Knoten kriegen wiederum einen Knoten. In diesem Falle ist das schon der Root Knoten.
    Wenn ich nun die Daten checke sollte ich mit:
    0 B erreichen
    10 C
    11 A
    Oder auch anderst herum.
    Wie entscheide ich also dass ein gleichmässiger Baum entsteht?

    (Ich hoffe das ich es irgendwie verständlich machen konnte...)

    Dank im vor.aus

    0
  • C

    http://de.wikipedia.org/wiki/Shannon-Fano-Kodierung#Huffman-Code

    0
Anmelden zum Antworten