PHPとMySQLを使い、登録データをツリー表示したいと思っています。

2分木の配列 $node_list を用意し、IDのみを代入する形にしてみました。

$node_list は1次元目の要素にIDを、2次元目の 'next' には隣のIDを、'child' には子どものIDを持ちます。要素がない場合（終端）には NULL を代入します。next や child は、メモリが許す限り増やすことができます。

//2分木を用意する
$node_list = array();
$node_list[0]['next']  = NULL;
$node_list[0]['child'] = NULL;

$sql = "SELECT * FROM test_db ORDER BY parent_id,sort";
$res = mysql_query($sql, $con);

while ($row = mysql_fetch_array($res)) {
    $id = $row['id'];
    $parent_id = $row['parent_id'];
    $name[$id] = $row['name'];
    $node = 0;
    while (TRUE) {
        //子ノードに追加
        if ($node_list[$parent_id]['child'] == NULL) {
            $node_list[$parent_id]['child'] = $id;
            $node_list[$id]['next']  = NULL;
            $node_list[$id]['child'] = NULL;
            break;
        //次ノードに追加
        } else {
            $node = $node_list[$parent_id]['child'];
            if ($node_list[$node]['next'] == NULL) {
                $node_list[$node]['next']  = $id;
                $node_list[$node]['child'] = NULL;
                $node_list[$id]['next']    = NULL;
                $node_list[$id]['child']   = NULL;
                break;
            }
        }
    }
}

ご質問のケースでは、$node_list の内容は下記のようになります。

$node_list[0]['next']  = NULL;
$node_list[0]['child'] = 1;
$node_list[1]['next']  = 2;
$node_list[1]['child'] = 4;
$node_list[2]['next']  = NULL;
$node_list[2]['child'] = NULL;
$node_list[3]['next']  = NULL;
$node_list[3]['child'] = 5;
$node_list[4]['next']  = 3;
$node_list[4]['child'] = NULL;
$node_list[5]['next']  = NULL;
$node_list[5]['child'] = NULL;

これを順番に追ってもらえれば、目的のツリー構造が表現できるのではないかと思います。