152 8. Trees
Indeed, when this entry (say, thek-th entry in the first row) was recorded,
the nodes before it in the first row were deleted (together with the edges
corresponding to the firstk−1 columns). The remaining entries in the
second row are exactly those nodes that are fathers at this time, which
means that they are not leaves.
This describes how the first row can be reconstructed from the second.
So we don’t need the full extended Pr ̈ufer code to store the tree; it suffices
to store the second row. In fact, we know that the last entry in the second
row is 0, so we don’t have to store this either. The sequence consisting of
the firstn−2 entries of the second row is called thePr ̈ ufer codeof the tree.
Thus the Pr ̈ufer code is a sequence of lengthn−2, each entry of which is
a number between 0 andn−1.
This is similar to the father code, just one shorter; not much gain here
for all the work. But the beauty of the Pr ̈ufer code is that it is optimal, in
the sense that
every sequence of numbers between 0 andn− 1 , of lengthn− 2 ,
is a Pr ̈ufer code of some tree onnnodes.This can be proved in two steps. First, we extend this sequence to a table
with two rows: We adda0attheend, and then write above each entry in
the first row the smallest integer that does not occur in the first row before
it, nor in the second row below or after it (note that it is always possible
to find such an integer: the condition excludes at mostn−1 values out of
n).
Now this table with two rows is the Pr ̈ufer code of a tree. The proof of
this fact, which is no longer difficult, is left to the reader as an exercise.
8.4.3Complete the proof.Let us sum up what the Pr ̈ufer code gives. First, it proves Cayley’s
theorem. Second, it provides a theoretically most efficient way of encoding
trees. Each Pr ̈ufer code can be considered as a natural number written
in the base-nnumber system; in this way, we associate a “serial number”
between 0 andnn−^2 −1 with eachn-point labeled tree. Expressing these
serial numbers in base two, we get a code using 0–1 sequences of length at
most(n−2) log 2 n.
As a third use of the Pr ̈ufer code, let’s suppose that we want to write a
program that generates a random labeled tree onnnodes in such a way
that all trees occur with the same probability. This is not easy from scratch;
but the Pr ̈ufer code gives an efficient solution. We just have to generate
n−2 independent random integers between 0 andn−1 (most programming
languages have a statement for this) and then “decode” this sequence as a
tree, as described.