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


Автор: gribikc 23.5.2008, 18:43
Код

id_ca    int(11)
parent_id_ca    int(11)
name    varchar(255)
text    text


как при такой структуре записи получь для произвольного id всех предков(ну тоеть id предков)
 smile 

Автор: skyboy 23.5.2008, 23:27
рекурсивно.

Автор: gribikc 25.5.2008, 13:22
Код


function get_in(&$mass,$idin){
    global $get_in;
    $get_in.=",".$mass[$idin];
    if(empty($mass[$idin])) return null;
    get_in(&$mass,$mass[$idin]);
    return $get_in;
}


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

собственно я думал может ктонить чтото интересненькое предложит...

вот весь скрипт 

Код

<?
include("config.php");
if($in==''){$in=0;}
$mysql_query=mysql_query("select * from catalogue where parent_id_ca in (".$in.") OR parent_id_ca=0");
$i=0;
$temp="";
while($a=mysql_fetch_array($mysql_query)){
    $arr[$a['parent_id_ca']][]=array('id' => $a['id_ca'], 'parent_id' => $a['parent_id_ca'], 'name' => $a['name']);
    $arr_in[$a['id_ca']]=$a['parent_id_ca'];
}
print_r($arr_in);
?>
<br><br><br>
<?
$get_in="0";
function get_in(&$mass,$idin){
    global $get_in;
    $get_in.=",".$mass[$idin];
    if(empty($mass[$idin])) return null;
    get_in(&$mass,$mass[$idin]);
    return $get_in;
}
?>
<br><br><br>
<?
$out="";
function get_tree(&$mass,$parent_id=0,$prefix="") {
    global $out;
    for($c=0;$c<sizeof($mass[$parent_id]);$c++){
        $out.=$prefix."<a href=\"tree.php?in=".$v."\">".$mass[$parent_id][$c]['name']." ".get_in($arr_in,$mass[$parent_id][$c]['id'])."</a><br>\n";
        get_tree($mass,$mass[$parent_id][$c]['id'], $prefix."&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;");
    }
    return $out;
}
echo get_tree($arr);
?>
<br>
<a href="tree.php">с нова</a>


он ещё не до конца верно работает

Автор: Feldmarschall 25.5.2008, 13:36
для получения предков рекурсия не нужна

Автор: skyboy 25.5.2008, 14:02
Цитата(Feldmarschall @  25.5.2008,  12:36 Найти цитируемый пост)
для получения предков

для получения непосредственных предков. так?
а мои телепатические способности утверждают, что топикстартеру нужно то, чем хвалится nested sets - быстро получить всех предков узла до N-го колена. впрочем, телепатические способности могут и ошибаться... smile

Автор: Feldmarschall 25.5.2008, 14:04
а какие бывают ещё, кроме непосредственных?
Вообще, насколько я понимаю, рекурсия бывает нужна только при движении вниз.
при движении вверх, или по горизонтали, она ведь не нужна. или я ошибаюсь?

Автор: gribikc 25.5.2008, 14:17
вообщем не буду мочить вот рабочий скрипт
http://gribikc.ru/tree/tree.php

вот его код
Код

<?
include("config.php");
if($in==''){$in=0;}
$mysql_query=mysql_query("select * from catalogue where parent_id_ca in (".$in.") OR parent_id_ca=0");
$i=0;
$temp="";
while($a=mysql_fetch_array($mysql_query)){
    $arr[$a['parent_id_ca']][]=array('id' => $a['id_ca'], 'parent_id' => $a['parent_id_ca'], 'name' => $a['name']);
    $arr_in[$a['id_ca']]=$a['parent_id_ca'];
}
//print_r($arr_in);
?>
<br><br><br>
<?
$get_in="";
function get_in(&$mass,$idin){
    global $get_in;
    $get_in.=",".$mass[$idin];
    if(empty($mass[$idin])) return $idin;
    get_in(&$mass,$mass[$idin]);
    return $get_in;
}
?>
<br><br><br>
<?
$out="";
function get_tree(&$mass,$arr_in,$parent_id=0,$prefix="") {
    global $out;
    global $get_in;
    for($c=0;$c<sizeof($mass[$parent_id]);$c++){
        $get_in=$mass[$parent_id][$c]['id'];
        $out.=$prefix."<a href=\"tree.php?in=".get_in($arr_in,$mass[$parent_id][$c]['id'])."\">".$mass[$parent_id][$c]['name']."</a><br>\n";
        get_tree($mass,$arr_in,$mass[$parent_id][$c]['id'], $prefix."&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;");
    }
    return $out;
}
echo get_tree($arr,$arr_in);
?>
<br><br><br>
<a href="tree.php">с нова</a>



