Построение дерева комментариев на PHP

PHP

Категории и подкатегории. Каталоги и подкаталоги. Построение древа, а именно древовидных комментариев, является общей не малой проблемой если не использовать готовые решения.

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

Представьте себе, простой набор данных, массив:

Array

(

    [0] => Array

        (

            [name] => Node 0

            [parent] => null

        )



    [1] => Array

        (

            [name] => Node 1

            [parent] => 4

        )



    [2] => Array

        (

            [name] => Node 2

            [parent] => 8

        )

    ...

Общий подход заключается в использовании рекурсивной функции, которая находит все корневые узлы, их составные и вложенные узлы их составных узлов, и так далее.

function mapTree($dataset, $parent=null) {

    $tree = array();

    foreach ($dataset as $id=>$node) {

        if ($node['parent'] !== $parent) continue;

        $node['children'] = mapTree($dataset, $id);

        $tree[$id] = $node;

    }



    return $tree;



}

Проблема этого метода в том, что, с точки зрения скорости: нужно искать все дочерние элементы для каждого узла древа. Таким образом, построение дерева из 1000 узлов в 100 раз более сложнее, чем построение дерева из 100 узлов, потому что вам придется искать в 10 раз больше узлов, в 10 раз чаще.

Более эффективным способом построения дерева является использование уникальных идентификаторов для элементов. Это позволяет отобразить все дерево за один проход, без рекурсии.

function mapTree($dataset) {

    $tree = array();

    foreach ($dataset as $id=>&$node) {

        if ($node['parent'] === null) { // root node

            $tree[$id] = &$node;

        } else { // sub node

            if (!isset($dataset[$node['parent']]['children'])) $dataset[$node['parent']]['childs'] = array();

            $dataset[$node['parent']]['children'][$id] = &$node;

        }

    }



    return $tree;

}

Скачать примеры построения дерева комментариев (в архиве два варианта построения, быстрый и медленный).

25.01.2013 11:35:04