Why is my probability still using this binary tree?

Question

This is basically just an implementation of the Huffman coding algorithm, but when I check the probability of the end of the BinaryTree (the only item in the queue on the left), it is very high.

// Make a BinaryTree for each item in CharOccurrences and add as an entry in initialQueue for (int i = 0; i < charOccurrences.size(); i++) { BinaryTree<CharProfile> bTree = new BinaryTree<CharProfile>(); bTree.makeRoot(charOccurrences.get(i)); initialQueue.add(bTree); } // Create the BinaryTree that we're adding to the resultQueue BinaryTree<CharProfile> treeMerge = new BinaryTree<CharProfile>(); // Create the CharProfile that will hold the probability of the two merged trees CharProfile data; while (!initialQueue.isEmpty()) { // Check if the resultQueue is empty, in which case we only need to look at initialQueue if (resultQueue.isEmpty()) { treeMerge.setLeft(initialQueue.remove()); treeMerge.setRight(initialQueue.remove()); // Set treeMerge data to be the sum of its two child trees' probabilities with a null char value data = new CharProfile('\0'); data.setProbability(treeMerge.getLeft().getData().getProbability() + treeMerge.getRight().getData().getProbability()); treeMerge.setData(data); } else { // Set the left part of treeMerge to the lowest of the front of the two queues if (initialQueue.peek().getData().getProbability() <= resultQueue.peek().getData().getProbability()) { treeMerge.setLeft(initialQueue.remove()); } else { treeMerge.setLeft(resultQueue.remove()); } if (!initialQueue.isEmpty()) { // Set the right part of treeMerge to the lowest of the front of the two queues if (initialQueue.peek().getData().getProbability() <= resultQueue.peek().getData().getProbability()) { treeMerge.setRight(initialQueue.remove()); } else { treeMerge.setRight(resultQueue.remove()); } } // In the case that initialQueue is now empty (as a result of just dequeuing the last element), simply make the right tree resultQueue head else { treeMerge.setRight(resultQueue.remove()); } // Set treeMerge data to be the sum of its two child trees' probabilities with a null char value data = new CharProfile('\0'); data.setProbability(treeMerge.getLeft().getData().getProbability() + treeMerge.getRight().getData().getProbability()); treeMerge.setData(data); } // Add the new tree we create to the resultQueue resultQueue.add(treeMerge); } if (resultQueue.size() > 1) { while (resultQueue.size() != 1) { treeMerge.setLeft(resultQueue.remove()); treeMerge.setRight(resultQueue.remove()); data = new CharProfile('\0'); data.setProbability(treeMerge.getLeft().getData().getProbability() + treeMerge.getRight().getData().getProbability()); treeMerge.setData(data); resultQueue.add(treeMerge); } } 

Then I get this at the end:

 System.out.println("\nProbability of end tree: " + resultQueue.peek().getData().getProbability()); 

What gives me:

Finite Tree Probability: 42728.31718061674

Answer 1

Move the following lines inside the while loop:

 // Create the BinaryTree that we're adding to the resultQueue BinaryTree<CharProfile> treeMerge = new BinaryTree<CharProfile>(); 

Otherwise, one iteration adds treeMerge to resultQueue , and the next can do treeMerge.setLeft(resultQueue.remove()); that makes treeMerge child in itself ...