Javaのハフマンツリーメソッドからコードを取得

Question

ハフマンツリーのコードのArrayListを返すことができるコードを記述しました。 Codeクラスには、文字とそれに対応するエンコーディングがあります。ツリーでは、左端が0、右端が1と指定されています。コードを取得するには2つの方法があります。

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"); 
    } 

} 

しかし、出力が正しくありません。それはすべて私のコード表示、次のようになります。

スタートコードの

サイズは27

コードですが、[CH =、コード= 00]

コード[CH = E、コード= 010]

コード[CH = N、コード= 0109】

コード[CH = I、コード= 0111]

コード[CH = B、コード= 100000]

コード[CH = P、コード= 100001]

コード[CH = Y、コード= 100010]

コード[CH = G 、コード= 100011]

コード[CH = O、コード= 1001]

[...]

のBuトンではなく、私はこれを取得：コードの

スタート

サイズは、それは私のコード/文字のように/何かが私のArrayListに保存されていないようです0

です。何が間違っている可能性があるかに関する提案はありますか？

Answer 1

二つの問題があります。

• がgetLeftがnullでない場合は、トラバースはgetRight
• traverseを調査しませんがgetLeftまたはgetRightがnullでない場合にのみ再帰を行います。それはあなたがtraverseメソッドにnullを送信しないことが、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"); 
} 

また、あなたはどのように構築するか