最近工作中用到了關于無限極分類的功能，于是查詢了一下相關內容晴竞。
無限極分類有兩種實現方式
- 毗鄰目錄模式
- 預排序遍歷樹算法
要了解這兩種方式具體內容洞焙，可以去查看這篇博客： 左右值無限分類實現算法
本文主要提供兩種將符合無限極分類格式的二維數組轉化為樹狀形式數組方法吕朵。
- 毗鄰目錄模式
function getNodeTree(&$list,&$tree,$pid=0){
foreach($list as $key=>$value){
if($pid == $value['parent']){
$tree[$value['id']]=$value;
unset($list[$key]);
getNodeTree($list,$tree[$value['id']]['children'],$value['id']);
}
}
}
其中第一個參數為需要處理的數組绰垂，$tree即為最后所需結果嗅榕。
- 預排序遍歷樹算法
上面的文章中對于預排序遍歷樹算法的描述我覺得不夠生動顺饮，所以在下面重新畫了一幅圖用來描述這種結構。
image.png
我們將一個折看成一個節(jié)點凌那，其中1-14為父節(jié)點兼雄，2-7、8-9帽蝶、10-11赦肋、12-13為1-14的子節(jié)點，3-6為2-7的子節(jié)點嘲碱，4-5為3-6的子節(jié)點金砍，折左邊的豎線代表的位置就是該節(jié)點的左值，右邊的豎線代表的位置就是該節(jié)點的右值麦锯。這樣也比較好理解為何增加一個節(jié)點恕稠，有些值需要加2。同樣比較容易理解為何按左值排序得到的數組就是最終樹的順序扶欣。同樣可以解釋鹅巍，為什么查詢左值大于某個節(jié)點左值同時右值小于該節(jié)點右值的節(jié)點就是該節(jié)點的所有子節(jié)點。
image.png
從圖中可以看到料祠，將節(jié)點按左值增加順序排序骆捧，大于增加位置上一個節(jié)點右值的所有左右值都需加2。同理可以比較好理解減去一個節(jié)點和移動一個子樹后左右值的變化髓绽。
以下是將符合預排序遍歷樹算法的二維數組轉化為樹形結構數組的方法敛苇。
function getNodeTree($arr,&$tree,$last_level=-1)
{
static $used_key = [];
foreach ($arr as $key => $value) {
if ( in_array($key,$used_key) ) {
continue;
}
$current_level = $value['level'];
$next_level = isset($arr[$key+1])?$arr[$key+1]['level']:-1;
if ( $current_level >= $last_level ) {
$tree[]=$value;
end($tree);
$index = key($tree);
$used_key[] = $key;
unset($arr[$key]);
$last_level = $value['level'];
if ( $next_level > $current_level ) {
getNodeTree($arr,$tree[$index]['children'],$last_level);
}
if ( $next_level == $current_level ) {
getNodeTree($arr,$tree,$last_level);
}
}else{
break;
}
}
}
其中第一個參數為需要處理的數組，數組要求必須按左值增加順序排序顺呕，$tree為最后所需結果枫攀。
