Обработка дерева Nested Sets

BestGS · 17 Мар 2005

Обработка дерева Nested Sets

Вот такой вопрос к знатокам дерева Nested Sets:
Надо организовать вывод дерева как в Проводнике Windows. Т.е. в начале отображаются только нулевые уровни. При выборе одной из веток отображаются корневые уровни до выбранной ветки, в выбранной ветке отображается следующий уровень и ниже отображаются все оставшиеся нулевые ветки. При выборе во вложенной ветке (первый уровень) отображаются ветки со вторым уровнем.

Должно выглядеть вот так.

Код:

Ветка_1_уровень_0
Ветка_2_уровень_0
Ветка_3_уровень_0 (эту выбрали первый раз)
             Ветка_3.1_уровень_1
             Ветка_3.2_уровень_1 (эту выбрали второй раз)
                          Ветка_3.2.1_уровень_2
             Ветка_3.3_уровень_1
Ветка_4_уровень_0

Как организовать такой вывод на логическом уровне? Какие запросы к БД должны быть при этом?

GeT · 17 Мар 2005

Должен быть 1 запрос
[SQL]
SELECT * FROM tree ORDER BY left_key
[/SQL]
А остальное делает класс HTML_TreeMenu в Pear

crocodile2u · 17 Мар 2005

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

1) Можно воспользоваться другим пакетом из PEAR - DB_NestedSet
2) Писать свои запросы, но для того, чтобы подсказать оптимальное решение, нужно знать конкретную структуру твоих таблиц (скажем, в пакете DB_NestedSet структура содержит несколько вспомогательных полей, которые необязательны для построения дерева, но облегчают жизнь, и в частности, построение таких запросов)

BestGS · 17 Мар 2005

Спасибо за советы. Буду разбираться...

GeT · 17 Мар 2005

crocodile2u
Это какие поля? Родитель и ID корня?
Я не в курсе что там в Pear

Crys · 17 Мар 2005

Должен быть 1 запрос
SQL:

SELECT *
FROM tree
ORDER BY left_key

А если (исходя из первого поста) в Ветка_4_уровень_0 до фига "детей", тоже тягать их надо? Смысл?

GeT · 17 Мар 2005

Crys
Моя вина, неправильно понял вопрос. Думал ему нужно без рефреша страницы методами JS, а не PHP.

BestGS · 17 Мар 2005

Автор оригинала: GeT
Crys
Моя вина, неправильно понял вопрос. Думал ему нужно без рефреша страницы методами JS, а не PHP.

Да, мне надо было с рефрешем на PHP. А как самому такую функцию написать? Как она примерно будет выглядеть (в смысле какие циклы за что отвечают? Сколько циклов и запросов и т.д.)

Crys · 18 Мар 2005

PHP:

<?php
function sel($id)
{
   $s=mysql_fetch_assoc(mysql_query("SELECT * FROM tree WHERE id='".intval($id)."' LIMIT 1"));
   if (!$s)
   {
      return false;
   }
   $sel=mysql_query("SELECT * FROM tree WHERE left<=".$s["left"]." && right>=".$s["right"]." ORDER BY left");
   while ($row=mysql_fetch_assoc($sel))
   {
      $p[]=$row;
   }
   foreach ($p as $row)
   {
      $res[]=$row;
      $q=mysql_query("SELECT * FROM tree WHERE left>".$row["left"]." && right<".$row["right"]." && level=".($row["level"]+1)."");
      while ($r=mysql_fetch_assoc($q))
      {
         if (!in_array($r,$p))
         {
            $res[]=$r;
         }
      }
   }
return $res;
}

$r=sel(4);
foreach ($r as $v)
{
   echo str_repeat("&nbsp;",6*$v["level"]).$v["title"]."<br>";
}
?>

Чё-нить типа этого посмотри... Типа, вначале смотрим всех родителей (типа с корня до выделенного элемента), потом выбираем по порядку "детей" каждого...

crocodile2u · 18 Мар 2005

Имеем:
$id выбранного пункта.

Нужно: выбрать все ветки, что лежат выше по уровню, чем выбранный, и находятся в его ветке + детей выбранного пункта + все корневые узлы.

