I would suggest an approach like this:
<?php
$db = new mysqli('localhost', 'root', '', 'eurodib');
$query = "SELECT categorie.cat_name, sous_categorie.*
FROM sous_categorie, categorie
WHERE sous_categorie.parent_id=categorie.id_cat
ORDER BY categorie.cat_name";
$result = $db->query($query);
echo "<ul>\n";
$cat_name = '';
while ($row = $result->fetch_array())
{
if ($row['cat_name'] != $cat_name)
{
// End previous category, if any.
if ($cat_name != '')
{
echo "</ul>\n</li>\n";
}
// Begin the new category.
$cat_name = $row['cat_name'];
echo "<li><h2>" . htmlspecialchars($cat_name) . "</h2>\n<ul>\n";
}
echo "<li>" . htmlspecialchars($row['sous_cat_name']) . "</li>\n";
}
// End category, if any.
if ($cat_name != '')
{
echo "</ul>\n</li>\n";
}
echo "</ul>";
?>
For one thing, notice that it only uses one query instead of executing queries in a loop. The query orders by the cat_name, and then checks to see if the cat_name retrieved is different from the current cat_name. If it is, then presumably we are at the start of the next category. When printing strings to be displayed by the browser, you should escape them as I have done with [man]htmlspecialchars/man.
EDIT:
Incidentally, I have removed the line breaks from your list items. You should style your lists with CSS, not HTML. I have also fixed the incorrect nesting of lists and placed your main category names in level 2 headings (but you may want to change that).