вопрос можно ли проще сделать чем через вложенную рекурсию


skyboy, необходимо получать всех предков до начальной записи


Feldmarschall, а как тогда???

Автор: Feldmarschall 25.5.2008, 14:24
так же, как и любые другие операции в программировании - созданием слгоритма!
ты можешь написать код, который получит одного предка? непосредственного предка?
а для полученного предка получить его предка?
а посмотреть на полученный код, и подумать, как его можно оптимизировать?

Автор: gribikc 25.5.2008, 14:26
Feldmarschall, к сажелению всё что смог оптимизировать это я вылож пока новых мыслей нет
в любом случае если не рекурсия то цикл будет

Автор: Feldmarschall 25.5.2008, 14:41
не понял смысла этого "в любом случае". а ты как хотел? чтобы вообще без единого оператора, все само построилось?
ну раз ты понимаешь, как сделать циклом - почему не сделаешь?

Автор: skyboy 25.5.2008, 15:00
Цитата(Feldmarschall @  25.5.2008,  13:04 Найти цитируемый пост)
а какие бывают ещё, кроме непосредственных?
Вообще, насколько я понимаю, рекурсия бывает нуж

предок предка.
Цитата(Feldmarschall @  25.5.2008,  13:04 Найти цитируемый пост)
при движении вверх, или по горизонтали, она ведь не нужна. 

почему же?
имеется идентификатор поста. необходимо определить полную цепь: тема, подфорумы(неограниченное количество), форум. сделать это можно и рекурсией, и циклом. так же как и при движении "вниз".
я прав: тебя интересовала именно адекватность использования рекурсии при движении "вверх"? и как, достаточно адекватный пример? smile

Автор: Mushu 25.5.2008, 15:06
Цитата(Feldmarschall @ 25.5.2008,  14:04)
а какие бывают ещё, кроме непосредственных?
Вообще, насколько я понимаю, рекурсия бывает нужна только при движении вниз.
при движении вверх, или по горизонтали, она ведь не нужна. или я ошибаюсь?

есть рекурсии как и по низ ходящим это от родителя до чилдрена,
так и восходящим тобишь от детей к родителю

Добавлено @ 15:07
Цитата(gribikc @ 25.5.2008,  14:17)
вообщем не буду мочить вот рабочий скрипт
http://gribikc.ru/tree/tree.php

вот его код
Код

<?
include("config.php");
if($in==''){$in=0;}
$mysql_query=mysql_query("select * from catalogue where parent_id_ca in (".$in.") OR parent_id_ca=0");
$i=0;
$temp="";
while($a=mysql_fetch_array($mysql_query)){
    $arr[$a['parent_id_ca']][]=array('id' => $a['id_ca'], 'parent_id' => $a['parent_id_ca'], 'name' => $a['name']);
    $arr_in[$a['id_ca']]=$a['parent_id_ca'];
}
//print_r($arr_in);
?>
<br><br><br>
<?
$get_in="";
function get_in(&$mass,$idin){
    global $get_in;
    $get_in.=",".$mass[$idin];
    if(empty($mass[$idin])) return $idin;
    get_in(&$mass,$mass[$idin]);
    return $get_in;
}
?>
<br><br><br>
<?
$out="";
function get_tree(&$mass,$arr_in,$parent_id=0,$prefix="") {
    global $out;
    global $get_in;
    for($c=0;$c<sizeof($mass[$parent_id]);$c++){
        $get_in=$mass[$parent_id][$c]['id'];
        $out.=$prefix."<a href=\"tree.php?in=".get_in($arr_in,$mass[$parent_id][$c]['id'])."\">".$mass[$parent_id][$c]['name']."</a><br>\n";
        get_tree($mass,$arr_in,$mass[$parent_id][$c]['id'], $prefix."&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;");
    }
    return $out;
}
echo get_tree($arr,$arr_in);
?>
<br><br><br>
<a href="tree.php">с нова</a>



вопрос можно ли проще сделать чем через вложенную рекурсию


skyboy, необходимо получать всех предков до начальной записи


Feldmarschall, а как тогда???

Через рекурсию самый быстрый способ.

 ! 
skyboy		наезды и оскорбления оставляем при себе