По идее, запрос будет что-то вроде такого:
[sql]
SELECT * FROM tree WHERE rootid=id OR (
rootid=$selected['rootid'] AND (level<=$selected['level'] OR
(level=$selected['level']+1 AND
left>$selected['left'] AND right<$selected['right']))
)
[/sql]

$selected = это выбранный узел.
ЗЫ: запрос написан тут же, "на коленке", сорри если ошибся. И еще - я предполагаю, что каждый узел содержит ID рутового узла, к чьей ветке он принадлежит (rootid).

Sherman · 18 Мар 2005

Тут обсуждали возможность сортировки. Вот предлагаю свой вариант(сыроват конечно, но можно оптимизировать).

Код:

catObj = new Category2();
	
$catObj->EnumChildrenAll(1,"cat_LEFT");

$startTime = microtime();
	
	$nodes = array();
	$prevID = 0;
	$numElements = count($catObj->nodeInfoCollection);
	for($i<0;$i<$numElements;$i++)
	{
		if ($catObj->nodeInfoCollection[$i]["level"] != $prevLevel)
		{
			if ($catObj->nodeInfoCollection[$i]["level"] == 1)
			{
				$catObj->nodeInfoCollection[$i]["parent_id"] = 1;
			}
			else 
			{
				$catObj->nodeInfoCollection[$i]["parent_id"] = $prevID;
			}
			$prevID = $catObj->nodeInfoCollection[$i]["id"];					
		}
		else 
		{
			
			$catObj->nodeInfoCollection[$i]["parent_id"] = $catObj->nodeInfoCollection[$i-1]["parent_id"];
		}
		
		$prevLevel = $catObj->nodeInfoCollection[$i]["level"];		
	}
	
	function cmp($a,$b)
	{
		return strcmp($a["data"]["desc"],$b["data"]["desc"]);
	}
	
	function getChild($parentid, $array)
	{
		$retArray = array();
		foreach($array as $arrayItem)
		{
			if ($arrayItem["parent_id"] == $parentid)
			{				
				$retArray[] = $arrayItem;
			}
		}
		usort($retArray, "cmp");	
		return $retArray;
	}
	
	function walk($root, $collection)
	{
		//global $nodes;
		$ret = getChild($root,$collection);
		if (!empty($ret))
		{
			for($i=0;$i<count($ret);$i++)
			{
				echo str_repeat("&nbsp;", 4*$ret[$i]["level"]);
				echo $ret[$i]["data"]["desc"]; 
				echo "  <b>" . $ret[$i]["id"] . "</b>";
				echo "  <b>" . $ret[$i]["parent_id"] . "</b>";
				echo "<BR>"; 
				walk($ret[$i]["id"],$collection);
			}
		}
	}
	
	walk(1,$catObj->nodeInfoCollection);
	
	echo number_format(microtime() - $startTime,4);

пояснения:

класс Category2 это класс реализующий nested sets алгоритм.
метод EnumChildrenAll(1,"cat_LEFT"); получает все дерево, отсортированное по левому ключу.
массив $catObj->nodeInfoCollection это список нодов.
один узел это ассоциативный массив с полями из бд:

Код:

var $nodeInfo = array(
		"id"=>0,
		"left"=>0,
		"right"=>0,
		"level"=>0,
		"data"=>array(
					"title"=>"",
					"creation_date"=>0,
					"modify_date"=>0,
					"desc"=>"",
					"photo"=>""));

сначала идет проставление всех родителей(кроме корня).

и затем рекурсивная функция сортировки по полю(в данном случае это название категории).

сама сортировка:

Код:

function cmp($a,$b)
	{
		return strcmp($a["data"]["desc"],$b["data"]["desc"]);
	}

usort($retArray, "cmp");

p.s. конечно лучше хранить уже осортированное дерево, т.е. вставлять узлы в «нужное место», но как это реализовать...

Полычь · 18 Мар 2005

Как я делаю - я храню два массива - один это непосредственно информация о дереве
$tree_info[tree_id] = array(pic=>.......);
и массив
$tree[$row[parent_id]][$row[tree_id]]=$row[tree_id];
с которым непосредственно и работаю - сортирую и тд.
А потом при выводе уже беру инфу (имя, картинку....) из $tree_info

