Деревья Nested Sets

Для начала нужно обязательно сходить и прочесть статью //myphp.net.ru/lessons/index.php?18 Это введение в деревья использующие алгоритм Nested Sets и необходимая и пользовая теория. Вкратце можно сказать что деревья используются в таблицах хранящих категории товаров неограниченной вложенности или например структуру всего сайта или структуру директорий на вашем винте и т.д. Всю эту прелесть можно хранить в одной таблице и ею довольно легко манипулировать.

Для создания и работы с деревьями Nested Sets написан класс CDBTree, качать его нугено тута. Вообщем все нужное вы найдете на //www.e-taller.net/dbtree/ Не буду вдаваться в теорию, далее будет представлен код и основные методы работы с этим типом дерева.

Итак... будем считать что теория прочитана и сейчас главное разобраться с SQL запросами. Для удобства заводим две функции: для коннекта к базе и для вывода дерева. И потом засылаем запросы к базе. Кусок IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag дает нам 1 если элемент дерева имеет потомков, иначе 0.

Для работы всех примеров используется уже готовое дерево Nested Sets - таблица molotok её дамп тута, настройки базы в фукции connect_db(). Если вы создадите свою табицу или она у вас уже есть, то её название в переменной $tbl. Исходники всех примеров тута, вы можете их скачать и погонять на своем тазике :))

Первый пример (ns_test1.php)
Основные методы работы с деревом.

 <?php




function connect_db()


{ 

    mysql_connect("localhost",
"root", "")
or die("Can`t connect");


    mysql_select_db("bidz")
or die("Can`t select");


} 



function print_rez($query,
$text="")


{ 

    $result =
mysql_query($query);


    if (mysql_num_rows($result)
== 0) die("Empty
result or Bad sql: ".$query);


    echo (!empty($text)
? "<P><B>".$text."</B><BR>n"
: "<P>n").$query."<P>n";


    while ($row =
mysql_fetch_assoc($result))


        echo str_repeat("&nbsp;
&nbsp; &nbsp;",    $row['cat_level']).


            "
[".$row['cat_id']."]
". ((isset($row['nflag'])
&& $row['nflag'])
? "<b>".$row['cat_name']."</b>"
: $row['cat_name']).


            "
<font color='#0033FF'>[".$row['cat_left']."]</font>
". 

            "
<font color='#009900'>[".$row['cat_right']."]</font>
(".$row['cat_level'].")
<br>"; 

} 



$tbl = "molotok";


connect_db(); 





// Выводим все дерево 

// 

$query = "SELECT
*, IF (cat_left+1 < cat_right OR cat_level = 1, 1, 0) AS nflag FROM ".$tbl."
ORDER BY cat_left"; 

print_rez($query,
"Выводим все дерево");






// Выводим всех родителей 

// 

$id = 65;
// id нужного элемента 

$query = "SELECT
A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM ".$tbl."
A, ".$tbl."
B WHERE B.cat_id='".$id."'
AND B.cat_left BETWEEN A.cat_left AND A.cat_right ORDER BY A.cat_left";


print_rez($query,
"Выводим всех родителей для элемента: ".$id);






// Выводим нужную ветку 

// 

$id = 14;
// id нужного элемента 

$query = "SELECT
A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM ".$tbl."
A, ".$tbl."
B WHERE B.cat_id='".$id."'
AND A.cat_left >= B.cat_left AND A.cat_right <= B.cat_right ORDER BY
A.cat_left"; 

print_rez($query,
"Выводим ветку для элемента: ".
$id); 





//Выводим "приоткрытое" дерево 

// 

$ncat = 44;
// id нужного элемента 

$query = "SELECT
A.* FROM ".$tbl."
A, ".$tbl."
B WHERE B.cat_id = '".$ncat."'
AND B.cat_left BETWEEN A.cat_left AND A.cat_right ORDER BY A.cat_left";


$result = mysql_query($query);


