Построение многоуровеневого меню на php

[SergoZD]

Задача такова. Для простоты, есть некий массив, например такой:

PHP код:

$m["o"]="";
$m["p"]="";
$m["q"]="o";
$m["r"]="o";
$m["s"]="q";
$m["t"]="";
$m["g"]="t";
$m["y"]="o";
$m["f"]="t";
$m["z"]="j";
$m["h"]="j";
$m["j"]="t";
$m["e"]="z"; 


В нем в качестве ключа стоит текущий id пункта, а значение - id родительского пункта меню. Пустая строка означает что это корневой элемент.
Нужно на php сделать вывод этого массива в древовидном виде, для данного примера в таком:

o
_q
__s
_r
_y
p
t
_g
_f
_j
__z
___e
__h

Пока смог дойти лишь до варианта, что они выводятся в нужном порядке, но не могу придумать, как бы сделать разделение уровней.
Да и сам код по моему не слишком удачен (увеличение массива до двухмерного сдается мне не очень удачное решение)

Вот что пока получается:

PHP код:

<?php

function menu1($id)
{
    global $m;

    foreach($m[0] as $key=>$value)
    {
        if ($value==$id and $m[1][$key]==0)
        {
            echo "$key=$value<br>";
            $m[1][$key]=1;
            menu1 ($key);
        }
    }
}

$m[0]["o"]="";
$m[0]["p"]="";
$m[0]["q"]="o";
$m[0]["r"]="o";
$m[0]["s"]="q";
$m[0]["t"]="";
$m[0]["g"]="t";
$m[0]["y"]="o";
$m[0]["f"]="t";
$m[0]["z"]="j";
$m[0]["h"]="j";
$m[0]["j"]="t";
$m[0]["e"]="z";

menu1("");

?>

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


Зы. недавно где-то видел тему с похожим названием, но чё-т не смог найти...

[Trotil]

Использовать счетчик уровня. Вот как я себе это представляю:

PHP код:

<?php

function menu1($id)
{
    global $m;
    static $i=0;

    foreach($m[0] as $key=>$value)
    {
        if ($value==$id and $m[1][$key]==0)
        {
            for ($j=$i; $j>0; $j--) echo "_";
            echo "$key<br>";
            $m[1][$key]=1;
            $i++;
            menu1 ($key);
            $i--;
        }
    }
}
//$i=0;
$m[0]["o"]="";
$m[0]["p"]="";
$m[0]["q"]="o";
$m[0]["r"]="o";
$m[0]["s"]="q";
$m[0]["t"]="";
$m[0]["g"]="t";
$m[0]["y"]="o";
$m[0]["f"]="t";
$m[0]["z"]="j";
$m[0]["h"]="j";
$m[0]["j"]="t";
$m[0]["e"]="z";

menu1("");

?>

[Naked]

Если небольшой массив, то, наверное можно делать так:
1. Выбрать корневой элемент (один)
2. Найти все элементы, значение которых равно ключу корневого элемента
3. Для каждого из тех элементов найти также их "детей"

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

[SergoZD]

The_naked
Речь про какое-то универсальное решение
По началу я решил просто сделать ограничение в три подуровня и вложенные циклы создал, но есть желание без ограничений таких решить проблему.

Trotil
В принципе работает, да. Я как-то до такого не додумал.
Но есть ли другие методы решения подобного? Или такой постановке задачи другого решения нету?
Тогда может как-то по другому можно сделать задание менюшек?
Сейчас пришла в голову мысль о многуровневом массиве, каждый уровень которого отвечал бы за соответствующий уровень на сайте. Вроде бы тут всё просто, но тогда другая проблема. Как его хранить в mysql?

(Суть идеи такова, в базе должна быть таблица, в которой хранится менюшка...)

[Hubbitus]

SergoZD:
Или такой постановке задачи другого решения нету?
Тогда может как-то по другому можно сделать задание менюшек?
Сейчас пришла в голову мысль о многуровневом массиве, каждый уровень которого отвечал бы за соответствующий уровень на сайте. Вроде бы тут всё просто, но тогда другая проблема. Как его хранить в mysql?

Проблема хранения деревьев (любых, B-деревьев, сбалансированных и т.д.) разрабатывается давно и используется часто. Существует множество способов для этого, кстати и здесь про них и MySQL уже была достаточно большая тема, но вот какраз недвано наткнулся на статью, где очень подробно на примерах расписано использование для этого клдасса, который там же и прилагается.

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