Имхо - рекурсивными запросами к базе получать дерево - зло

Дешевле работать с массивчиком

Sherman · 19 Мар 2005

а при чем тут nested sets?

BestGS · 19 Мар 2005

Я попробовал функцию, которую предложил Crys. Скорее всего я буду ее использовать в другом проекте, там, где вложенность большая.

Еще я немного поработал с HTML_TreeMenu-1.2 предложенный GeT. В принципе при небольшом уровне вложенности (до 9 уровней) я решил использовать этот класс. Но возникла проблема. Я не могу, точнее не понимаю, как сделать функцию, которая формировала бы данные для вывода из базы. Как сделать вручную я понял, а как написать функцию, которая бы это делала автоматически че то не догнал

Вот так это выглядит, если делать ручками (пример из файла example.php)

PHP:

$node1   = new HTML_TreeNode(array('text' => "First level", 'link' => "test.php", 'icon' => $icon, 'expandedIcon' => $expandedIcon, 'expanded' => true), array('onclick' => "alert('foo'); return false", 'onexpand' => "alert('Expanded')"));
    $node1_1 = &$node1->addItem(new HTML_TreeNode(array('text' => "Second level", 'link' => "test.php", 'icon' => $icon, 'expandedIcon' => $expandedIcon)));
    $node1_1_1 = &$node1_1->addItem(new HTML_TreeNode(array('text' => "Third level", 'link' => "test.php", 'icon' => $icon, 'expandedIcon' => $expandedIcon)));
    $node1_1_1_1 = &$node1_1_1->addItem(new HTML_TreeNode(array('text' => "Fourth level", 'link' => "test.php", 'icon' => $icon, 'expandedIcon' => $expandedIcon)));
    $node1_1_1_1->addItem(new HTML_TreeNode(array('text' => "Fifth level", 'link' => "test.php", 'icon' => $icon, 'expandedIcon' => $expandedIcon, 'cssClass' => 'treeMenuBold')));

    $node1->addItem(new HTML_TreeNode(array('text' => "Second level, item 2", 'link' => "test.php", 'icon' => $icon, 'expandedIcon' => $expandedIcon)));
    $node1->addItem(new HTML_TreeNode(array('text' => "Second level, item 3", 'link' => "test.php", 'icon' => $icon, 'expandedIcon' => $expandedIcon)));

    $menu->addItem($node1);
    $menu->addItem($node1);

Макс · 20 Мар 2005

BestGS
ты parent_id в таблице дерева не хранишь ?
Это как раз тот случай, когда это поле было бы полезным

crocodile2u · 21 Мар 2005

Просто дополнение:

А вот используя PEAR - DB_NestedSet, всех этих трудностей легко избежать. Имеется класс DB_NestedSet_Output, который работает (в частности) с HTML_TreeMenu.

BestGS · 21 Мар 2005

Автор оригинала: Макс
BestGS
ты parent_id в таблице дерева не хранишь ?
Это как раз тот случай, когда это поле было бы полезным

Нет, не храню.

-~{}~ 21.03.05 20:04:

Надо попробывать PEAR - DB_NestedSet

Макс · 21 Мар 2005

вот пример кода. Как он работает - не помню.
У меня в таблице еще было поле sort (в котором была сортировка дерева). Просто убери его из кода (он в запросе и еще в одном месте) :

PHP:

$vars['cat_navigation'] = "Навигация";
require_once($classes_dir."TreeMenu.php");

$icon = 'folder.gif';
$expandedIcon = 'folder.gif';
$low_level_icon = 'folder.gif';


$menu  =  & new HTML_TreeMenu();

$node = & new HTML_TreeNode(array(
   'text' => "Начало",
   'link' => "index.php?",
   'icon' => $icon, 
   'expandedIcon' => $expandedIcon, 
));

// получаем дерево категорий из БД и по ним формируем меню
$res = $conn->Execute("SELECT * FROM $t_cats WHERE clevel > 0 AND is_hidden = 0 ORDER BY clevel, sort ASC");

