Java实现遍历 Twig 生成位码的递归方法(哈夫曼编码)

Question

给定一棵二叉树，我想开发一种递归方法，在给定树根的情况下查找特定字符的位码(见图)

假设您有一个树类，其中每棵树都有 4 个字段 [左树、右树、左叶、右叶]，其中每个分支要么通向另一棵树，要么通向一片叶子(字符值)。

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

问题是您没有处理在子树中找不到目标的情况。即使在左树中没有找到目标，b += "0"+ traverse(t.lefttree,target, b);也会被执行。当你遍历正确的树时也可以这样说。事实上，即使已经在左树中找到目标，您的方法也会遍历右树。 add赋值运算符的使用进一步体现了这个问题。

另请注意，此函数不需要参数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;

}