Suppose we want to save the shape of an ordered tree of n node, each node has maximal 2 children. If it is a binary tree, we must use 2n bits. Since in our situation, we don't have left or right child, they are the same, so we must have some redundant sequences. So, can we encode it in a better way? It seems each node still have 3 cases, no child, one child, two children, but can we store it in less than 2 bits? Or in total have a better constant than 2?
To encode the shape of an ordered tree into bit sequence more efficiently
1
$\begingroup$
algorithms
graph-theory
-
0If I was correct. Please mark it so. – 2013-01-23
1 Answers
1
I believe what you're looking for is Huffman encoding.