Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > PHP: Общие вопросы > Вывод дерева из БД


Автор: mark2011 28.7.2011, 16:52
Избитая, конечно, тема, ну да ладно....

В прикреплённом файлике структура таблицы. Задача проста - вывести её на экран. 

Делаю так:

Код

global $db;    

//получить корень
//первый вызов функции: $this->PrintTree(0);
$db->query('SELECT cat_id, cat_name FROM photo_browser_categories WHERE parent_id = ' . $parent_id);
$r = $db->parse_query('array');
$var.= $r['cat_name']."<br>";


Так, занесли в переменную корень дерева... Хорошо, идём дальше...

Код

//выбрать тот элемент, у которого parent_id = cat_id текущего элемента
$db->query('SELECT cat_id, cat_name FROM photo_browser_categories WHERE parent_id = "' . $r['cat_id'] .'"');
$rr = $db->parse_query('array');
$var .= $rr['cat_name']."<Br>";


Логично, правда? Посмотрите на рисунок: у корня cat_id=29, он же parent_id у второго элемента. Казалось бы, повторяй эту конструкцию в цикле, ан нет...

У элемента "1.1.1"  cat_id=31, но не существует элемента, у которого parent_id=31.  Значит автоматически указанное выше условие рекурсии недействительно.

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

Знаю, что существуют обходы деревьев (префиксный, постфиксный и инфиксный) но, насколько я знаю, это для деревьев Nested Sets, там где используется left_id, right_id... А у меня очень простая структура. 

В общем то надо условие повтора (ради чего рекурсия) и условие выхода из рекурсии...

Всем откликнувшимся огромное спасибо smile

Автор: Sanchezzz 31.7.2011, 03:47
что то типо того должно быть я так понимаю ?

Код

