Метод заключается в том, что в каждом дочернем элементе сохраняются данные о его непосредственном родителе, то есть, рассматривая схему выше, элементы 2 и 5 содержат ссылку на элемент 1, а 3 и 4 - на элемент 2.

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

CREATE TABLE catalogs (
cat_id int(11) NOT NULL auto_increment,
parent_id int(11) NOT NULL default '0',
cat_name varchar(200) NOT NULL default '',
PRIMARY KEY (cat_id)
)

Вставим в полученную таблицу несколько записей:

// функция для вставки записей в MySQL
function sql_insert($parent_id, $cat_name) {
$query = "INSERT INTO catalogs(parent_id, cat_name) VALUES('".(int)$parent_id."', '$cat_name')";
mysql_query($query) or die(mysql_error());
return mysql_insert_id(); // возвращаем id внесенной записи
}
// соединение и выбор базы данных рассматривать не будем
$level[1][0] = sql_insert("0", "Программирование");
$level[2][0] = sql_insert($level[1][0], "Веб программирование");
$level[2][1] = sql_insert($level[1][0], "Системное программирование");
$level[3][0] = sql_insert($level[2][0], "PHP");
$level[3][1] = sql_insert($level[2][0], "Perl");
$level[3][2] = sql_insert($level[2][1], "C++");
$level[4][0] = sql_insert($level[3][2], "Visual C++");
$level[3][3] = sql_insert($level[2][1], "Delphi");

// Вторая ветвь
$level[1][1] = sql_insert("0", "Базы данных");
$level[2][2] = sql_insert($level[1][1], "MySQL");
$level[2][3] = sql_insert($level[1][1], "Oracle");
$level[2][4] = sql_insert($level[1][1], "MS Access");

Теперь выведем полученное дерево:

function get_tree($parent_id = 0, $prefix = "") {
global $out;
$query = "SELECT * FROM catalogs WHERE parent_id = '$parent_id'";
$result = mysql_query($query);
while ($row = mysql_fetch_array($result)) {
$out .= $prefix.$row['cat_name']."<br>";
get_tree($row['cat_id'], $prefix."&nbsp;&nbsp;");
}
return $out;
}
echo get_tree();

Так как мы имеем многоуровневое дерево, функцию get_tree() нам приходся вызывать рекурсивно, для одноуровневых деревьев (не больше одного уровня вложенности) этого не требуется.

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

К достоинствам данного метода построения деревьев можно отнести то, что каждый элемент дерева обладает достаточной степенью обособленности, так как с родителем его связывает значение только одного поля, которое мы без проблем можем изменить и элементарно поменять тем самым родителя. К недостаткам же - крайне неудобную работу при высоких уровнях вложенности. Так что этот алгоритм оптимально подходит для одноуровневых деревьев и деревьев с невысоким уровем вложенности (2 - 3 уровня).

Алгоритм Nested Sets.

Алгоритм Nested Sets - более мощный инструмент работы с деревьями. Класс для работы с ним вы можете скачать здесь. Архив состоит из двух файлов: dbtree.php - собственно, класс для работы с деревьями, и database.php - класс для работы с базой данных. Во второй файл вы можете добавить свои функции работы с MySQL и всячески подстраивать для себя, только не изменяйте функции, используемые классом в файле dbtree.php.

Алгоритм Nested Sets с первого взгляда может показаться сложным, но на самом деле он предельно прост. Суть его заключается в том, что он не сохраняет id родительского элемента, а использует три дополнительных поля: cat_left, cat_right и cat_level (имена полей вы можете изменить). Использует он их следующим образом.

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

Посмотрим, как поставит флажки наш человечек в схеме дерева из начала урока (синим отмечены флажки, поставленные при первом проходе элемента, зеленым - при возвращении из ветки).

элемент 1 [1] [10]
|
+ - элемент 2 [2] [7]
| |
| + - элемент 3 [3] [4]
| + - элемент 4 [5] [6]
|
+ - элемент 5 [8] [9]

Значения синих флажков в таблице MySQL запоминаются в поле cat_left, а зеленых - в поле cat_right, уровень вложенности - в поле cat_level.

Создадим таблицу с деревом, подобному указанному выше.

