它基本上只是霍夫曼编码算法的一个实现,但是当我检查结束二叉树(队列中唯一剩下的项目)的概率时,它非常高。
// 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's 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's head
else {
treeMerge.setRight(resultQueue.remove());
}
// Set treeMerge's 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);
}
}
然后我在最后有这个:
System.out.println("\nProbability of end tree: "
+ resultQueue.peek().getData().getProbability());
这给了我:
Probability of end tree: 42728.31718061674
最佳答案
在 while 循环中移动以下行:
// Create the BinaryTree that we're adding to the resultQueue
BinaryTree<CharProfile> treeMerge = new BinaryTree<CharProfile>();
否则,一次迭代将 treeMerge
添加到 resultQueue
,下一次可能会执行 treeMerge.setLeft(resultQueue.remove());
,这使得 treeMerge
成为它自己的 child ......
关于java - 为什么我使用这个二叉树的概率如此之大?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13198795/