Меню
Что нового?

Рекурсия. Непонятки с алгоритмом

Денч

Новичок
Рекурсия. Непонятки с алгоритмом

Заранее извиняюсь, если не в ту тему.
Есть таблица БД:
! id ! id_parent !
--------------------
! 1 ! 0 !
! 2 ! 1 !
! 3 ! 1 !
! 4 ! 0 !
! 5 ! 1 !
! 6 ! 1 !
! 7 ! 1 !
! 8 ! 2 !
! 9 ! 2 !
! 10! 2 !
--------------------

смысл такой: В поле id_parent хранится id родителя. Вложенность неограниченная. На устройство таблиц не обращайте внимания, структура зависитне от меня.
Нужно отыскать все дочерние элементы, начиная от первой заданной при вызове функции.
Вот функция:
PHP: 
function Get_tree($id)
{
$out="";
	$query_parent="SELECT * FROM tree WHERE id_parent='".$id."'";
	
	$res_parent=mysql_query($query_parent);
	$num_parent=mysql_num_rows($res_parent);
	if($num_parent==0)
		{$out.= $id;}
	else 
	{
		while($data=mysql_fetch_array($res_parent))
		{
			$out.= $data['id'].",";
			echo $data['id'].",";
			get_tree($data['id']);
		}
	}
	return "'(".$out.")'";
}
строка
PHP: 
echo $data['id'].",";
пишет то, что нужно. А вот эта строка
PHP: 
$out.= $data['id'].",";
отдает только первые дочерние элементы, не учитывая вложенность выше второго уровня, хотя вторая строка не сильно, на мой взгляд, отличается от первой.
Что нужно поменять в коде, чтобы функция заработала?
Уж извините, не очень силен в особенностях рекурсивных функций :(
 

SiMM

Новичок
[telepat mode]
PHP: 
$out .= $data['id'].','.get_tree($data['id']);
в теле цикла.
[/telepat mode]
 
fixxxer

fixxxer

К.О.
Партнер клуба
кстати, удобнее в массив складывать.
тогда не надо думать, где нужна запятая, а где нет.
 

Денч

Новичок
SiMM
Такое я уже ставил, возвращает с повторениями.
Кстати, так и не понял, почему... Вроде должно было работать как надо

Забыл одно уточнение: функция должна вернуть строку вида '(1,2,5,3)' для использования в запросах к бд.
Дошел до такого:
PHP: 
            ob_start();
            echo $data['id'].","; 
            get_tree($data['id']); 
            $out.=ob_get_contents();
            ob_end_clean();
Не помогло, тот же результат, что и
PHP: 
echo $data['id'].",";
-~{}~ 19.05.05 23:41:

Поставил вот это
PHP: 
$out.="<b>".$data['id']."</b>";
$out.=get_tree($data['id']);
Жирным шрифтом вывел то, что нужно. Но стоило убрать
PHP: 
$out.=get_tree($data['id']);
и тут же функция стала возвращать только первый уровень... Либо я туп, либо просто что-то упустил...

-~{}~ 20.05.05 00:25:

SiMM
Прошу прощения, твой вариант более жизнеспособен.
PHP: 
function Get_tree($id)
{
	$query_parent="SELECT * FROM tree WHERE id_parent='".$id."'";
	
	$res_parent=mysql_query($query_parent);
	$num_parent=mysql_num_rows($res_parent);
	if($num_parent==0)
		return $id;
	else 
	{
		while($data=mysql_fetch_array($res_parent))
			$out.=$data['id'].",".get_tree($data['id']);
	}
	return $out;
}
Но вот куда девать, return $id; ума не приложу... Он ведь тоже нужен, если для заданного id нет детей...
 
rotoZOOM

rotoZOOM

ACM maniac
так как функция у тебя призвана возвращать строку, то и возвращай строку. Немного подкорректируем.
PHP: 
....
if($num_parent==0) return "";
else{
    while($data=mysql_fetch_array($res_parent)){
            if ($out!=="")$out.=",";
            $out.=$data['id'];
            if (($str=get_tree($data['id']))!=="") $out.=",".$str;
    }
}
return "(".$out.")"; // ну и скобочки добавим для красоты
 
itprog

itprog

Cruftsman
Код: 
function Get_tree($id,&$out=false)
{
    $query_parent="SELECT * FROM tree WHERE id_parent='".$id."'";
    
    $res_parent=mysql_query($query_parent);
    $num_parent=mysql_num_rows($res_parent);
    if($num_parent==0)
        {$out.= $id;}
    else
    {
        while($data=mysql_fetch_array($res_parent))
        {
            $out.= $data['id'].",";
            echo $data['id'].",";
            get_tree($data['id'],&$out);
        }
    }
    return "'(".$out.")'";
}
?>
 
rotoZOOM

rotoZOOM

ACM maniac
itprog что у тебя выдаст программа на таком дереве ?
PHP: 
+Node1
|     |
|     +Node2
|
+Node3
 

impossible

Новичок
PHP: 
function f_tree($id) {
	$sql="SELECT * FROM page WHERE ppid=".$id." ORDER BY pid";
	$res=mysql_query($sql);
	if (mysql_num_rows($res)>0) {
		$space.='=';
		while ($_map=mysql_fetch_array($res)) {
			echo $space.$_map['pid'].'<br>';
			f_tree($_map['pid']);
		}
		$space=substr($space,0,strlen($space)-1);
	}
	else {
		return 0;
	}
}

$sql="SELECT * FROM page WHERE ppid=0 ORDER BY pid";
$res=mysql_query($sql);
if (mysql_num_rows($res)>0) {
	while ($_map=mysql_fetch_array($res)) {
		echo $space.$_map['pid'].'<br>';
		f_tree($_map['pid']);
	}
}
строит карту сайта...не много подчистил для читабельности
первый запрос выбирает главные (без подчинения ppid=0)
 

tashkentchi

Новичок
Вариант:
PHP: 
function Get_tree($list) {
   global $link;
   $sql = "SELECT DISTINCT id
       FROM tree
       WHERE id_parent IN (".$list.")";
   $result=mysql_query($sql, $link);
   $list2="";
   while ($data = mysql_fetch_array($result)) {
      if ($list2) $list2=$list2.",".$data[0];
      else $list2=$data[0];
   }
   if ($list2) { return $list.",".Get_tree($list2); }
   return $list;
}
 

Денч

Новичок
tashkentchi
С меня пиво;) То, что надо
rotoZOOM
impossible

