вторник, 7 мая 2013 г.

Рекурсивный алгоритм обхода дерева (General tree) (в контексте разделов инфоблока Битрикс)

Во время моей учебы в университете СИАОД казался мне скучнейшим предметом. Мы лежали на партах и не знали, куда себя девать, считая секунды до конца. Спустя годы я понимаю, что должна быть благодарна нашему преподавателю, который не позволял нам пропускать свои заунылые лекции. Потому что, занимаясь оптимизацией web-проектов на битрикс, я сплошь и рядом вижу ситуации, когда незнание такого простого алгоритма, как обход естественного дерева, вынуждает разработчиков делать лишние запросы к базе данных.

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

В исходниках типового древовидного меню Битрикс мы можем видеть один из алгоритмов обхода дерева, но он мне, честно говоря, не очень нравится - он не достаточно нагляден и не очень гибок. Мои стажеры испытывают трудности, когда им нужно видоизменить этот алгоритм. Поэтому я хочу описать другой - самый простой, на мой взгляд.

Сначала я выбираю все активные разделы из инфоблока

    $map=array();
    if(isset($arParams["IBLOCK_MAP_ID"]))
    {   
        $arFilter = Array('IBLOCK_ID'=>$arParams["IBLOCK_MAP_ID"], 'GLOBAL_ACTIVE'=>'Y');
        $db_list = CIBlockSection::GetList(Array("left_margin"=>"asc"), $arFilter, true, array("UF_ID_IB"));
       
        while($ar_result = $db_list->GetNext())
        {
            $map[''.$ar_result['ID']]=$ar_result;
         }
   
    }

Многие думают, что функция CIBlockSection::GetTreeList или CIBlockSection::GetList с сортировкой "left_margin"=>"asc" сразу возвращает нам дерево. Но она возвращает не дерево, а один из вариантов его обхода. Хорошо, если этот обход совпадает с тем путем, по которому вам нужно обойти дерево, но часто нужно обойти его в другом порядке. В массиве же $map каждый потомок содержит ссылку на предка, но предок не содержит ссылок на потомков.

В массиве $map сейчас потомки идут сразу за своими предками - то есть прямой ссылки нет - она определяется порядком следования элементов в массиве. Да, можно обойти дерево как угодно и в этом его представлении - примеров в исходниках Битрикс - масса. Но это, как я уже говорила - громоздкие алгоритмы. Если нам нужно, к примеру, вывести ветку, начиная с определенного узла, нам придется перебирать весь массив в цикле, пока мы не дойдем до этого узла (а чаще делают дополнительный аякс запрос по мере необходимости - в лучшем случае, а в худшем - запросы в цикле фигачат). А я предпочитаю не делать даже аякс запросов, если можно их не делать. Поэтому я преобразую дерево к другому очень удобному для работы виду - гроздьями.

$map_sec=array();
    foreach($map as $key=>$val){
   
        if($val['IBLOCK_SECTION_ID']>0){
            $parent_id=$map[$val['IBLOCK_SECTION_ID']]['ID'];
            $map_sec[''.$parent_id]['CODE']=$map[$parent_id]['CODE'];
            $map_sec[''.$parent_id]['NAME']=$map[$parent_id]['NAME'];
            $map_sec[''.$parent_id]['UF_ID_IB']=$map[$parent_id]['UF_ID_IB'];
            $map_sec[''.$parent_id]['CHILDS'][]=array("ID"=>$val['ID'],"CODE"=>$val['CODE'],"NAME"=>$val['NAME'],"UF_ID_IB"=>$val['UF_ID_IB']);
           
        }

    }
   
 $arResult['MAP']=$map_sec;

В массиве  $arResult['MAP'] у нас дерево в виде гроздей - каждый предок содержит ссылки на своих потомков. Вот к нему мы уже можем применять классические алгоритмы работы с деревьями в их неизменном виде.

Функция рекурсивного обхода такого дерева будет выглядеть следующим образом:

function outTree($category_arr,$parent_id) {
       
        if (isset($category_arr[$parent_id])) {
           
                foreach ($category_arr[$parent_id]['CHILDS'] as $value) { //Обходим
                    echo "<div style=\"margin-left:" . ($value['DEPTH_LEVEL']  * 25) . "px;\">" . $value["NAME"] . "</div>";
                  
                    if (count($category_arr[$value["ID"]]['CHILDS'])>0){
                        //Рекурсивно вызываем эту же функцию, но с новым $parent_id
                        outTree($category_arr,$value["ID"]);
                    }
                    else{
                         //Выводим листик
                     }
                 
                }
           
           }
       
    }


Теперь для того, чтобы вывести ветку дерева, начиная с любого узла $id_uzla достаточно написать:
outTree($arResult['MAP'],$id_uzla);
то есть мы можем выводить ветки дерева в любом порядке, в каком они нужны нам в шаблоне, например, чтобы вывести иерархию каталога на вложенных друг в друга закладочках, не обращаясь при этом к базе данных каждый раз при переключении закладки.

В практическом плане. Данный метод (с несколькими модификациями, естественно) я использовала для представления иерархии каталога товаров в виде вот таких вложенных закладочек. И вложенность там ничем не ограничена (только фантазией дизайнера).



Обращение к базе - только единожды (одна функция CIBlockSection::GetList) - и все построено на результатах ее работы. Работающий пример тоже покажу - ближе к запуску проекта, для которого писала это.

3 комментария:

Анонимный комментирует...

Здравствуйте, предлагаю способ проще, без рекурсии, с использованием ссылок, вот описание.

Анонимный комментирует...

Ссори, не вставил сам код:
$arResult['ROOT'] = array();
$sectionLinc[0] = &$arResult['ROOT'];
while($arSection = $rsSections->GetNext()) {
$sectionLinc[intval($arSection['IBLOCK_SECTION_ID'])]['CHILD'][$arSection['ID']] = $arSection;
$sectionLinc[$arSection['ID']] = &$sectionLinc[intval($arSection['IBLOCK_SECTION_ID'])]['CHILD'][$ar_result['ID']];
}
В результате в $arResult['ROOT'] имеем дерево.

Юлия комментирует...

Интересный способ. Попробуем.