java - Java中从哈夫曼树方法获取代码

Question

我编写的代码应该能够返回霍夫曼树中代码的 ArrayList。 Code 类有一个字符及其对应的编码。在树中，左边缘指定为0，右边缘指定为1。我使用两种方法来检索代码。

public ArrayList<Code> getCodes() {
        ArrayList<Code> code = new ArrayList<Code>();
        if (root == null) return null;
        traverse(code, root.left, "0");
        traverse(code, root.right, "1");
        return code;
}


private void traverse(ArrayList<Code> code, BinaryTreeNode<Letter> node, String prefix) {
        
    if(node==null){
        code.add(new Code(node.getElement().getLetter(), prefix));
    }
    else if (node.getLeft()!=null){
        traverse(code, node.getLeft(), prefix + "0");
    }
    else if (node.getRight()!=null){
        traverse(code, node.getRight(), prefix + "1");
    }

}

但是我得到的输出不正确。它应该看起来像这样，显示我的所有代码:

Start

Size of codes is 27

Code [ch= , code=00]

Code [ch=e, code=010]

Code [ch=n, code=0110]

Code [ch=i, code=0111]

Code [ch=b, code=100000]

Code [ch=p, code=100001]

Code [ch=y, code=100010]

Code [ch=g, code=100011]

Code [ch=o, code=1001]

[...]

但是，我得到了这个:

Start

Size of codes is 0

我的代码/字符/任何东西似乎都没有保存到我的 ArrayList 中。对于可能出现的问题有什么建议吗？

Answer 1

有两个问题:

• 如果getLeft不为null，traverse将不会调查getRight
• traverse 仅当 getLeft 或 getRight 不为 null 时才进行递归。这意味着您永远不会将 null 发送到 traverse 方法，但只有在 null 发送到 traverse 方法时才将结果添加到 code 数组(即从不发送)。

遍历方法大概应该是:

if(node==null){
    code.add(new Code(node.getElement().getLetter(), prefix));
} else {
    traverse(code, node.getLeft(), prefix + "0");
    traverse(code, node.getRight(), prefix + "1");
}

您还可以通过从 traverse(code, root, ""); 开始(而不是 traverse(...left) 和 traverse(...right))来使代码稍微更奇特(更短)