Replace in sitemap.php
$cat_list .= "<img src=\"".get_gallery_image("folder".$folder.".gif")."\" alt=\"\">";
with:
$cat_list .= "<img src=\"".get_gallery_image("folder".$folder.".gif")."\" alt=\"\" align=\"left\">";
Or
Replace it with:
$cat_list .= "<table><td>";
$cat_list .= "<img src=\"".get_gallery_image("folder".$folder.".gif")."\" alt=\"\">";
$cat_list .= "</td><td valign=\"middle\">";
Then, below
$cat_list .= "<b><a href=\"".$site_sess->url(ROOT_PATH."categories.php?cat_id=".$category_id)."\">".multilang($cat_cache[$category_id]['cat_name'])."</a></b> ".$cat_info."<br />";
and
$cat_list .= sitemap_bits($cat_id, $category_id, $depth + 1, $bg, 1);
Add:
$cat_list .= "</td></table>";
P.S.
Not tested.