How can I randomly generate trees?

Knuth says to look at it as generating all nested parentheses in lexicographic order.

Look here for the details

http://www-cs-faculty.stanford.edu/~uno/fasc4a.ps.

To generate a random tree you can use the following algorithm, where dst and src are two stacks:

dst := random permutation of all nodes;
src := empty stack
src.push(dst.pop()); % picks the root
while (!dst.empty()) {
  a := random element from src;
  b := dst.pop();
  add the edge (a, b)
  src.push(b);
}

Proof of correctness (all trees are possible and equally likely): Alexey S. Rodionov and Hyunseung Choo, On Generating Random Network Structures: Trees, ICCS 2003, LNCS 2658, pp. 879-887, 2003.