Código PHP:
<?php
$categorias = mysql_query("SELECT * FROM categorias");
while ($categoria = mysql_fetch_assoc($categorias)) {
if( is_null( $categoria['categoria_madre']) ){
$cate[ $categoria['categoria_id' ] ] ['super'] = $categoria['categoria_nombre'];
}
else{
$cate[ $categoria['categoria_madre' ] ] ['sub'] [ $categoria['categoria_id'] ] = $categoria['categoria_nombre'];
}
}
?>
<li><a href="#">TIENDA ONLINE</a><span></span>
<ul>
<?php
foreach($cate as $k=>$c ){
if( !array_key_exists('sub', $c)) {
?><li><a href="#"><?php echo $c['super']?></a></li>
<?php } else { ?>
<li><a href="#"><?php echo$c['super']?></a>
<ul>
<?php foreach($c['sub'] as $kk=>$cc){
?><li><a href="#"><?=$cc?></a></li>
<?php } ?>
</ul>
</li>
<?php
}
}
?>
</ul>
</li>
Tenes el codigo asi? Hiciste los cambios anteriores, fijate la parte donde se arma el array $cate.