Урок 18 - php - Каталог статей - ВСЕ ДЛЯ ПРОГРАММИСТА

Урок 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."  "); } 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("   ", $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("   ", $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 все комментарии перед методами класса, так как вышеприведенными методами этот класс не ограничивается. На этом и заканчиваем наш урок. До встречи на следующем!
1 2 3 4 5 Категория: php \| Добавил: SLOT85 (04.02.2012)
Просмотров: 843 \| Рейтинг: 0.0/0

Всего комментариев: 0

Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]