И вам огромное спасибо
 
BeGe

BeGe

Вождь Апачей, блин (c)
PHP: 
function Get_tree(&$list, $id=0,$lvl=0) {
   $sql = "SELECT DISTINCT id FROM tree WHERE id_parent = ".$id;
   $result=mysql_query($sql);
   while ($data = mysql_fetch_array($result)) {
        $list[] = array("id"=>$data["id"],"pid"=>$data["id_parent"],"lvl"=>$lvl);
        Get_tree($list,$data["id"],$lvl+1) 
   }
}

$tree = array();
Get_tree($tree);
Отказываемся от глобальных переменных :)
Для такой функции надо построение дерва - где для топовых елементов парент id = 0.
 
diamond_krnl

diamond_krnl

pure-php
при такой структуре "плоское" дерево надо брать целиком одним запросом, и без рекусий тогда можно обойтись.
 

Денч

Новичок
С вашими примерами уже лучше разбираюсь в рекурсиях. Всем большое спасибо.

ЗЫ
Если кто новый заглянет, скинь свой примерчик рекурсии(необязательно по теме), думаю - это многим не повредит...
 
diamond_krnl

diamond_krnl

pure-php
кусок из рабочего проекта, без рекусии, но перед этим дерево
берётся циликом - одним запросом.
PHP: 
function document_childs($parent) 
{
  $ret = array($parent=>$parent);
  $flag = true;
  $documents = &$GLOBALS['kernel']['documents'];
  while($flag)
  {
    $flag = false;
    foreach($documents as $i)
    {
      if(in_array($i['parent'], $ret) && !isset($ret[ $i['id'] ]))
      {
        $ret[ $i['id'] ] = $i['id'];
        $flag = true;
      }
    }
  }
  unset($ret[$parent]);
  return $ret;
}
 

Светлана PHP

Guest
Следует не забывать о ресурсах и вспоминать о хороших алгоритмах:
http://detail.phpclub.ru/article/db_tree
 
Войдите или зарегистрируйтесь для ответа.
Сверху