Javaツリーの枝を走査してビットコードを生成する再帰的メソッドを実装する（ハフマン符号化）

Question

バイナリツリーが与えられているツリーのルートを与えられた特定の文字のビットコードを見つける再帰的メソッドを開発したい（図参照）

すべての木が4つの分野すべての分岐はどちらか別のツリーまたはリーフ（char値）につながっ[左側のツリー、右ツリー、左の葉、右葉]を持っていた場所がツリークラスを持っていたとします。

String result = traverse(root, 'c', ""); //1011 

public static String traverse(Tree t, char target, String bitcode){ 

     String b = bitcode; 

     if (t.leftleaf != null){ 
      if (t.leftleaf == target) { 
      b += "0"; 
      } 
     } 
     if (t.rightleaf != null){ 
      if (t.rightleaf == target){ 
      b += "1";  
      } 
     } 

     if (t.lefttree != null){ 
      b += "0" + traverse(t.lefttree,target, b); 
     } 
     if (t.righttree != null){ 
      b += "1" + traverse(t.righttree,target, b); 

     } 

     return b; 

    } 

ただし、上記の方法は期待どおりに機能しません。ビットコードが正しく表示されるように、どのように書き直すことができますか？

Answer 1

をデコードすると、つまりバイナリコードからキャラクタに移動するときに、ルートからリーフに向かってツリーを移動します。

エンコードの場合は、文字のインデックスを持っていなければならず、次に各ツリーノードがその親を指し示すようにする必要があります。 またはの場合、エンコードツリーを1回たどって、エンコードテーブルを作成し、可能な入力文字ごとに最終的なハフマンコードを出力することができます。

Answer 2

問題は、ターゲットがサブツリーに見つからない場合を処理していないことです。左ツリーにターゲットが見つからない場合でも、b += "0" + traverse(t.lefttree,target, b);が実行されます。右のツリーをたどると同じことが言えます。実際には、ターゲットが左のツリーにすでに見つかっていても、正しいツリーをトラバースします。加算代入演算子を使用すると、この問題がさらに顕在化します。

この機能では、パラメータString bitcodeは動作しません。

public static String findBitcode(Tree t, char target){ 

    // See if target immediately available 
    if (t.leftleaf == target) return "0"; 
    if (t.rightleaf == target) return "1"; 

    // Search deeper 
    String leftResult = findBitcode(t.leftree, target); 
    if (leftResult != null) return "0" + leftResult; 
    String rightResult = findBitcode(t.righttree, target); 
    if (rightResult != null) return "1" + rightResult; 

    // Not found 
    return null; 

}