Деревья 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

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