<?php
header('Content-Type: text/html; charset=iso-8859-1');
    function mkmap($dir,$niveau=1){
    global $adresse;
        echo "<ul>";
        $dossier=$_GET['s'];
        $folder = opendir ($dir);
        // on boucle le dossier
        while ($file = readdir ($folder)) {
            if ($file != "." && $file != "..") {
                $pathfile = $dir.'\\'.$file;
                // $urlFolder = str_replace("D:\\Videos\\", "", $pathfile);
                // $urlFolder = str_replace("\\", "/", $urlFolder);
                $adresseVideo = str_replace("D:\\Videos\\", "", $pathfile);
                $adresseVideo = str_replace("\\", "/", $adresseVideo);
                $urlFolder = $adresseVideo;
                $path = str_replace("\\", "/", $pathfile);
                $extension=strrchr($file,'.');
                $extension=substr($extension,1) ;
                $urlIcon = $adresse.$urlFolder.'/';
                $icon = 'icon.png';
                $image = file_exists($pathfile . "/icon.png") ? '<img style="width:18px;height:18px;" src="'.$urlIcon.'icon.png" />' : '';
                /*
                 * on vérifie l'extention du fichier
                 * on dois pouvoir vérifier des extentions pour les vidéos et les pdf et afficher un lien différent si il s'agit d'un pdf
                 */
                if ($extension=="mp4" || $extension=="mov" || $extension=="avi" || $extension=="mkv") {
                    $namef=preg_replace("`(.+)\_Grafikart - Tutoriel `isU", "", $file);
                    echo '<li><a href="index.php?s='.$dossier.'&v='.$adresseVideo.'">'.$namef.'</a></li>';
                } else if ($extension=="pdf") {
                    echo '<li><a href="index.php?s='.$dossier.'&pdf='.$adresseVideo.'">'.$file.'</a></li>';
                } else {
                    $namef=preg_replace("`(.+)\_`isU", "", $file);
                    $namef=str_replace("icon.png", "", $namef);
                    // on affiche l'icone si il y'en a
                    if ($niveau==1){
                        echo '<li><span class="titre">'.$image.' '.ucfirst($namef).'</span></li>';
                    }else if ($niveau==2){
                        echo '<li><span class="soustitre">'.$image.' '.ucfirst($namef).'</span></li>';
                    }
                    else{
                        echo '<li><span class="dossier">'.$image.' '.ucfirst($namef).'</span></li>';
                    }
                    if(filetype($pathfile) == 'dir'){            
                        mkmap($pathfile,$niveau+1);
                    }
                }
                // echo $url3.$url2.$url1;
            }
        }
        closedir ($folder);    
        echo "</ul>";
    }
?>

function niveau($niveau)
{
  echo $niveau;
  niveau($niveau + 1);
}
niveau(0);

Il faudrait rajouter à ta fonction récursive(en paramètre) le niveau de profondeur du dossier sollicité.
Avec cette nouvelle information tu pourrais décider d'appliquer un h3 ou un h4.

if( file_exists($pathfile . "/icon.png") )
  echo '<img src="" />';

Dossier primaire

• Dossier secondaire 01
  • video01
    video02
  • Dossier tertiaire
    • video02

• Dossier secondaire 02

...
...

<?php
    function mkmap($dir){
        echo "<ul>";   
        $folder = opendir ($dir);
        $authextension = 'mp4';
        // on boucle le dossier
        while ($file = readdir ($folder)) {
            if ($file != "." && $file != "..") {
                $pathfile = $dir.'/'.$file;
                $extension=strrchr($file,'.');
                $extension=substr($extension,1) ;
                /*
                 * on vérifie l'extention du fichier
                 */
                // si il n'y en a pas, alors il s'agit d'un dossier
                if ($extension == $authextension) {
                    $namef=preg_replace("`(.+)\_Grafikart - Tutoriel `isU", "", $file);
                    echo '<li><a href="'.$pathfile.'" target="_blank">'.$namef.'</a></li>';
                // sinon c'est u fichier
                } else {
                    $namef=preg_replace("`(.+)\_`isU", "", $file);
                    echo '<li><h4>'.$namef.'<h4></li>'."\n"; 
                    if(filetype($pathfile) == 'dir'){            
                        mkmap($pathfile);
                    }
                }
            }
        }
        closedir ($folder);    
        echo "</ul>";
    }
?>