Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (109)
games submitted by our members
Games in WIP (536)
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 1946 times)
0 Members and 1 Guest are viewing this topic.
Offline Serethos

Junior Member




Java games rock!


« Posted 2004-05-31 14: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 Member




Java games rock!


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

hmmm, ascii format got lost, better:
Offline Serethos

Junior Member




Java games rock!


« Reply #2 - Posted 2004-05-31 15: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 Member




... Boing ...


« Reply #3 - Posted 2004-06-01 11: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:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
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:
1  
rootNode.BuildCode(0,0);

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 Member




Java games rock!


« Reply #4 - Posted 2004-06-02 19: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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CogWheelz (18 views)
2014-07-30 21:08:39

Riven (27 views)
2014-07-29 18:09:19

Riven (16 views)
2014-07-29 18:08:52

Dwinin (14 views)
2014-07-29 10:59:34

E.R. Fleming (35 views)
2014-07-29 03:07:13

E.R. Fleming (13 views)
2014-07-29 03:06:25

pw (44 views)
2014-07-24 01:59:36

Riven (44 views)
2014-07-23 21:16:32

Riven (30 views)
2014-07-23 21:07:15

Riven (31 views)
2014-07-23 20:56:16
List of Learning Resources
by SilverTiger
2014-07-31 18:29:50

List of Learning Resources
by SilverTiger
2014-07-31 18:26:06

List of Learning Resources
by SilverTiger
2014-07-31 13:54:12

HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54
java-gaming.org 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‑gaming.org
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!