编码二叉树的更好方法是什么？

Question

我正在实施霍夫曼压缩算法。我有一个二叉树，其中包含源的每个字符，我需要能够根据给定字符在树中的位置对其进行编码。例如：

  /\            If we use this tree, and say that a 0 represents the left branch,
 a  |           and a 1 represents the right branch, our encoded characters would
   / \          be:
  |   b              a = 0    b = 11
 / \                 c = 100  d = 101
c   d

我目前使用的指定字符编码方法是这样的：

treeHas(char, tree){
     if(tree = Leaf) return char == tree.value
     else return treeHas(char, tree.left) || treeHas(char, tree.right)
}

encodeChar(char, tree){
     if(treeHas(tree.left)) return concat("0", encodeChar(char, tree.left))
     if(treeHas(tree.right)) return concat("1", encodeChar(char, tree.right))
     error
}

有效，但效率似乎很低。 treeHas 和 encodeChar 都递归遍历树。有没有更高效的算法？也许只走过一次树？

Answer 1

这是一次性收集所有编码的方法；在 JavaScript:

function encode(tree, path="") {
    if (!tree.left && !tree.right) return [[tree.value, path]];
    let result = [];
    if (tree.left ) result = result.concat(encode(tree.left , path + "0"));
    if (tree.right) result = result.concat(encode(tree.right, path + "1"));
    return result;
}

// Demo
let tree = {
    left: { value: "a" },
    right: {
        left: {
            left: { value: "c" },
            right: { value: "d" }
        },
        right: { value: "b" }
    }
};
let result = encode(tree);
console.log(result);

编码二叉树的更好方法是什么？

What is a better way to encode a binary tree?

algorithm

tree

binary-tree