include("dbtree.php");
include("database.php");

$db = new CDatabase("your_database_name", "localhost", "root", "12345");
$tree = new CDBTree ($db, "catalogs2", "cat_id");

// создаем таблицу
$query="CREATE TABLE catalogs2(
cat_id int not null auto_increment primary key,
cat_left int not null,
cat_right int not null,
cat_level int not null,
cat_name varchar(200) not null)";
$db->query($query);

// заполняем таблицу

// создаем корневой элемент
$level[0][0]=$tree->clear();
// записываем основную часть дерева
$level[1][0] = $tree->insert($level[0][0], array("cat_name"=>"Программирование"));
$level[1][1] = $tree->insert($level[0][0], array("cat_name"=>"Базы данных"));

$level[2][0] = $tree->insert($level[1][0],
array("cat_name"=>"Веб программирование"));
$level[2][1] = $tree->insert($level[1][0],
array("cat_name"=>"Системное программирование"));$level[2][2] = $tree->insert($level[1][1], array("cat_name"=>"MySQL"));
$level[2][3] = $tree->insert($level[1][1], array("cat_name"=>"Oracle"));
$level[2][4] = $tree->insert($level[1][1], array("cat_name"=>"MS Access"));

$level[3][0] = $tree->insert($level[2][0], array("cat_name"=>"PHP"));
$level[3][1] = $tree->insert($level[2][0], array("cat_name"=>"Perl"));
$level[3][2] = $tree->insert($level[2][1], array("cat_name"=>"C++"));
$level[3][3] = $tree->insert($level[2][1], array("cat_name"=>"Delphi"));

$level[4][0] = $tree->insert($level[3][2], array("cat_name"=>"Visual C++"));

// Выводим дерево
$query = "SELECT * FROM catalogs2 ORDER BY cat_left";
$result = $db->query($query);
while ($row = $db->fetch_array($result)){
echo str_repeat("&nbsp;&nbsp;&nbsp;", $row['cat_level']).$row['cat_name']. " <font color='#0033FF'>[".$row['cat_left']."]</font>".
" <font color='#009900'>[".$row['cat_right']."]</font><br>";
}

Использование полей cat_left и cat_right позволяет манипулировать деревом практически во всех направлениях. Например, заметьте, что у элементов, не имеющих потомков, значения этих полей отличаются на единицу. А у потомков какого-либо данного элемента значения cat_left больше значения у выбранного родителя, а cat_right - меньше, причем, чем больше ветвь потомков, тем больше разность между значениями cat_right и cat_left у данного родителя (сравните "Веб программирование" и "Базы данных"). Основываясь на этих данных, сделаем выборку всех элементов, не имеющих родителей, а также всех потомков элемента "Системное программирование":

$query = "SELECT cat_left, cat_right FROM catalogs2 ". "WHERE cat_name = 'Системное программирование'";
$result = $db->query($query);
$val = $db->fetch_array($result);
$query = "SELECT * FROM catalogs2 WHERE cat_left > '".$val['cat_left']. "' AND cat_right < '".$val['cat_right']."' ORDER BY cat_left";
$result = $db->query($query);
echo "<b>Ветка 'Системное программирование'</b><br>";
while ($row = $db->fetch_array($result)) {
echo str_repeat("&nbsp;&nbsp;&nbsp;", $row['cat_level']). $row['cat_name']."<br>";
}
echo "<b>Все элементы, не имеющие потомков</b><br>";
$query = "SELECT * FROM catalogs2 WHERE cat_right - cat_left = 1";
$result = $db->query($query);
while ($row = $db->fetch_array($result)) {
echo $row['cat_name']." ( ".$row['cat_id']." )<br>";
}

Возможности этого класса вышеуказанным не ограничиваются. Можно логически домыслить, как найти всех родителей данного элемента, заканчивая корневым (что удобно при создании навигации по разделам), а также множество других возможностей. Настоятельно рекомендую перед использованием данного класса просмотреть в файле dbtree.php все комментарии перед методами класса, так как вышеприведенными методами этот класс не ограничивается.

На этом и заканчиваем наш урок. До встречи на следующем! Все свои вопросы Вы можете задавать на нашем форуме.