Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (739)
Games in Android Showcase (224)
games submitted by our members
Games in WIP (820)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Recursive loop in Huffman Tree  (Read 3933 times)
0 Members and 1 Guest are viewing this topic.
Offline Serethos

Junior Devvie

Java games rock!

« Posted 2004-05-31 12:11:08 »

recursive loops are not my strong side so i need some help:

ive made a huffman tree, which consist of two elements: leaves and nodes (leaves carry the character information, the nodes get calculated).  each node has the information of which two elements came before (called leftElement and rightElement). per isLeaf() you can test if its a leaf and therefore you reached the end of a brunch.

to create an easy tree i sort the leaves at the beginning so that each huffman tree looks like this: e.g.:

10%              20%             30%                 40%
A                    B                   C                     D
    |            |          |           |        |           |
     Node1              |        |           |         |
        |--------------  Node2              |      |
                                 |                   |     |
                                 -----------     Node3

hope it doesnt look too confusing =)

now my problem: i need to generate the code itself with an recursion so that every node/leaf gets walked through an for each left branch a '0' is remembered and for each right branch a '1'. important is, that i need to save the result after a leave is reached.
i had some experiments, but no good result.
Offline Serethos

Junior Devvie

Java games rock!

« Reply #1 - Posted 2004-05-31 12:22:28 »

hmmm, ascii format got lost, better:
Offline Serethos

Junior Devvie

Java games rock!

« Reply #2 - Posted 2004-05-31 13:31:21 »

ok, questions is still alive, but ilve noticed, that it is absolutely  wrong to state, that in presorted order the tree always looks like ive displayed ....
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline crystalsquid

Junior Devvie

... Boing ...

« Reply #3 - Posted 2004-06-01 09:39:27 »

I don't think presorting will ever get you a nice neat code like you said first. It depends on the probablility of the sources.

Anyway, to recurse the tree, you need something like this:

class Node
    Node left;
    Node right;
    int code;
    int codeBits;

    void BuildCode( int depth, int currentCode )
          code = currentCode;
          codeBits = depth;

          // Give '0' for left
          if(left != null)
              left.BuildCode(depth+1, code<<1);
          // Give '1' for right
          if(right != null)
              right.BuildCode(depth+1, (code<<1)+1);

You call this by doing:

The root node will get code 0, length 0. Its 'left' will be 0, 1bit, the right '1, 1 bit', and so on down the tree.
Decoding can be done by traversing the tree itself and taking left/right branches as the bits dictate until you reach a 'null' reference. Then the node you are in is the character denoted by the Huffman code.

As an aside, you can create a more efficient tree by using a state machine. I can't remember the code but a bit of googling should find it. Its a bit harder to understand though!

Hope this helps,

- Dom
Offline Serethos

Junior Devvie

Java games rock!

« Reply #4 - Posted 2004-06-02 17:18:36 »

at least ive solved the problem by myself, but thx a lot for your answer. i should only test which algorithm is better  Smiley
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

Ecumene (54 views)
2017-09-30 02:57:34

theagentd (77 views)
2017-09-26 18:23:31

cybrmynd (185 views)
2017-08-02 12:28:51

cybrmynd (183 views)
2017-08-02 12:19:43

cybrmynd (190 views)
2017-08-02 12:18:09

Sralse (200 views)
2017-07-25 17:13:48

Archive (748 views)
2017-04-27 17:45:51

buddyBro (882 views)
2017-04-05 03:38:00

CopyableCougar4 (1431 views)
2017-03-24 15:39:42

theagentd (1322 views)
2017-03-24 15:32:08
List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05

SF/X Libraries
by SkyAphid
2017-03-02 06:38:56

SF/X Libraries
by SkyAphid
2017-03-02 06:38:32

SF/X Libraries
by SkyAphid
2017-03-02 06:38:05

SF/X Libraries
by SkyAphid
2017-03-02 06:37:51 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!