[EvroStandart]

SergoZD:
Как его хранить в mysql?

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

[SergoZD]

EvroStandart
Можешь показать пример кода?
Не совсем представляю себе, как это реализовать без двухмерного массива...
Точнее пока совсем не представляю

[Al-x]

Держи функцию, которую я когда-то писал для этих целей:
$link - соед. с базой
$sqlTblCat - таблица, хранящая меню
my_mysql_query() - я ей ошибки обрабатывал
$href передаётся для формирования ссылки в меню
Хотя это всё не важно, думаю можно и так разобраться

PHP код:

function printTree($pid,$href) {
    global $link;
    global $sqlTblCat;

    $ret='';
    $query="SELECT * FROM $sqlTblCat WHERE pid='$pid'  ORDER BY descName";
    $result = my_mysql_query($query, $link) or die(mysql_die(__FILE__.': '.__LINE__.' in '.__FUNCTION__,false,true,true));

    if (mysql_num_rows($result) > 0)
    {
        $ret.=("<UL>\n");
        while ( $row = mysql_fetch_array($result) ) {
            $ret.=("<LI>\n");
            $ret.="<A HREF='$href"."?id=".$row['id']."'>".htmlspecialchars(stripslashes($row["descName"]), ENT_QUOTES)."</A><br>\n";
            $ret.="</li>\n";
            $ret.=printTree($row['id'],$href);
        }
        $ret.=("</UL>\n");
    }
    return $ret;
} 


Вызов:

PHP код:

printTree(0,$HTTP_SERVER_VARS['PHP_SELF']) 


База:

CREATE TABLE `cathegories` (
  `id` int(11) NOT NULL auto_increment,
  `pid` int(11) NOT NULL default '0',
  `descName` varchar(255) NOT NULL default ''
)

[SergoZD]

Занятно.
Попарился сегодня ещё над развитием своего варианта, и таки получилось то что и хотел.

PHP код:

function menu($id) 
{ 
    global $m; 
    $j=$m;
    static $i=0; 

    foreach($j as $key=>$value) 
    { 
        if ($value==$id) 
        { 
            echo "$i уровень - $key<br>"; 
            $i++; 
            menu ($key); 
            $i--; 
        } 
    } 
} 


Но вот такое дело, объяснения которому я так и не нашел. Функция практически не изменилась, просто все $m[0] заменил просто на $m. Т.е. избавился от двумерности массива.
Но если влоб сделать такую замену - скрипт перестает работать как надо.
При обходе foreach($m as $key=>$value) при определенном условии вызывается эта же функция (рекурсия вроде называется), в которой так же идет обход foreach($m as $key=>$value).
Так вот, выход из рекурсивно вызванной функции происходит при невыполнении условия if и завершении foreach. И после этого выхода из функции счетчик foreach не восстанавливает своего значения, а указывает туда, где остановился в выполненной только что функции, т.е. в конец. А это не есть гуд.
Я решил просто добавлением после global $m определения $j=$m и в foreach использую уже $j. Тогда при возвращении из функции указатель указывает на тот элемет массива, на котором остановился перед её вызовом.
Не понятным мне остается, почему такая разница получается при использовании $m[0] и $m.

[Sheryld]

Сообщение от Hubbitus

Проблема хранения деревьев (любых, B-деревьев, сбалансированных и т.д.) разрабатывается давно и используется часто. Существует множество способов для этого, кстати и здесь про них и MySQL уже была достаточно большая тема, но вот какраз недвано наткнулся на статью, где очень подробно на примерах расписано использование для этого клдасса, который там же и прилагается.

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

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

Для себя выдернул алгоритм построения меню(смотри фун-ию Ajar). Но алгоритм не оптимальный. Все остальное вроде уже где-то встречалось...

p.s. К тому же, если у вас есть в наличии нормальная СУБД(pgsql/ms sql/etc), то необходимо, просто обязательно использовать хранимки, триггеры и транзакции — решите кучу проблем, а также добавите скорости.

[apoc]

Тоже самое, но немного другими словами:

Деревья Nested Sets

Управление деревьями Nested Set

Дерево каталогов NESTED SETS (вложенные множества) часть вторая