Создание иерархии обхода дерева с нуля с использованием PHP/MySQL

Question

Создание иерархии обхода дерева с нуля с использованием PHP/MySQL

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

Проблема в том, что функция rebuild_tree была бы достаточно хороша (другими словами, эффективна для больших деревьев).

Пример запроса:

 CREATE TABLE `t_categories`(
   `id` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
   `title` VARCHAR(45) NOT NULL,
   `lft` INTEGER UNSIGNED NOT NULL,
   `rght` INTEGER UNSIGNED NOT NULL,
   PRIMARY KEY (`id`)
 );

 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 1',1,16);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 2',2,3);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 3',4,7);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 4',5,6);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 5',8,13);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 6',9,12);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 7',10,11);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 8',14,15);

Результаты таблицы выглядят так:

 ID    TITLE   LFT    RGHT
 1     Cat1    1      16
 2     Cat2    2      3
 3     Cat3    4      7
 4     Cat4    5      6
 5     Cat5    8      13
 6     Cat6    9      12
 7     Cat7    10     11
 8     Cat8    14     15

Я привел пример данных выше, но мне нужно также создать совершенно новый узел с нуля.

Итак, как я могу добавить новый узел в это дерево, используя функцию PHP, которая эффективна с большими деревьями?

1

php mysql tree traversal rebuild

Источник

user272478 07 мар '11 в 18:07

4 ответа

Другие вопросы по тегам php mysql tree traversal rebuild

user340457 07 мар '11 в 18:31 2011-03-07 18:31 · Answer 1 · 2011-03-07 18:31

Это целко дерево. Подход Simpelst будет сначала проходить по глубине дерева и обновлять только левое значение, а затем рекурсивным образом правильное значение. Вставка намного дороже.

2

Источник

user340457 07 мар '11 в 18:31

user535724 07 мар '11 в 18:34 2011-03-07 18:34 · Answer 2 · 2011-03-07 18:34

Я рекомендую вам добавить поле "родительский идентификатор" в структуру таблицы вместо полей "левый" и "правый". Если важно, чтобы у вас был заказ на товары для детей, используйте также поле int localorder.

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

CREATE TABLE `t_categories`(
   `keyid` INTEGER UNSIGNED NOT NULL,
   `title` VARCHAR(45) NOT NULL,
   `parentid` INTEGER UNSIGNED NOT NULL,
   `sortorder` INTEGER UNSIGNED NOT NULL,
   PRIMARY KEY (`id`)
 );

-- root item, no parent
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (1, 'Root', 0, 0);

-- first level
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (2, 'a:', 1, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (3, 'b:', 1, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (3, 'c:', 1, 3);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (4, 'd:', 1, 4);

-- second level

 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (5, 'a:\temp', 2, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (6, 'a:\docs'', 2, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (7, 'a:\music', 2, 3);

 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (8, 'c:\temp', 4, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (9, 'c:\docs'', 4, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (10, 'c:\music', 4, 3);

-- and so on

user340457 07 мар '11 в 20:23 2011-03-07 20:23 · Answer 3 · 2011-03-07 20:23

Это же дерево используется компрессией Хаффмана для подсчета появления буквы в данном документе. Я думаю, что для кодирования строки алгоритм затем использует также обход в глубину, чтобы буква с наибольшим количеством вхождений кодировалась с наименьшим возможным битом. Я не знаю, полезно ли это здесь, но наименьшую энтропию текста можно найти, используя теорию Шеннона -log(x)+log(2), где x - буква, а log (2) - база в битах. 2.

user535724 08 мар '11 в 16:19 2011-03-08 16:19 · Answer 4 · 2011-03-08 16:19

Мой предыдущий ответ неполон. Это резюме, весь код должен быть в посте на форуме. Забыли спросить, процедурный PHP или объектно-ориентированный PHP?

MySQL: СОЗДАТЬ ТАБЛИЦУ t_categories(keyid INTEGER НЕ ПОДПИСАНО НЕ НУЛЬ, title VARCHAR (45) НЕ NULL, parentid INTEGER НЕ ПОДПИСАНО НЕ НУЛЬ, sortorder INTEGER НЕ ПОДПИСАН НЕ НУЛЬ, ПЕРВИЧНЫЙ КЛЮЧ (id));

Заголовки функций PHP:

// globar var, действует как тип / * typedef * / treeNodeType = array ("keyid" => 0, "title" => "", "parentid" => 0, "sortorder" => 0,)

// globar var, действует как тип /* typedef */ treeType = array( "root" => nil, "what" => "",)

/ * treeNodeType / function insertNode (/ treeType / ATree, AParentId, ATitle) {...} / void / функция deleteNode (/ treeType * / ATree, AKeyId) {...}

// -> MAIN main ();

/ * void * / function main () {// treeType myTree; myTree = treeType;

// вставляем root = 0 rootNode = insertNode (myTree, 0, '[PC]');

...}