java - 为什么我使用这个二叉树的概率如此之大？

Question

它基本上只是霍夫曼编码算法的一个实现，但是当我检查结束二叉树(队列中唯一剩下的项目)的概率时，它非常高。

// 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

Answer 1

在 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 ......