Автор: Feldmarschall 25.5.2008, 15:12
skyboy, нет, я не понял, почему при движении вверх (а вот интересно, почему я говорю "вверх", имея в виду корень дерева?) адекватной будет рекурсия, а не цикл. Цикл проще, с точки зрения алгоритма, реализации и понимания.

Я считаю, что рекурсия не должна быть синонимом слова "дерево", и применяться для любой задачи, с ним связанной, на автомате.

Добавлено через 40 секунд
Батюшки =) Специалист подтянулся =))))

Автор: skyboy 25.5.2008, 15:26
Цитата(Feldmarschall @  25.5.2008,  14:12 Найти цитируемый пост)
а вот интересно, почему я говорю "вверх", имея в виду корень дерева?

небось, на бумаге рисовал от корня и сверху-вниз. так?  smile 
Цитата(Feldmarschall @  25.5.2008,  14:12 Найти цитируемый пост)
Я считаю, что рекурсия не должна быть синонимом слова "дерево", и применяться для любой задачи, с ним связанной, на автомате.

согласен.
построение древовидной структуры и быстрее, и нагляднее - итеративно. за N действий.
но обход - почему бы и нет?
вообще говоря, вопрос простоты понимания - довольно субъективная вещь. мне чаще проще написать рекурсивную функцию, тогда как в циклах не всегда обойтись без дополнительных ветвлений и всяких булевских флагов. В отдельной функции оно, по крайней мере, смотрися "прозрачнее".
впрочем, это слишком близко к вопросу религии smile

Автор: gribikc 25.5.2008, 15:27
Feldmarschall,  в данном случаее рекурсией сдесь наглядней чем циклом

но меня интересует как ещё это можно сделать???

Автор: skyboy 25.5.2008, 15:31
Цитата(gribikc @  25.5.2008,  14:27 Найти цитируемый пост)
но меня интересует как ещё это можно сделать??? 

"пройтись" по (не)ограниченной вложенности структуре возможно двумя способами:
- итеративно
- рекурсивно
варианты приводимы друг к другу, т.е. нет ситуации, когда одно использовать возможно, а второе - нет.
другой вопрос, что при одном алгоритме короче/читаемее рекурсивный вариант, а в другом случае - итерация будет верхом изящества. смотри сам, по ситуации.

Добавлено через 2 минуты и 13 секунд
Цитата(gribikc @  25.5.2008,  12:22 Найти цитируемый пост)
но при этом мне необходимо в рекурсивной функции каждый раз вызывать другую рекурсивную функцию

дело в том, что как раз вызов из функции самой себя - это и есть рекурсия. не будет "самовызова" - это уже не рекурсия будет.
и вот ещё: нет, само по себе это не тупо.

Автор: Feldmarschall 25.5.2008, 15:34
Цитата(skyboy @  25.5.2008,  15:26 Найти цитируемый пост)
в циклах не всегда обойтись без дополнительных ветвлений и всяких булевских флагов. 

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

здесь задача, скорее, на понимание своих действий.
если человек представляет себе дерево, то цикл - наиболее естественный вариант решения. что может быть проще, чем запросить в цикле у БД несколько записей?
если дерево для человека - тёмный лес, и есть только шаблон "дерево=рекурсия", то да - проще рекурсией.

здесь задача, скорее, на умение алгоритмизировать свои действия.
что такое цикл? когда мы его применяем? когда видим несколько одинаковых действий.

ведь прекрасно будет работать программа, к примеру, такая:
Код

print $array[1];
print $array[2];
print $array[3];
print $array[4];
print $array[5];

но программист видит повторяемость операторов, и делает на этом месте цикл.
то же самое и с получением предков.

Автор: gribikc 25.5.2008, 15:39
skyboy, нет ты не понел мы в одной рекурсивной функции вызываем другую рекурсивную функцию вот о чём была речь.- итеративно-что ты под этим понимаешь??


Feldmarschall, я не щитаю множественные запросы к базе данных удачным решением(об этом даже хостер просит чтоб так не делали)

Автор: Feldmarschall 25.5.2008, 15:58
Хостер твой дурак. Дело не в количестве запросов, а в качестве. Выборка по первичному ключу ВООБЩЕ никак не напрягает базу. Хоть сто записей выбирай, а не 2-3, как у тебя.

Но речь вообще не о БД. БД я привел для примера. 
Если у тебя все лежит в массиве, то для него задачу тоже можно решить. Для этого надо думать над структурой массива. 

Автор: gribikc 25.5.2008, 15:59
Feldmarschall, ну как разтаки над структурой массива я всё продумал их там из одного запроса составляется 2 для дерева и для предков соответственно

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