if ($res && $res->RecordCount()) {
   // если записи найдены
   $nodes = array();
   $tmp = array();
   $i = 0;
   while (!$res->EOF) {
      if (
         !isset($tmp[$res->fields['clevel']]) ||
         !is_array($tmp[$res->fields['clevel']])) {

         $tmp[$res->fields['clevel']] = array();
      }
      $tmp[$res->fields['clevel']][$res->fields['cid']] = array($res->fields['cleft'], $res->fields['cright'], $res->fields['sort']);

      if ($res->fields['clevel'] == 1) {
         $is_last = ($res->fields['cright'] - $res->fields['cleft'] == 1)?1:0;
         $nodes[$res->fields['cid']] = &$node->addItem(new HTML_TreeNode(
            array(
               'text' => stripslashes($res->fields['title']),
               'link' => "index.php?cid=".$res->fields['cid'],
               'icon' => $is_last?$low_level_icon:$icon,
               'expandedIcon'=> $is_last?$low_level_icon:$expandedIcon)
         ));
        } else {
         // нужно найти элемент, являющийся родителем
         $need_key = 0;
         reset($tmp[$res->fields['clevel']-1]);
         while ((list($key, $val) = each($tmp[$res->fields['clevel']-1])) && !$need_key) {
            if ($val[0] < $res->fields['cleft'] && $val[1] > $res->fields['cright']) {
                    $need_key = $key;
                }
            }
            $is_last = ($res->fields['cright'] - $res->fields['cleft'] == 1)?1:0;
            $nodes[$res->fields['cid']] = &$nodes[$need_key]->addItem(new HTML_TreeNode(
               array(
                  'text' => stripslashes($res->fields['title']),
                  'link' => "index.php?cid=".$res->fields['cid'],
                  'icon' => $is_last?$low_level_icon:$icon,
                  'expandedIcon'=> $is_last?$low_level_icon:$expandedIcon)

            ));
        }
        $res->MoveNext();
    } //while (!$res->EOF)
} // if ($res && $res->RecordCount()) 
$menu->addItem($node);
$treeMenu = &new HTML_TreeMenu_DHTML($menu, array('images' => 'tree_images'));
// записываем HTML-код меню в $admin_menu
$vars['cat_navigation'] = $treeMenu->toHtml();

Crys · 24 Мар 2005

Скорее всего я буду ее использовать в другом проекте, там, где вложенность большая.

Там дерево криво отображалось в результате...
Тут вроде бы всё ок...

PHP:

<?php
function sel($id,$d=false)
{
   $query="SELECT * FROM data WHERE `id`=".intval($id)." LIMIT 1";
   $s=mysql_fetch_assoc(mysql_query($query));
   if ($d)
   {
      print "<hr><font size=\"3\"><b>MYSQL:</b> <i>".$query."</i><br>";
   }
   if (!$s)
   {
      return false;
   }
   $query="SELECT * FROM data WHERE `left`<=".$s["left"]." && `right`>=".$s["right"]."";
   $sel=mysql_query($query);
   if ($d)
   {
      print "<b>MYSQL:</b> <i>".$query."</i><br>";
   }
   while ($row=mysql_fetch_assoc($sel))
   {

      @$q.="(`left`>".$row["left"]." && `right`<".$row["right"]." && `level`=".($row["level"]+1).") OR ";
   }
   $q=substr($q,0,-4);

   $query="SELECT * FROM data WHERE (".$q.") ORDER BY left";

   $s=mysql_query($query);
   if ($d)
   {
      print "<b>MYSQL:</b> <i>".$query."</i></font><hr>";
   }
   while($row=mysql_fetch_assoc($s))
   {
      $r[]=$row;
   }
   return $r;
}

$r=sel(5,true);
foreach ($r as $v)
{
   echo str_repeat("&nbsp;",6*$v["level"]).$v["title"]."<br>";
}

BestGS · 12 Апр 2005

Вот такая загвоздка:
Мне надо при выводе дерева пропустить определенные уровни. В частности 1.

В данный момент функция такая:

PHP:

require_once("../tree_menu/TreeMenu.php"); 

$icon         = 'folder.gif';
$expandedIcon = 'folder-expanded.gif';

