In joint work with Ibrahim Salama, we study the complexity function pτ(n) of a labeled tree or tree shift, which counts as a function of n the number of different labelings of a shape of size n. We give a definition of entropy, prove that the limit in the definition exists, and that the limit is the infimum. For tree shifts determined by adjacency constraints a version of Pavlov's strip technique proves strict inequality with dimension and provides an efficient approximation method. Attractive questions concern equilibrium measures and relations with other kinds of entropy.