  For each integer $k \geq 2$, we introduce a sequence of $k$-ary discrete
trees constructed recursively by choosing at each step an edge uniformly among
the present edges and grafting on "its middle" $k-1$ new edges. When $k=2$,
this corresponds to a well-known algorithm which was first introduced by
R\'emy. Our main result concerns the asymptotic behavior of these trees as $n$
becomes large: for all $k$, the sequence of $k$-ary trees grows at speed
$n^{1/k}$ towards a $k$-ary random real tree that belongs to the family of
self-similar fragmentation trees. This convergence is proved with respect to
the Gromov-Hausdorff-Prokhorov topology. We also study embeddings of the
limiting trees when $k$ varies.
