Еще раз про деревья

[Kill_Santa]

Еще раз про деревья

Прежде чем отправлять меня на поиск - сами поищите, да?
google не в счет - давайте добавим золота именно на этот замечательный форум!

Суть вопроса в следующем. Есть масса алгоритмов для построения деревьев.
1. С хранением shift level в бд
2. С хранением shild id в бд
А тут попалось обратное - в бд есть только parent_id.
Что делать? Как искать? На ум просится что-нить рекурсивное, но получается какая-то фигня - или подвисает, или выдает только по первой строчке на каждом уровне.
Исходная матрица имеет неограниченно кол-во вложений и ключ sortorder для каждого подсписка.

 

[Popoff]

А тут попалось обратное - в бд есть только parent_id.

Метод называется "Списки смежностей". По-английски "Adjacency lists". Используй эти слова для поиска. Чтобы отличить дерево от графов, используй дополнительное слово "Деревья" или "Trees".

 

[Krishna]

С хранением shild id в бд

Это видимо child? И где он хранится? В строке парента? Значит может быть только 1 чайлд?

На самом деле основных вариантов 2 - nested sets и хранение parent_id

 

[Kill_Santa]

Krishna неа, наоборот. Хранится как раз parent_id

 

[Sluggard]

один вариант - рукурсивное выполнение запросов (ты его уже знаешь).
с идеей другого ознакомся здесь.
Кстати, нашел в поиске форума по слову "деревья" на 8-й позиции, если не считать твой вопрос, который ты поспешил задать.

 

[HraKK]

ID и PARENT_ID - это классический метод хранения дерева.
Строится элементарной рекурсивной функцией за 5 секунд написаной.

В detail все написано даже с примераи, правда стыдно даже смотреть, это как 1+1

 

[Kill_Santa]

Почему не работает следущее:

$sql="SELECT tree_id AS ARRAY_KEY, tree_pid AS PARENT_KEY level_name FROM tree ORDER BY level_name";forest($DB ->select($sql);function forest($forest){ foreach ($forest as $tree) { print'<ul>'; print '<li>'.$tree['level_name']; forest($tree['childNodes']); print '</li>'; print'</ul>'; }}

-~{}~ 01.03.08 00:54:

с выводом леса проблем нет. как сформировать лес из списка?

 

[AmdY]

не моё, НАШЁЛ на ЭТОМ форуме

function _transform2forest($rows, $idName, $pidName)
{
    $children = array(); // children of each ID
    $ids = array();
    foreach ($rows as $i=>$r) {
        $row =& $rows[$i];
        $id = $row[$idName];
        $pid = $row[$pidName];
        $children[$pid][$id] =& $row;
        if (!isset($children[$id])) $children[$id] = array();
        $row['childNodes'] =& $children[$id];
        $ids[$row[$idName]] = true;
    }
    // Root elements are elements with non-found PIDs.
    $forest = array();
    foreach ($rows as $i=>$r) {
        $row =& $rows[$i];
        if (!isset($ids[$row[$pidName]])) {
            $forest[$row[$idName]] =& $row;
        }
        unset($row[$idName]); unset($row[$pidName]);
    }
    return $forest;
}