- shurinskiy / category_tree.php
- Бинарное дерево поиска на PHP
- Построение дерева на php (вывод меню с неограниченной вложенностью)
- Как делать не нужно
- Как делать нужно
- Построение и вывод дерева на php
- Подготовка базы данных
- Вывод дерева на PHP
- Вывод меню на PHP4
- Вывод меню на PHP5
- Комментарии (Написать комментарий)
shurinskiy / category_tree.php
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| /** |
| * Пример кода который будет упорядочивать рекурсивно массив и превращать его в дерево по |
| * идентификаторам родительских элементов — при этом он работает с произвольным уровнем вложенности. |
| * В этом примере, предпологается использование одной корневой категории, не имеющей потомков. |
| **/ |
| $v_arr = array( |
| array(ID = > «0», name = > «корневая», parent= > «-1»), |
| array(ID = > «1», name = > «первая», parent= > «0»), |
| array(ID = > «2», name = > «вторая», parent= > «0»), |
| array(ID = > «3», name = > «третья», parent= > «1»), |
| array(ID = > «4», name = > «четвертая», parent= > «1»), |
| array(ID = > «5», name = > «пятая», parent= > «2»), |
| array(ID = > «6», name = > «шестая», parent= > «2»), |
| array(ID = > «7», name = > «седьмая», parent= > «5»), |
| array(ID = > «8», name = > «восьмая», parent= > «5») |
| ); |
| $v_tree = array(); |
| /** |
| * Построить дерево |
| **/ |
| function make_tree($arr, &$tree, $par_id=-1) |
| foreach($arr as $item) |
| if($item[‘parent’] == $par_id) |
| if( ! is_array($tree)) |
| $tree = array(); |
| > |
| $tree[$item[‘ID’]] = array( |
| ‘name’ = > $item[‘name’], |
| ‘ID’ = > $item[‘ID’], |
| ‘parentID’ = > $item[‘parent’] |
| ); |
| make_tree($arr, $tree[$item[‘ID’]], $item[‘ID’]); |
| > |
| > |
| > |
| /** |
| * Обойти дерево и преобразовать в список |
| **/ |
| function menu_output($arr) |
| $html = »; |
| foreach($arr as $value) |
| if(! is_array($value)) continue; |
| $html .= ‘ < li >‘; |
| $html .= $value[‘name’]; |
| $html .= menu_output($value); |
| $html .= ‘ ‘; |
| > |
| return $html ? ‘ < ul >‘.$html.’ ‘ : »; |
| > |
| make_tree($v_arr, $v_tree); // построить дерево из массива |
| echo menu_output(array_shift($v_tree)); // избавляюсь от корневого элемента дерева, а остальное вывожу как список |
Источник
Бинарное дерево поиска на PHP
Этот пост явился следствием прочтения вот этого перевода статьи о структурах данных для PHP-прогрммистов. В посте было рассказано о некоторых структурах данных, в том числе о бинарном дереве поиска, но самую интересную часть, то есть удаление узлов бинарного дерева, автор обошел стороной.
После прочтения перевода у меня появилось жгучее желание реализовать это дерево на PHP полнофункционально, то есть, включая удаление узлов из него, что я и сделал ниже по тексту:)
Обратите внимание, что я не призываю использовать бинарное дерево поиска написанное на PHP в реальном коде, реализация носит исключительно образовательный характер).
И так, реализация дерева и операции вставки нового узла, я думаю, в комментариях не нуждаются, так как практически ничем не отличаются от реализации в переводе:
class BinaryNode < public $value; public $left = NULL; public $right = NULL; public function __construct ($value) < $this->value = $value; > > class BinaryTree < protected $root = NULL; public function isEmpty () < return is_null($this->root); > public function insert ($value) < $node = new BinaryNode($value); $this->insertNode($node, $this->root); > protected function insertNode (BinaryNode $node, &$subtree) < if (is_null($subtree)) < $subtree = $node; >else < if ($node->value < $subtree->value) < $this->insertNode($node, $subtree->left); > elseif ($node->value > $subtree->value) < $this->insertNode($node, $subtree->right); > > return $this; > > Что бы удалить узел дерева, нам сначала понадобится его найти. Для этого напишем рекурсивную функцию поиска узла в нашем дереве:
protected function &findNode ($value, &$subtree) < // Если элемент не найден, возвращаем FALSE if (is_null($subtree)) < return FALSE; >// Для искомого значения меньшего, чем значение узла, продолжаем искать в левом поддереве if ($subtree->value > $value) < return $this->findNode($value, $subtree->left); > // Для искомого значения большего, чем значение узла, продолжаем искать в правом поддереве elseif ($subtree->value < $value) < return $this->findNode($value, $subtree->right); > // Если искомое значение равно значению узла, то возвращаем этот узел else < return $subtree; >> Приступим к реализации алгоритма удаления узла из дерева. Суть алгоритма такова:
- если у узла нет потомков (поддеревьев), то смело его удаляем;
- если есть один потомок (только правое или левое поддерево), то заменяем удаляемый узел потомком;
- если есть оба потомка, то:
- если у правого поддерева нет левого потомка, то заменяем удаляемый узел правым потомком, сохраняя левую ветвь удаляемого узла;
- если у правого поддерева есть левый потомок, то копируем его значение в удаляемый узел и рекурсивно удаляем.
Непосредственно метод удаления узла:
public function delete ($value) < // Выьрасываем исключение при попытке удаления элемента из пустого дерева if ($this->isEmpty()) < throw new UnderflowException('Tree is empty!'); >// Ищем нод в дереве $node = &$this->findNode($value, $this->root); // Если нод найден в дереве, то рекурсивно удаляем его if ($node) < $this->deleteNode($node); > return $this; > // Метод рекурсивного удаления, найденого нода из дерева protected function deleteNode (BinaryNode &$node) < // Если у узла нет потомков, удаляем его if (is_null($node->left) && is_null($node->right)) < $node = NULL; >// Если у узла нет левого поддерева, заменяем его правым поддеревом elseif (is_null($node->left)) < $node = $node->right; > // Если у узла нет правого поддерева, заменяем его левым поддеревом elseif (is_null($node->right)) < $node = $node->left; > // Если у узла есть оба потомка else < // Если у правого поддерева нет левого потомка, то заменяем удаляемый узел правым потомком, сохраняя левую ветвь удаляемого узла if (is_null($node->right->left)) < $node->right->left = $node->left; $node = $node->right; > // если у правого поддерева есть левый потомок, то копируем его значение в удаляемый узел и рекурсивно удаляем else < $node->value = $node->right->left->value; $this->deleteNode($node->right->left); > > >Бинарное дерево поиска готово.
P.S.: В листингах кода, я намеренно вырезал phpdoc-комментарии и не использовал пространства имен, чтобы их не загромождать.
Полные версии исходных кодов бинарного дерева поиска (а так же реализации еще нескольких структур данных, — одно/двухсвязные списков и стека/очереди, реализованных с помощью этих списков) можно посмотреть на githubе.Источник
Построение дерева на php (вывод меню с неограниченной вложенностью)
Современные сайты и интернет магазины требуют меню с неограниченной вложенностью. Обычно заказчики сами не знают, какая вложенность может понадобиться их сайту в будущем.
При создании сайтов и интернет магазинов многие программисты сталкиваются с проблемой вывода меню с неограниченной вложенностью. Ведь если сайт будет с меню без подкатегорий, то стоимость сайта будет очень низкая. Чтобы увеличить качество и стоимость создания сайта, в этой статье мы рассмотрим, как нужно делать меню неограниченной вложенностью, с 1-им циклом и 1-м запросом к базе, и какое меню делать не нужно. Начнем с того, как делать не нужно.
Как делать не нужно
Многие начинающие разработчики при создании меню, которое состоит, например, из 3 уровней вложенности, делают 3 вложенных цикла, в каждом цикле делают запросы к базе данных на выборку и вывод подкатегорий. В этом методе есть следующие недостатки:
- Огромное кол-во запросов к базе данных
Например, в интернет-магазине меню состоит из 300-т категорий и подкатегорий. Для вывода такого меню нужно 100-ни запросов, что очень сильно грузит сервер, и тормозит загрузку сайта. - Заказчик не сможет сам добавлять уровень вложенности из системы управления
- Если заказчик попросит добавить новый уровень вложенности, придется потратить очень много времени и сил на это.
У нас был заказчик, который очень удивлялся высокой стоимости поддержки сайта, т.к. у него и вывод меню был сделан не правильно, и все остальное. И для веб мастера нужно было потратить много сил и времени, чтобы что-то исправить на сайте. В итоге он решил сделать себе новый сайт. Хотя стоимость сайта была достаточно высока, но она окупилась через какое-то время, за счет низкой стоимости поддержки сайта.
Как делать нужно
Нужно делать так, чтобы вложенность меню генерировалась автоматически, и было всего 1-о обращение к базе данных.
Построение и вывод дерева на php
Сейчас мы сделаем вывод дерева на примере структуры сайта нашей компании (ox2.ru). Мы постоим дерево следующего вида (3 уровня вложенности):
Подготовка базы данных
Для построения дерева на php нам нужна база данных следующего вида:
Первое поле id категории, оно уникально для каждой категории. Второе поле name – имя категории, третье полеparent_id – оно ссылается на id категории родителя.
Например, для раздела Тариф «Оптимальный» parent_id = 4, поскольку она является подкатегорией раздела с id равным 4-ем (Создание интернет магазина, а она имеет parent_id равным 2-ум, т.к. является 2-ым уровнем вложенности раздела Услуги). Если parent_id = 0, то это главная категория.
Вот дамп нашей базы данных:
-- -- База данных: `ox2.ru-test-base` -- CREATE DATABASE `ox2.ru-test-base` DEFAULT CHARACTER SET cp1251 COLLATE cp1251_general_ci; USE `ox2.ru-test-base`; -- -------------------------------------------------------- -- -- Структура таблицы `category` -- CREATE TABLE IF NOT EXISTS `category` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(255) DEFAULT NULL, `parent_id` int(11) NOT NULL DEFAULT '0', PRIMARY KEY (`id`), KEY `parent_id` (`parent_id`) ) ENGINE=MyISAM DEFAULT CHARSET=cp1251 AUTO_INCREMENT=18 ; -- -- Дамп данных таблицы `category` -- INSERT INTO `category` (`id`, `name`, `parent_id`) VALUES (1, 'Главная', 0), (2, 'Услуги', 0), (3, 'Наши работы', 0), (4, 'Создание интернет магазина', 2), (5, 'Создание сайта', 2), (6, 'Продвижение сайта', 2), (13, 'Продвижение по позициям', 6), (7, 'Тариф «Оптимальный»', 4), (8, 'Тариф «Расширенный»', 4), (9, 'Тариф «Максимальный»', 4), (10, 'Сайт визитка', 5), (11, 'Фирменный сайт', 5), (12, 'Корпоративный сайт', 5), (14, 'Продвижение по трафику', 6), (15, 'Сроки и гарантии', 6), (16, 'Создание интернет магазина', 3), (17, 'Создание сайта', 3);
Вывод дерева на PHP
Поскольку много читателей не знакомы с PHP5, мы сделали 2 версии вывода меню (на PHP4 и на PHP5)
Для тех кто программирует на PHP5, пропустите следующий раздел
Вывод меню на PHP4
return $result; > //В переменную $category_arr записываем все категории $category_arr = getCategory(); /** * Вывод дерева * @param Integer $parent_id - id-родителя * @param Integer $level - уровень вложености */ function outTree($parent_id, $level) < global $category_arr; //Делаем переменную $category_arr видимой в функции if (isset($category_arr[$parent_id])) < //Если категория с таким parent_id существует foreach ($category_arr[$parent_id] as $value) < //Обходим /** * Выводим категорию * $level * 25 - отступ, $level - хранит текущий уровень вложености (0,1,2..) */ echo "
" . $value["name"] . ""; $level = $level + 1; //Увеличиваем уровень вложености //Рекурсивно вызываем эту же функцию, но с новым $parent_id и $level outTree($value["id"], $level); $level = $level - 1; //Уменьшаем уровень вложености > > > outTree(0, 0); ?>Вывод меню на PHP5
_db = new PDO("mysql:dbname=ox2.ru-test-base;host=localhost", "root", ""); //В переменную $_category_arr записываем все категории (см. ниже) $this->_category_arr = $this->_getCategory(); > /** * Метод читает из таблицы category все сточки, и * возвращает двумерный массив, в котором первый ключ - id - родителя * категории (parent_id) * @return Array */ private function _getCategory() < $query = $this->_db->prepare("SELECT * FROM `category`"); //Готовим запрос $query->execute(); //Выполняем запрос //Читаем все строчки и записываем в переменную $result $result = $query->fetchAll(PDO::FETCH_OBJ); //Перелапачиваем массим (делаем из одномерного массива - двумерный, в котором //первый ключ - parent_id) $return = array(); foreach ($result as $value) < //Обходим массив $return[$value->parent_id][] = $value; > return $return; > /** * Вывод дерева * @param Integer $parent_id - id-родителя * @param Integer $level - уровень вложености */ public function outTree($parent_id, $level) < if (isset($this->_category_arr[$parent_id])) < //Если категория с таким parent_id существует foreach ($this->_category_arr[$parent_id] as $value) < //Обходим ее /** * Выводим категорию * $level * 25 - отступ, $level - хранит текущий уровень вложености (0,1,2..) */ echo "" . $value->name . ""; $level++; //Увеличиваем уровень вложености //Рекурсивно вызываем этот же метод, но с новым $parent_id и $level $this->outTree($value->id, $level); $level--; //Уменьшаем уровень вложености > > > > $tree = new TreeOX2(); $tree->outTree(0, 0); //Выводим дерево ?>Современные сайты и интернет магазины требуют меню с неограниченной вложенностью. Обычно заказчики сами не знают, какая вложенность может понадобиться их сайту в будущем. При создании сайтов и интернет магазинов многие программисты сталкиваются с проблемой вывода меню с неограниченной вложенностью.
Комментарии (Написать комментарий)
- , то можно отказаться от $level и вывод сделать более красивым
Сергей [14.08.2015] Комментарий:
Спасибо, ваша статья помогла мне решить поставленную задачу. Скрипт написал правда свой, но идею с логикой частично позаимствовал у вас )Иван [16.06.2015] Комментарий:
Спасибо за образец, ваш сайт помогает в освоении практики программирования.Источник
