302 MGraphics.ru - Учебник по PHP 4 - Деревья
Уроки photoshopa


Учебник по PHP 4

Деревья

Условия перепечатки материалов

Рейтинг статьи: 77777
Проголосовало 6 человек.
Оцените статью:

Урок 18. Деревья.

С человеком происходит то же, что и с деревом.
Чем больше стремится он вверх, к свету, тем глубже
уходят корни его в землю, вниз, в мрак и глубину - ко злу.
Фридрих Ницше

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

Все, кто имел дело с компьютером, имеют представление о деревьях. Например, это файловая система операционной системы.

Графически дерево можно представить следующим образом:

элемент 1
  |
  + - элемент 2
  |     |
  |     + - элемент 3
  |     + - элемент 4
  |
  + - элемент 5

Уровень вложенности и длина дерева не ограничены.

Создание деревьев.

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

Метод заключается в том, что в каждом дочернем элементе сохраняются данные о его непосредственном родителе, то есть, рассматривая схему выше, элементы 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 все комментарии перед методами класса, так как вышеприведенными методами этот класс не ограничивается.

Автор учебника: Артем Акатов
 Сайт: http://myphp.net.ru

Разместил: Vulko
Опубликовано: 15.02.2004
Статья "Учебник по PHP 4 - Деревья" прочтена 39063 раза.





Последние новости