function Tree($id=0, $level=0, $i=0) {
$s = "SELECT cat_id, cat_name FROM photo_browser_categories WHERE parent_id = '{$id}";
$res = mysql_query($s);
if( mysql_num_rows($res) > 0){
        $level++;    
        while($r = mysql_fetch_assoc($res){
            $i++;
            print_R($r);
            Tree($r['cat_id']);
            
        }
    }else{
        $level--;
    }
}

tree(0);


parent_id должен быть в таблицы по дефолту стоять 0 по умолчанию если он не является потомком.

Автор: mark2011 2.8.2011, 09:33
Sanchezzz, 
Такой вариант не работает однозначно, я проверил.

Но вот о чём я задумался.... в принципе дерево можно всё за один проход передать в массив и дальше уже работать с этим массивом. С другой стороны, дерево может быть очень большое и массив может получиться огромный. Вот.... возникает вопрос, где будет больше накладных расходов - при прохождении массивом, или прямым рекурсивным выводом из базы?

Автор: baldina 2.8.2011, 09:51
Цитата(mark2011 @  2.8.2011,  09:33 Найти цитируемый пост)
в принципе дерево можно всё за один проход передать в массив и дальше уже работать с этим массивом

нет никакой разницы откуда получать данные, из базы или массива
Цитата(mark2011 @  28.7.2011,  16:52 Найти цитируемый пост)
У элемента "1.1.1"  cat_id=31, но не существует элемента, у которого parent_id=31

на приведенном рисунке существует... но допустим что нет. это означает, что этот элемент - лист. конец рекурсии.
вот если бы наоборот, parent_id != 0, но элемента с таким cat_id нет. это означает, что целостность данных нарушена. возможно, такая ситуация вполне штатная, просто при обновлениях базы забыли про это поле. тогда просто следует принять решение (с точки зрения задачи), что означают такие записи. очевидных варианта два: либо считать данный элемент корнем еще одного дерева (parent_id=0) либо просто не рассматривать его.
вообще, если мы идем от корня (начиная с parent_id = 0), узлы с несуществующими родителями нам просто не вернутся из базы.
Цитата(mark2011 @  2.8.2011,  09:33 Найти цитируемый пост)
Такой вариант не работает однозначно, я проверил.

что мешает этому варианту работать?

Добавлено @ 10:05
http://codepad.org/dPYKaHtG

Автор: baldina 2.8.2011, 10:15
Цитата(mark2011 @  2.8.2011,  09:33 Найти цитируемый пост)
где будет больше накладных расходов - при прохождении массивом, или прямым рекурсивным выводом из базы? 

нельзя сказать однозначно. зависит от размера данных, нагрузки на базу, нагрузки на сервер php.
по возможности всю работу целесообразно переложить на СУБД, выполняя иерархический запрос. Напрямую иерархические запросы могут не поддерживаться, это потребует программирования на стороне СУБД

Автор: нуп 2.8.2011, 10:40
Да тупо кэшировать категории и всё  smile 

Автор: CruorVult 2.8.2011, 10:52
Цитата(mark2011 @  2.8.2011,  09:33 Найти цитируемый пост)
С другой стороны, дерево может быть очень большое и массив может получиться огромный. Вот.... возникает вопрос, где будет больше накладных расходов - при прохождении массивом, или прямым рекурсивным выводом из базы?


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

Автор: mark2011 2.8.2011, 11:41
CruorVult, 
В некоторых случаях - да. Но у меня была ситуация, когда потребовалось тянуть всё дерево, аякс работал, но был неприемлем для заказчика.

baldina, 
Ну по вашей логике: существует элемент с cat_id = 32, но не существует элемента parent_id = 32. Этот элемент лист - конец рекурсии. А элемент с cat_id = 33? Получается что он вообще не войдёт в выборку?

Автор: CruorVult 2.8.2011, 12:20
Цитата(mark2011 @  2.8.2011,  11:41 Найти цитируемый пост)
А элемент с cat_id = 33? Получается что он вообще не войдёт в выборку?


с какого перепуга? Судя с дампа на рисунке cat_id = 33 он не имеет ни малейшего отношения к 32.

Да и вообще, вопрос по-моему уже ришен, просто вы никак не хотите начать думать smile 

Автор: gcc 2.8.2011, 12:24
если таблица с одним деревом не 100гиг, то можно использовать http://www.google.com.ua/#hl=ru&source=hp&q=Nested+Set+&oq=Nested+Set+&aq=f&aqi=g10&aql=&gs_sm=e&gs_upl=629l629l0l1056l1l1l0l0l0l0l274l274l2-1l1l0&fp=258deabd11a5a999&biw=1280&bih=799 и еще примеры есть с innodb

Автор: baldina 2.8.2011, 12:45
Цитата(mark2011 @  2.8.2011,  11:41 Найти цитируемый пост)
существует элемент с cat_id = 32, но не существует элемента parent_id = 32. Этот элемент лист - конец рекурсии. 

да
Цитата(mark2011 @  2.8.2011,  11:41 Найти цитируемый пост)
А элемент с cat_id = 33? Получается что он вообще не войдёт в выборку?  

это от вас зависит, как вы хотите. или не войдет, или будет на верхнем уровне (как будто его parent_id=0)

вообще-то я все это уже говорил. и пример вам сделал, работающий с вашими данными

Добавлено через 57 секунд
http://codepad.org/dPYKaHtG смотрели?

Добавлено через 6 минут и 33 секунды
и вот это http://codepad.org/HwoD1QWJ

Автор: mark2011 19.10.2011, 13:22
Ну что ж, заново открываю мной же созданную тему...

Итак, структура базы данных та же. 
Вариант, предложенный Sanchezzz, после допиливания работает, но выдаёт следующее:

Цитата

Array
(
    [photo_category_id] => 1
    [photo_category_name] => 31
    [level] => 1
)
Array
(
    [photo_category_id] => 2
    [photo_category_name] => 32
    [level] => 1
)
Array
(
    [photo_category_id] => 3
    [photo_category_name] => 33
    [level] => 1
)
Array
(
    [photo_category_id] => 4
    [photo_category_name] => 34
    [level] => 1
)
Array
(
    [photo_category_id] => 11
    [photo_category_name] => 41
    [level] => 1
)
Array
(
    [photo_category_id] => 12
    [photo_category_name] => 42
    [level] => 1
)
Array
(
    [photo_category_id] => 13
    [photo_category_name] => 43
    [level] => 1
)
Array
(
    [photo_category_id] => 14
    [photo_category_name] => 44
    [level] => 1
)
Array
(
    [photo_category_id] => 5
    [photo_category_name] => 35
    [level] => 1
)
Array
(
    [photo_category_id] => 6
    [photo_category_name] => 36
    [level] => 1
)
Array
(
    [photo_category_id] => 7
    [photo_category_name] => 37
    [level] => 1
)
Array
(
    [photo_category_id] => 8
    [photo_category_name] => 38
    [level] => 1
)
Array
(
    [photo_category_id] => 9
    [photo_category_name] => 39
    [level] => 1
)
Array
(
    [photo_category_id] => 10
    [photo_category_name] => 40
    [level] => 1
)
Array
(
    [photo_category_id] => 15
    [photo_category_name] => 45
    [level] => 1
)


Т.е. как бы нормально, НО:

Почему-то уровень всё время первый, т.е. невозможно однозначно отследить где начинается потомок. Вот мой допиленный код:
Код

function Tree($id=0, $level=0, $i=0) {
$s = "SELECT photo_category_id, photo_category_name FROM photo_browser_categories WHERE photo_category_parent_id = '" . $id . "'";
$res = mysql_query($s);

if( mysql_num_rows($res) > 0){
        $level++;    
        while($r = mysql_fetch_assoc($res)){
            $i++;
            $r['level'] = $level;
            print_R($r);
            Tree($r['photo_category_id']);
            
        }
    }else{
        $level--;
    }
}

Автор: MoLeX 19.10.2011, 19:35
http://habrahabr.ru/tag/nested%20set/

http://www.google.ru/#sclient=psy-ab&hl=ru&newwindow=1&source=hp&q=nested%20sets&pbx=1&oq=neste&aq=1&aqi=g4&aql=1&gs_sm=sc&gs_upl=1070l6269l0l10145l8l7l1l0l0l0l1166l2887l2-3.3.7-1l8l0&bav=on.2,or.r_gc.r_pw.,cf.osb&fp=722f8ceee399dfd&biw=1920&bih=890&pf=p&pdl=300

Автор: mark2011 20.10.2011, 08:14
Я не могу использовать вложенные множества. Во-первых это потребует изменения структуры таблицы, во вторых у меня не такое разветвлённое дерево. Изменять структуру таблицы не нужно.

Автор: MoLeX 20.10.2011, 08:32
mark2011, плодите тогда запросы к СУБД. Это ваше право, наше дело предложить

Автор: mark2011 20.10.2011, 08:46
Я уже мало что понимаю.... накопал следующую функцию:

Код

function get_tree($tree, $pid)
{
    $html = '';
 
    foreach ($tree as $row)
    {
        if ($row['photo_category_parent_id'] == $pid)
        {
            $html .= '<li>' . "\n";
            $html .= '    ' . $row['photo_category_name'] . "\n";
            $html .= '    ' . get_tree($tree, $row['photo_category_id']);
            $html .= '</li>' . "\n";
        }
    }
 
    return $html ? '<ul>' . $html . '</ul>' . "\n" : '';
}


Использую её следующим образом:

Код

$s = "SELECT * FROM photo_browser_categories WHERE photo_category_parent_id = 0";
$db->query($s);
while ($data = $db->parse_query('array'))
{
    $r_tree[] = $data;
}

function get_tree($tree, $pid)
{
    $html = '';
 
    foreach ($tree as $row)
    {
        if ($row['photo_category_parent_id'] == $pid)
        {
            $html .= '<li>' . "\n";
            $html .= '    ' . $row['photo_category_name'] . "\n";
            $html .= '    ' . get_tree($tree, $row['photo_category_id']);
            $html .= '</li>' . "\n";
        }
    }
 
    return $html ? '<ul>' . $html . '</ul>' . "\n" : '';
}

echo get_tree($r_tree, 0);


В ответ получаю:
Цитата

    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    45

Т.е. в выводе пропущены элементы. Кто-нибудь подскажет вообще в чём причина?

Автор: MoLeX 20.10.2011, 13:05

M
MoLeX		Модератор: Давайте вернёмся к теме обсуждения.

Автор: patap 20.10.2011, 13:15
вот посмотри http://kod34fr33.wordpress.com/2008/05/06/adjacency-list-tree-on-mysql/

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)