无限的父子关系树如何排序?

Question

数据结构大概是这样的.{id:parentIds} id是唯一的,parentIds储存了上级的ids.例如父类为id=1下的id=5下的id=9 parentIds就为1,5,9 最高层的parentIds为0 那这样如何进行一个排序呢?

例如现在的数据是:

array(
    '1'=>'0',
    '2'=>'0',
    '3'=>'0',
    '4'=>'1',
    '5'=>'1',
    '6'=>'2',
    '7'=>'1',
    '8'=>'1',
    '9'=>'2',
    '10'=>'3',
    '11'=>'3',
    '12'=>'2',
    '13'=>'1',
    '14'=>'1,8',
    '15'=>'1,8,14',
    '16'=>'2,9',
    '17'=>'1,8',
    '18'=>'3,10',
    '19'=>'3,11',
    '20'=>'3,10,18',
    '21'=>'1,8,14,15',
    '22'=>'1,8,14');

处理过后(同级可不按顺序):

array(
    '1'=>'0',
    '4'=>'1',
    '5'=>'1',
    '7'=>'1',
    '8'=>'1',
    '14'=>'1,8',
    '15'=>'1,8,14',
    '22'=>'1,8,14');
    '21'=>'1,8,14,15',
    '17'=>'1,8',
    '13'=>'1',
    '2'=>'0',
    '6'=>'2',
    '9'=>'2',
    '16'=>'2,9',
    '12'=>'2',
    '3'=>'0',
    '10'=>'3',
    '18'=>'3,10',
    '20'=>'3,10,18',
    '11'=>'3',
    '19'=>'3,11',

Answer 1

把path转换成版本号进行对比排序

$a = [
    '1' => '0',
    '2' => '0',
    '3' => '0',
    '4' => '1',
    '5' => '1',
    '6' => '2',
    '7' => '1',
    '8' => '1',
    '9' => '2',
    '10' => '3',
    '11' => '3',
    '12' => '2',
    '13' => '1',
    '14' => '1,8',
    '15' => '1,8,14',
    '16' => '2,9',
    '17' => '1,8',
    '18' => '3,10',
    '19' => '3,11',
    '20' => '3,10,18',
    '21' => '1,8,14,15',
    '22' => '1,8,14',
];

$result = treeSort($a);
print_r($result);

function treeSort($arr)
{
    $list = [];
    foreach ($arr as $key => $item) {
        $version = $item == 0 ? $item : ('0.' . $item);
        $list[] = [$key, str_replace(',', '.', $version) . '.' . $key];
    }
    $mySort = function ($a, $b) {
        return version_compare($a[1], $b[1], 'ge');
    };
    usort($list, $mySort);
    $tree = [];
    foreach ($list as $item) {
        $tree[$item[0]] = $arr[$item[0]];
    }
    return $tree;
}