<?php
$arr = [
    ['id' => 1, 'parent_id' => 0, 'name' => 'root'],
    ['id' => 2, 'parent_id' => 1, 'name' => 'child_1'],
    ['id' => 3, 'parent_id' => 2, 'name' => 'child_1.1'],
    ['id' => 4, 'parent_id' => 2, 'name' => 'child_1.2'],
    ['id' => 5, 'parent_id' => 1, 'name' => 'child_2'],
    ['id' => 6, 'parent_id' => 5, 'name' => 'child_2.1'],
    ['id' => 7, 'parent_id' => 5, 'name' => 'child_2.2'],
    ['id' => 8, 'parent_id' => 2, 'name' => 'child_1.3'],
];

$initRight = 0;
$depth = 0;
$data = [];
foreach ($arr as $key => $val) {
    if (count($data) > 0) {
        $ids = array_column($data, 'id');
        $index = array_search($val['parent_id'], $ids);
        $right = $data[$index]['right'];
        $depth = $data[$index]['depth'];
        //$data = update($data, $right);
        foreach ($data as $k => $v) {
            if ($v['left'] > $right) {
                $data[$k]['left'] += 2;
            }
            if ($v['right'] >= $right) {
                $data[$k]['right'] += 2;
            }
        }
        $data[] = [
            'id' => $val['id'],
            'parent_id' => $val['parent_id'],
            'name' => $val['name'],
            'left' => $right,
            'right' => $right + 1,
            'depth' => $depth + 1
        ];
    } else {
        //初始化
        $data[] = [
            'id' => $val['id'],
            'parent_id' => $val['parent_id'],
            'name' => $val['name'],
            'left' => $initRight + 1,
            'right' => $left + 2,
            'depth' => $depth
        ];
    }

}

function update($data, $right){
    foreach ($data as $key => $val) {
        if ($val['left'] > $right) {
            $data[$key]['left'] += 2;
        }
        if ($val['right'] >= $right) {
            $data[$key]['right'] += 2;
        }
    }

    return $data;
}
?>