Java

Problem debugging method for Binary Tree

Please support our Java advertiser: Programming Forums - DaniWeb Sister Site

•

Join Date: Sep 2008

Posts: 1,649

Reputation: BestJewSinceJC is a splendid one to behold

Solved Threads: 206

BestJewSinceJC BestJewSinceJC is offline

Offline

Posting Virtuoso

Problem debugging method for Binary Tree

Dec 8th, 2008

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
public void generateBits(Node root, int current, int counter){
		if (root== null) return;
 
		if (root.left == null && root.right == null){
			list.add(new HuffCode(root.theChar, current, counter));			
		} else{
			current<<= 1; //move all the bits 1 spot to the left
			generateBits(root.left, current, counter+1);
			generateBits(root.right, (current | 1), counter+1);
		}
	}
public void generateBits(Node root, int current, int counter){
		if (root== null) return;
			
		if (root.left == null && root.right == null){
			list.add(new HuffCode(root.theChar, current, counter));			
		} else{
			current<<= 1; //move all the bits 1 spot to the left
			generateBits(root.left, current, counter+1);
			generateBits(root.right, (current | 1), counter+1);
		}
	}

Somehow, this method is generating wrong bit sequences for the Huffman Code. Specifically, the SAME bit sequences are being generated for different Nodes, which should be impossible... the way I'm trying to generate the bit sequences is "if you move left in the tree, add a 0 to the bit sequences, if you move right in the tree, add a 1 to the bit sequence. If you're at a leaf node, stop, and create a new HuffCode". Regardless of how the tree was created, there can only be one Node at any given position. Therefore, I should never have the same bit sequence twice, but I do. So there has to be something wrong with my method, right? I can't see what.

•