[Sheryld]

можно еще как вариант, просатвить сначала всех родителей, а потом сразу выводить рекусривной функцией. но это решение в лоб. думаю попозже все-таки реализую функцию вставки ветви на в конкретное место, чтобы хранить дерево уже отсортированным.

решение:

$catObj = new Category2();
	
$catObj->EnumChildrenAll(1,"cat_LEFT");

$startTime = microtime();
	
	$nodes = array();
	$prevID = 0;
	$numElements = count($catObj->nodeInfoCollection);
	for($i<0;$i<$numElements;$i++)
	{
		if ($catObj->nodeInfoCollection[$i]["level"] != $prevLevel)
		{
			if ($catObj->nodeInfoCollection[$i]["level"] == 1)
			{
				$catObj->nodeInfoCollection[$i]["parent_id"] = 1;
			}
			else 
			{
				$catObj->nodeInfoCollection[$i]["parent_id"] = $prevID;
			}
			$prevID = $catObj->nodeInfoCollection[$i]["id"];					
		}
		else 
		{
			
			$catObj->nodeInfoCollection[$i]["parent_id"] = $catObj->nodeInfoCollection[$i-1]["parent_id"];
		}
		
		$prevLevel = $catObj->nodeInfoCollection[$i]["level"];		
	}
	
	function cmp($a,$b)
	{
		return strcmp($a["data"]["desc"],$b["data"]["desc"]);
	}
	
	function getChild($parentid, $array)
	{
		$retArray = array();
		foreach($array as $arrayItem)
		{
			if ($arrayItem["parent_id"] == $parentid)
			{				
				$retArray[] = $arrayItem;
			}
		}
		usort($retArray, "cmp");	
		return $retArray;
	}
	
	function walk($root, $collection)
	{
		//global $nodes;
		$ret = getChild($root,$collection);
		if (!empty($ret))
		{
			for($i=0;$i<count($ret);$i++)
			{
				echo str_repeat("&nbsp;", 4*$ret[$i]["level"]);
				echo $ret[$i]["data"]["desc"]; 
				echo "  <b>" . $ret[$i]["id"] . "</b>";
				echo "  <b>" . $ret[$i]["parent_id"] . "</b>";
				echo "<BR>"; 
				walk($ret[$i]["id"],$collection);
			}
		}
	}
	
	walk(1,$catObj->nodeInfoCollection);
	
	echo number_format(microtime() - $startTime,4);

оговорки, работает довольно медленно на больших объемах. не оптимизировано.