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

Структуру данных лучше взять общепринятую — в записи сообщения или рубрики форума содержится идентификатор родителя. Для организации вывода дерева напрашивается рекурсивная функция. Именно так сделано в Phorum’е [http://phorum.org]. Файл include/multi-threads.php содержит функцию thread, которая строит вызывается для каждого корневого сообщения и рекурсивно вызывает себя для ответов на них:
function thread ($seed = 0) {
…

if(@is_array($messages[$seed]["replies"])) {
$count = count($messages[$seed]["replies"]);
for($x = 1;$ x <= $count; $x++) {
$key = key($messages[$seed]["replies"]);
thread ($key);
next ($messages[$seed]["replies"]);
}
}
}

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

Для построения дерева достаточно знать последовательность вывода рубрик и их уровень в дереве. Добавим два поля с этими данными в таблицу: level (TINYINT(4). 127 уровней — хватит?) и sortorder (VARCHAR(128)).

Всё, что нам нужно для построения дерева — это идентификатор рубрики и её родителя. Допустим, мы имеем в каталоге несколько рубрик такого содержания:
———
id parent
———
3 0
5 0
7 0
10 3
11 7
12 5
13 3
16 10
21 16
26 11
30 3
47 7
60 10
73 13
75 47
———

Структура дерева, подобие которой мы хотим получить такова:
o- 3
|
+-o- 10
| |
| +-o- 16
| | |
| | +-o- 21
| |
| +-o- 60
|
+-o- 13
| |
| +-o- 73
|
+-o- 30

o- 5
|
+-o- 12

o- 7
|
+-o- 11
| |
| +-o- 26
|
+-o- 47
|
+-o- 75

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

Вернёмся ещё раз к таблице id-parent. Это рубрики, уже отсортированные по некоторому признаку, по которому мы хотим сортировать элементы одинакового уровня. Например, по убыванию числа сайтов. Кроме id и родительской рубрики мы знаем и номер каждой из них в данном списке. Выровняем эти номера до нужной длины, добавив слева нули. После этого для каждой рубрики сделаем текстовую строку с номерами всех её родителей от самого корня:
——————————
id sort parent sortorder level
——————————
3 1 0 01 0
5 2 0 02 0
7 3 0 03 0
10 4 3 0104 1
11 5 7 0305 1
12 6 5 0206 1
13 7 3 0107 1
16 8 10 010408 2
21 9 16 01040809 3
26 10 11 030510 2
30 11 3 0111 1
47 12 7 0312 1
60 13 10 010413 2
73 14 13 010714 2
75 15 47 031215 2
——————————

При сортировке по полю sortorder мы получим именно то, что нам нужно:
——————————
id sort parent sortorder level
——————————
3 1 0 01 0
10 4 3 0104 1
16 8 10 010408 2
21 9 16 01040809 3
60 13 10 010413 2
13 7 3 0107 1
73 14 13 010714 2
30 11 3 0111 1
5 2 0 02 0
12 6 5 0206 1
7 3 0 03 0
11 5 7 0305 1
26 10 11 030510 2
47 12 7 0312 1
75 15 47 031215 2
——————————

Отступ слева делается, учитывая поле level.

Важно так же отметить, что нам не нужно ничего сортировать в самом скрипте. Для формирования полей sortorder и level нужно заблокировать таблицу от записи (чтобы не произошло изменения структуры веток), выбрать из базы идентификатор рубрики и её родителя, отсортировав по нужному признаку, и записать их в простой двухмерный массив. Затем обработать массив последовательно от первого до последнего уровня и записать поля sortorder и level в таблицу.

Для формирования sortorder не нужно рекурсии (хотя можно, и, вероятно, она работать будет даже быстрее). Достаточно пройтись по массиву одним и тем же циклом. В нём, если рубрика не обработана, для неё формируется поле sortorder из поля sort и родительского sortorder. Если родительская рубрика ещё не обработана, поднимается флаг $unprocessed_rows_exist и цикл запускается ещё раз.
mysql_query(«LOCK TABLES dir WRITE»);

$result = mysql_query(«SELECT id, IFNULL(parent,0) as parent \
FROM dir ORDER BY sites DESC, title»);

while ($row = mysql_fetch_array($result)) {
$count++;
$data["parent"][$row["id"]] = $row["parent"];
$data["sort"][$row["id"]] = $count;
}

reset($data);

$unprocessed_rows_exist = true;
while($unprocessed_rows_exist) {
$unprocessed_rows_exist = false;
while (list($i, $v) = each($data["parent"])) {
if(($data["parent"][$i] == 0 || !isset($data["sort"][$data["parent"][$i]])) &&
!isset($data["sortorder"][$i])) {
$data["sortorder"][$i] = str_pad($data["sort"][$i], $max,
«0″, STR_PAD_LEFT);
$data["level"][$i] = 0;
}
elseif(!isset($data["sortorder"][$i]) &&
isset($data["sortorder"][$data["parent"][$i]])) {
$data["sortorder"][$i] = $data["sortorder"][$data["parent"][$i]].
str_pad($data["sort"][$i], $max, «0″, STR_PAD_LEFT);
$data["level"][$i] = $data["level"][$data["parent"][$i]] + 1;
}
elseif(!isset($data["sortorder"][$i]) &&
isset($data["sort"][$data["parent"][$i]])) {
$unprocessed_rows_exist = true;
}
}

reset($data);

Отмечу, что данный алгоритм не зацикливается при наличии строк с битым полем parent и не пропускает их, а делает корневыми. Рекурсивный алгоритм их просто пропустит.

После выполнения этого цикла мы имеем массивы «id => level» и «id => sortorder». Отправляем в базу всего один запрос, пользуясь внутренними функциями MySQL ELT и FIND_IN_SET:
mysql_query(«UPDATE dir SET sortorder=ELT(FIND_IN_SET(id,’».
implode(«,», array_keys($data["sortorder"])).
«‘),». implode(«,», $data["sortorder"]).
«), level=ELT(FIND_IN_SET(id,’».
implode(«,», array_keys($data["level"])).
«‘),». implode(«,», $data["level"]).
«) WHERE id IN («.
implode(«,», array_keys($data["sortorder"])).
«)»);

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

В форумах чаще всего используется сортировка по дате написания сообщения. Поэтому поле sortorder можно смело делать из своего и родительского timestamp’а, выровненного функцией str_pad [http://www.php.net/manual/en/function.str-pad.php] до 11-значной длины.

Источник:   codingrus.ru