codice:
function inserisci(&$albero, $id, $id_padre, $nome) {
  $ris = false; 
  if($albero['id'] == $id_padre) {
      // trovato, aggiungi figlio
      $albero[] = array('id' => $id, 'nome' => $nome);
      $ris = true;
   else {
      // non trovato, cerca nei figli
      $i = 0;
      while(isset($albero[$i]))
         ris = inserisci($albero[$i++], $id, $id_padre, $nome);
   }
   return $ris;
}

$insiemeAlberi = array();
$query = mysql_query("SELECT * FROM menu ORDER BY ID");
while($rs = mysql_fetch_assoc($query))
   if($rs['id_padre'] == 0) // radice, crea un nuovo albero
      $insiemeAlberi[] = array('id' => $rs['id'], 'nome' => $rs['nome']);
   else {
      // è figlio di qualcuno, trovalo
      $trovato = false;
      for($i = 0; $i < count($insiemeAlberi) && !$trovato; $i++) // scorri tutti gli alberi
         $trovato = inserisci($insiemeAlberi[$i], $rs['id'], $rs['id_padre'], $rs['nome']);
   }
in questo modo dovremmo popolare tutti gli alberi, dico dovremmo perché non posso provarlo, è probabile che ci siano degli errori

per stamparlo basta richiamare la mia funzione di prima, con una leggera modifica:
codice:
function percorri($tree) {
   print $tree['nome'];
   $i = 0;
   while(isset($tree[$i]))
      percorri($tree[$i++]);
}

for($i = 0; $i < count($insiemeAlberi); $i++)
   percorri($insiemeAlberi[$i]);