if (($alen = mysql_num_rows($result))
== 0) die("Err!");


$i = 0;


$sql = "";




while ($row = mysql_fetch_assoc($result))


{ 

    if ((++$i ==
$alen) &&
($row['cat_left']+1
== $row['cat_right']))
break; 

    $sql .=
" OR (cat_level=".($row['cat_level']+1)."
AND cat_left>".$row['cat_left']."
AND cat_right<".$row['cat_right'].
")"; 

} 



$sql = "SELECT
*, IF (cat_left+1 < cat_right OR cat_level = 1, 1, 0) AS nflag FROM ".$tbl."
WHERE cat_level=1 ".$sql."
ORDER BY cat_left"; 

print_rez($sql,
"Выводим "приоткрытое" дерево для элемента:
". $ncat);




?>

Запускаем все это дело и видим нужный нам результат...

Выводим все дерево
SELECT *, IF (cat_left+1 < cat_right OR cat_level = 1, 1, 0) AS nflag FROM molotok ORDER BY cat_left

[1] [1] [132] (0)
[2] Книги, Видео, Музыка, CD [2] [63] (1)
   [3] Журналы и газеты [3] [4] (2)
   [4] Видео [5] [28] (2)
      [21] Видеодиски [6] [13] (3)
         [33] Комедии, Мелодрамы [7] [8] (4)
         [34] Семейное и детское кино [9] [10] (4)
         [35] Фантастика, Мистика, Ужасы [11] [12] (4)
      [22] DVD-диски [14] [15] (3)
      [23] Видеокассеты с неигровыми записями [16] [17] (3)
      [24] Видеокассеты с зарубежными фильмами [18] [25] (3)
         [36] Комедии, Мелодрамы [19] [20] (4)
         [37] Семейное и детское кино [21] [22] (4)
         [38] Фантастика, Мистика, Ужасы [23] [24] (4)
      [25] Видеокассеты с фильмами без перевода [26] [27] (3)
   [5] Книги [29] [58] (2)
      [26] Художественная литература [30] [31] (3)
      [27] Детская литература [32] [33] (3)
      [28] Дом, Семья, Досуг [34] [35] (3)
      [29] Естественные науки [36] [37] (3)
      [30] Искусство, искусствоведение [38] [39] (3)
      [31] Компьютеры, Программирование, Интернет [40] [55] (3)
         [60] PHP [41] [48] (4)
            [64] For Lammotz [42] [43] (5)
            [65] For Coders [44] [45] (5)
            [66] RTFM etc. [46] [47] (5)
         [61] C/C++/C# [49] [50] (4)
         [62] Delphi [51] [52] (4)
         [63] Other shit [53] [54] (4)
      [32] На иностранных языках [56] [57] (3)
   [6] Мультимедийные издания [59] [60] (2)
   [7] Музыка [61] [62] (2)
[8] Коллекционирование [64] [129] (1)
   [9] Вещи знаменитостей, Автографы [65] [66] (2)
   [10] Военные вещи [67] [68] (2)
   [11] Игры: MtG, Pokemon и другие [69] [70] (2)
   [12] Киндер Сюрприз [71] [72] (2)
   [13] Коллекционное оружие [73] [74] (2)
   [14] Банкноты [75] [100] (2)
      [39] Австралия и Океания [76] [77] (3)
      [40] Азия [78] [79] (3)
      [41] Америка [80] [81] (3)
      [42] Россия и СССР [82] [93] (3)
         [54] Госвыпуски до 1917 [83] [84] (4)
         [55] Госвыпуски после 1917 [85] [86] (4)
         [56] Лотереи, акции, облигации [87] [88] (4)
         [57] Частные выпуски до 1922 [89] [90] (4)
         [58] Частные выпуски после [91] [92] (4)
      [43] Африка [94] [95] (3)
      [44] Европа [96] [97] (3)
      [45] Страны СНГ [98] [99] (3)
   [15] Модели [101] [102] (2)
   [16] Открытки [103] [104] (2)
   [17] Спортивные карточки [105] [106] (2)
   [18] Жетоны, Медали, Значки [107] [124] (2)
      [46] Жетоны [108] [109] (3)
      [47] Памятные медали и знаки, Значки [110] [111] (3)
      [48] Воинские награды и знаки отличия [112] [121] (3)
         [50] Россия до 1917 г. [113] [114] (4)
         [51] Россия и СНГ после 1991 г. [115] [116] (4)
         [52] СССР с 1917 до 1991 г. [117] [118] (4)
         [53] Другие страны [119] [120] (4)
      [49] Памятные медали и знаки, Значки [122] [123] (3)
   [19] Фотографии, Письма [125] [126] (2)
   [20] Марки [127] [128] (2)
[59] Услуги [130] [131] (1)

Выводим всех родителей для элемента: 65
SELECT A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM molotok A, molotok B WHERE B.cat_id='65' AND B.cat_left BETWEEN A.cat_left AND A.cat_right ORDER BY A.cat_left

[1] [1] [132] (0)
[2] Книги, Видео, Музыка, CD [2] [63] (1)
   [5] Книги [29] [58] (2)
      [31] Компьютеры, Программирование, Интернет [40] [55] (3)
         [60] PHP [41] [48] (4)
            [65] For Coders [44] [45] (5)

Выводим ветку для элемента: 14
SELECT A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM molotok A, molotok B WHERE B.cat_id='14' AND A.cat_left >= B.cat_left AND A.cat_right <= B.cat_right ORDER BY A.cat_left

   [14] Банкноты [75] [100] (2)
      [39] Австралия и Океания [76] [77] (3)
      [40] Азия [78] [79] (3)
      [41] Америка [80] [81] (3)
      [42] Россия и СССР [82] [93] (3)
         [54] Госвыпуски до 1917 [83] [84] (4)
         [55] Госвыпуски после 1917 [85] [86] (4)
         [56] Лотереи, акции, облигации [87] [88] (4)
         [57] Частные выпуски до 1922 [89] [90] (4)
         [58] Частные выпуски после [91] [92] (4)
      [43] Африка [94] [95] (3)
      [44] Европа [96] [97] (3)
      [45] Страны СНГ [98] [99] (3)

Выводим "приоткрытое" дерево для элемента: 44
SELECT *, IF (cat_left+1 < cat_right OR cat_level = 1, 1, 0) AS nflag FROM molotok WHERE cat_level=1 OR (cat_level=1 AND cat_left>1 AND cat_right<132) OR (cat_level=2 AND cat_left>64 AND cat_right<129) OR (cat_level=3 AND cat_left>75 AND cat_right<100) ORDER BY cat_left

[2] Книги, Видео, Музыка, CD [2] [63] (1)
[8] Коллекционирование [64] [129] (1)
   [9] Вещи знаменитостей, Автографы [65] [66] (2)
   [10] Военные вещи [67] [68] (2)
   [11] Игры: MtG, Pokemon и другие [69] [70] (2)
   [12] Киндер Сюрприз [71] [72] (2)
   [13] Коллекционное оружие [73] [74] (2)
   [14] Банкноты [75] [100] (2)
      [39] Австралия и Океания [76] [77] (3)
      [40] Азия [78] [79] (3)
      [41] Америка [80] [81] (3)
      [42] Россия и СССР [82] [93] (3)
      [43] Африка [94] [95] (3)
      [44] Европа [96] [97] (3)
      [45] Страны СНГ [98] [99] (3)
   [15] Модели [101] [102] (2)
   [16] Открытки [103] [104] (2)
   [17] Спортивные карточки [105] [106] (2)
   [18] Жетоны, Медали, Значки [107] [124] (2)
   [19] Фотографии, Письма [125] [126] (2)
   [20] Марки [127] [128] (2)
[59] Услуги [130] [131] (1)

Заметьте, что ветки: 2, 42, 18 и 59 не открыты. То есть данный результат получился бы и при выводе для элемента 14. А если бы мы выводили "приоткрытое" дерево для элемента 42, тогда бы добавились его потомки четвертого уровня. Этот фикус можно заюзать для построения навигации по сайту, вообщем поэкспериментируйте. Л

Второй пример (ns_test2.php)
Представим что нам нужно вывести дерево одной таблицей как тут: //molotok.ru/catalog/index.php?MIval=/catalog/default.app Рисуем шаблон для Integrated Template(класс HTML_Template_IT) из PEAR.

 <!DOCTYPE HTML
PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 

<html> 

<head> 

<title>molotok sample</title> 

<meta http2-equiv="Content-Type" content="text/html; charset=windows-1251">


</head> 



<body> 

<table width="100%" border="0" cellspacing="0" cellpadding="0"> 

<!-- BEGIN t_data --> 

  <tr> 

    <!-- BEGIN t_inner --> 

        <!-- BEGIN _twd --><td
width="5%" align="center">*</td><!-- END _twd --> 

        <!-- BEGIN _d --> 

            <td<!--
BEGIN _ttd --> colspan="{_tcols}"<!-- END _ttd -->><!-- BEGIN
_zag --><b>{header}</b><br><!-- END _zag --> 

            <!--
BEGIN hdr0 --><a href="{lnk0}">enter category</a><!-- END
hdr0 --> 

            <!--
BEGIN _data --><!-- BEGIN dlm --> -:- <!-- END dlm --><a
href="{lnk}">{tdata}</a><!-- END _data --> 

            </td>


        <!-- END _d --> 

    <!-- END t_inner --> 

  </tr> 

<!-- BEGIN t_spacer --> 

  <tr> 

    <td height="5"<!-- BEGIN _ts --> colspan="{max_lvl}"<!--
END _ts -->></td> 

  </tr> 

<!-- END t_spacer --> 

<!-- END t_data --> 

</table> 

</body> 

</html>

И рисуем код, переменная $max_lvl = 4; //MAX(cat_level) - 1 тоесть она меньше максимального уровня дерева на единицу. Мoжно выставить сразу или дописать вначале запрос и определить.

 <?php




function connect_db()


{ 

    mysql_connect("localhost",
"root", "")
or die("Can`t connect");


    mysql_select_db("bidz")
or die("Can`t select");


} 





require_once("template_it.class.php");


connect_db(); 

$mod = new IntegratedTemplate();


$mod->loadTemplatefile("tree_tmpl.html");




$tbl = "molotok";


$sql = "SELECT  IF
( A.cat_level = 0, B.cat_left, A.cat_left ) AS cat, A.cat_level, A.cat_name
AS name, B.cat_id, B.cat_name FROM ".$tbl."
A INNER  JOIN ".$tbl."
B ON ( ( B.cat_level = A.cat_level + 1 ) AND ( B.cat_left = B.cat_right -
1 ) AND B.cat_left BETWEEN A.cat_left AND A.cat_right )  WHERE (
A.cat_left != A.cat_right - 1) ORDER BY cat, B.cat_id";


print $sql."<p>";


$res = mysql_query($sql);


if (mysql_num_rows($res)
== 0) die("Err
(2): cat tree!"); 



//ВНИМАНИЕ $max_lvl требует настройки

$max_lvl = 4;
//MAX(cat_level) - 1 

$dlm = false;


$i = 0;


$cat = -1;




while ($row = mysql_fetch_assoc($res))


{ 

    if ($cat !=
$row['cat'])


    { 

        if (++$i
> 1)
$mod->parse("t_data");


        //t_inner


        $mod->setCurrentBlock("t_inner");




        if ($row['cat_level']
== 0) 

        { 

            if
($max_lvl > 1)
$mod->setVariable(array("_tcols"
=> $max_lvl,
"max_lvl" =>
$max_lvl)); 

                else
$mod->touchBlock("t_spacer");


            $mod->setVariable(array("header"
=> $row['cat_name'],
"lnk0" => "?cat=".$row['cat_id']));


            continue;


        } 



        $cols
= ($max_lvl +
1) - $row['cat_level'];


        $dlm
= true;


        $cat
= $row['cat'];




        if ($row['cat_level']
> 1) 

            for
($i = 1;
$i <= $row['cat_level']-1;
$i++) 

            {




                <

font color="#0000BB">$mod->touchBlock("_twd");




                <

font color="#0000BB">$mod->parse("t_inner");


            }




        if ($cols
> 1)
$mod->setVariable("_tcols",
$cols); 

        $mod->setVariable("header",
$row['name']);


        if ($max_lvl
> 1)
$mod->setVariable("max_lvl",
$max_lvl); else
$mod->touchBlock("t_spacer");


    } 



    if (true)
//$lvl < $row['cat_level'] 

    { 

        //_data


        $mod->setCurrentBlock("_data");


        if ($dlm)
$dlm = !$dlm;    else
$mod->touchBlock("dlm");


        $mod->setVariable(array("tdata"
=> $row['cat_name'],
"lnk" => "?cat=".$row['cat_id']));


        $mod->parse("_data");


    } 

} 



$mod->show();




?>

Не думаю что SQL запрос идеален, но в принципе он нам подходит. Запускаем всю эту колбасень...

SELECT IF ( A.cat_level = 0, B.cat_left, A.cat_left ) AS cat, A.cat_level, A.cat_name AS name, B.cat_id, B.cat_name FROM molotok A INNER JOIN molotok B ON ( ( B.cat_level = A.cat_level + 1 ) AND ( B.cat_left = B.cat_right - 1 ) AND B.cat_left BETWEEN A.cat_left AND A.cat_right ) WHERE ( A.cat_left != A.cat_right - 1) ORDER BY cat, B.cat_id

Книги, Видео, Музыка, CD
Журналы и газеты -:- Мультимедийные издания -:- Музыка

* Видео
DVD-диски -:- Видеокассеты с неигровыми записями -:- Видеокассеты с фильмами без перевода

* * Видеодиски
Комедии, Мелодрамы -:- Семейное и детское кино -:- Фантастика, Мистика, Ужасы

* * Видеокассеты с зарубежными фильмами
Комедии, Мелодрамы -:- Семейное и детское кино -:- Фантастика, Мистика, Ужасы

* Книги
Художественная литература -:- Детская литература -:- Дом, Семья, Досуг -:- Естественные науки -:- Искусство, искусствоведение -:- На иностранных языках

* * Компьютеры, Программирование, Интернет
C/C++/C# -:- Delphi -:- Other shit

* * * PHP
For Lammotz -:- For Coders -:- RTFM etc.

Коллекционирование
Вещи знаменитостей, Автографы -:- Военные вещи -:- Игры: MtG, Pokemon и другие -:- Киндер Сюрприз -:- Коллекционное оружие -:- Модели -:- Открытки -:- Спортивные карточки -:- Фотографии, Письма -:- Марки

* Банкноты
Австралия и Океания -:- Азия -:- Америка -:- Африка -:- Европа -:- Страны СНГ

* * Россия и СССР
Госвыпуски до 1917 -:- Госвыпуски после 1917 -:- Лотереи, акции, облигации -:- Частные выпуски до 1922 -:- Частные выпуски после

* Жетоны, Медали, Значки
Жетоны -:- Памятные медали и знаки, Значки -:- Памятные медали и знаки, Значки

* * Воинские награды и знаки отличия
Россия до 1917 г. -:- Россия и СНГ после 1991 г. -:- СССР с 1917 до 1991 г. -:- Другие страны

Услуги
enter category

На этом пока все, не судите строго и разрешите откланяться :) Если возникнут вопросы, мыльте, я всем отвечу.