Ci ho pensato e ripensato e sono arrivato a questa conclusione:
Le tabelle "relazioni" e "prodotti" vanno bene per come sono, ma la tabella "categorie" dovrebbe essere così composta:
codice:
------------------------------------------------
id |       nome           | sx | dx | prodotti |
------------------------------------------------
 1 | Categoria Principale |  1 | 12 |     0    |
 2 | Abbigliamento        |  2 |  5 |     0    |
 3 | Calzature            |  6 | 11 |     0    |
 4 | Giacche              |  3 |  4 |     0    |
 5 | Scarpe               |  7 | 10 |     0    |
 6 | Da Ginnastica        |  8 |  9 |     1    |
------------------------------------------------
La colonna prodotti non fa altro che indicarmi se ci sono prodotti sotto quella categoria (in questo caso lancio una seconda query nel ciclo che mi mette in lista il campo "nome_prod" della tabella "prodotti").
Il codice che dovrei stampare è questo:
codice:
d.add(1,-1,'Categoria Principale','insert_under.php?id=1');
d.add(2,1,'Abbigliamento','insert_under.php?id=2');
d.add(4,2,'Giacche','insert_under.php?id=4');
d.add(3,1,'Calzature','insert_under.php?id=3');
d.add(5,3,'Scarpe','insert_under.php?id=5');
d.add(6,5,'Da Ginnastica','insert_under.php?id=6');
d.add(10000001,6,'Nike 707','scheda.php?id=1','','','img/page.gif');
Che è così generato...
1)Di default è così composto:
codice:
d.add(ID-CATEGORIA,ID-CATEGORIA-NELLA-QUALE-E'-CONTENUTA,'NOME-CATEGORIA','insert_under.php?id=ID-CATEGORIA');
2)Nel caso sia una categoria principale il secondo campo deve essere -1
codice:
d.add(ID-CATEGORIA,-1,'NOME-CATEGORIA','insert_under.php?id=ID-CATEGORIA');
2)Nel caso sia un prodotto (cioè se nella colonna "prodotti" c'è il valore settato ad 1) il codice dovrebbe essere:
codice:
d.add(1000000+ID-PRODOTTO,ID-CATEGORIA-NEL-QUALE-E'-CONTENUTO,'NOME-PRODOTTO','scheda.php?id=ID-PRODOTTO','','','img/page.gif');
Aggiungo 1000000 all'id del prodotto poichè nel codice non ci possono essere due id con valore uguale (in questo caso sono il prodotto "Nike 707" e la "Categoria Principale" che hanno tutti e due id=1) perciò ipotizzo che il numero max di categorie che posso raggiungere è 10.000.000 e gli aggiungo l'id cosi il nuovo id per javascript del prodotto è 10000001,10000002 ecc..

Spero di non aver detto cavolate... ma non riesco a trovare un metodo migliore!
Ora l'unico problema che non so come risolvere è: Come faccio a sapere l'id della categoria nella quale è contenuta ogni categoria?
Cioè nell'esempio di giacche (che ha l'id 4) come faccio a calcolarmi l'id della categoria Abbigliamento (cioè id 2) che la contiene?
Vi ringrazio ancora per l'attenzione!