从 Java 中的霍夫曼树方法获取代码

Question

我编写的代码应该能够 return 我的霍夫曼树中代码的 ArrayList。 Code class 有一个字符及其对应的编码。在树中，左边缘被指定为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

我的 codes/characters/anything 似乎没有保存到我的 ArrayList 中。关于可能出现的问题有什么建议吗？

Answer 1

有两个问题：

如果getLeft不是null，traverse不会调查getRight
traverse 仅在 getLeft 或 getRight 不为空时才进行递归。这意味着您永远不会将 null 发送到 traverse 方法，但如果 null 被发送到遍历方法（即从不），您只会将结果添加到 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)）

来使代码更漂亮（更短）

从 Java 中的霍夫曼树方法获取代码

Getting codes from Huffman tree method in Java

java

huffman-code