One possibility is to use an algorithm called simplex noise, invented by Ken Perlin (known for Perlin Noise). One nice feature of simplex noise (like Perlin noise) is that it can be tiled - ie, only a small region out of the potential area needs to be calculated and this can be repeated over the entire area without visible seams.
For the noise function to be repeatable, i.e. always yield the same value for a given input point,
gradients need to be pseudo-random, not truly random. They need to have enough variation to conceal the fact that the
function is not truly random, but too much variation will cause
unpredictable behaviour for the noise function
Simplex noise can be generated faster than Perlin noise and does not require a random number generator. It is not arbitrary to implement just by knowing the theory, but there is some source code to help you along (referenced from Wikipedia).
Other options for generating pseudo-random noise are fractals and wavelets.
On your situation you would use one of these techniques to generate a series of data in one dimension, and then apply a threshold to determine whether a tree should be placed at that position.