$menu  =  & new HTML_TreeMenu(); 
$node = & new HTML_TreeNode(array( 
   'text' => 'Лекции',
   'link' => '',//'?action=lessons', 
   'icon' => $icon, 
   'expandedIcon' => $expandedIcon,
   'expanded' => true,
));


//выбераем ключи
$res_tree = $db->Execute("SELECT * FROM lessons WHERE title = '$_SESSION[id_group]' AND level = '1'  "); 
while (!$res_tree->EOF) { 
$left_key['tree'] = $res_tree->fields['left_key'];
$right_key['tree'] = $res_tree->fields['right_key'];


$res = $db->Execute("SELECT * FROM lessons WHERE right_key > '$left_key[tree]' AND left_key < '$right_key[tree]' ORDER BY left_key");
//выводит лекции
if ($res && $res->RecordCount()) { 
   // если записи найдены 
   $nodes = array(); 
   $tmp = array(); 
   $i = 0; 
   while (!$res->EOF) { 
      if ( 
         !isset($tmp[$res->fields['level']]) || !is_array($tmp[$res->fields['level']])) { 
         $tmp[$res->fields['level']] = array(); 
      } 
      $tmp[$res->fields['level']][$res->fields['id']] = array($res->fields['left_key'], $res->fields['right_key'] ); 

      if ($res->fields['level'] == 0) {
         $is_last = ($res->fields['right_key'] - $res->fields['left_key'] == 1)?1:0; 
         $nodes[$res->fields['id']] = &$node->addItem(new HTML_TreeNode( 
            array( 
               'text' => stripslashes(substr($res->fields['title'],0,30))."&nbsp;",  
               'link' => '',//'?action='.$_REQUEST['action'].'&id='.$res->fields['id'].'&left_key='.$res->fields['left_key'].'&right_key='.$res->fields['right_key'].'&level='.$res->fields['level'], 
               'icon' => $icon, 
               'expandedIcon'=> $expandedIcon,
			   'expanded' => false) 
         )); 
		 

        } else { 
         // нужно найти элемент, являющийся родителем 
         
         $need_key = 0;
         reset($tmp[$res->fields['level']-1]);
          
         while ((list($key, $val) = each($tmp[$res->fields['level']-1])) && !$need_key) { 
            if ($val[0] < $res->fields['left_key'] && $val[1] > $res->fields['right_key']) { 
                    $need_key = $key; 
                } 
            }//while

            $is_last = ($res->fields['right_key'] - $res->fields['left_key'] == 1)?1:0; 
			if ($res->fields['level'] > 2):
            $link = '?action='.$_REQUEST['action'].'&id='.$res->fields['id'].'&left_key='.$res->fields['left_key'].'&right_key='.$res->fields['right_key'].'&level='.$res->fields['level'];
			else:
			$link = '';
			endif;//
            $nodes[$res->fields['id']] = &$nodes[$need_key]->addItem(new HTML_TreeNode( 
               array( 
                  'text' => stripslashes(substr($res->fields['title'],0,30))."&nbsp;",
                  'link' => $link,
                  'icon' => $icon, 
                  'expandedIcon'=> $expandedIcon,
                  'expanded' => false)
            ));
        
         }//else
        
	$res->MoveNext(); 
  } //while (!$res->EOF)
  
} // if ($res && $res->RecordCount()) 




$res_tree->MoveNext(); 
} //while (!$res_tree->EOF) 
	
$menu->addItem($node); 
$treeMenu = &new HTML_TreeMenu_DHTML($menu, array('images' => '../tree_menu/images', 'defaultClass' => 'treeMenuDefault'));
$treeMenu->printMenu();

Обработка дерева Nested Sets

BestGS

Guest

Новичок

http://vbolshov.org.ru

BestGS

Guest

Новичок

Двинутый новичок

Новичок

BestGS

Guest

Двинутый новичок

http://vbolshov.org.ru

Mephi

Полычь

Guest

Mephi

BestGS

Guest

Старожил PHPClub

http://vbolshov.org.ru

BestGS

Guest

Старожил PHPClub

Двинутый новичок

BestGS

Guest