2

В базе данных есть таблица хранящая список категорий

id   parentID     название
1       0               Категория 1
2       0               Категория 2
3       2               Категория 3
4       2               Категория 4

Нужно придумать алгоритм на php который бы переводил эту конструкцию во что-то подобное:

  1. Категория 1
  2. категория 2
    2.1 Категория 3
    2.2 Категория 4
8
  • Переведите в html в xml, потом в многомерный массив.
    – meboban
    4 янв 2014 в 14:39
  • не понимаю зачем xml? ваш комментарий навел меня на мысль использования динамического многомерного массива, но у меня все так же нет идей как это дело правильно считать из БД (MySQL)
    – atom-22
    4 янв 2014 в 14:47
  • вам нужна функция, которая будет проходить по массиву и находить для каждого элемента родителя (если parentID != 0) и записывать этот элемент в дети родителя (по ссылке), после чего будет удалять все элементы массива, у которых parentID != 0. В результате у вас останутся только те деревья, чьи корни действительно являются корневыми элементами искомого дерева. Если будет время, позже напишу пример.
    – etki
    4 янв 2014 в 14:52
  • основную суть алгоритма я представляю так: берем строку если родитель == 0 $array[id]=$name; иначе $array[parentID][]=$name; берем следующую строку и все заново. Логично?
    – atom-22
    4 янв 2014 в 14:59
  • У Вас сначала была ДОМ модель в табличной вёрстке, если нужно с базы, то ниже вам уже подсказали.
    – meboban
    4 янв 2014 в 15:12

2 ответа 2

6

Таблица в базе данных:

+--+-------------+--------+
|id|name         |parentid|
+--+-------------+--------+
|1 |Имя раздела 1|0       |
|2 |Имя раздела 2|0       |
|3 |Имя раздела 3|1       |
|4 |Имя раздела 4|2       |
|5 |Имя раздела 5|4       |
|6 |Имя раздела 6|2       |
+--+-------------+--------+

Массив, полученный после выборки из базы данных:

$arr = array(
    array(
        'id' => '1',
        'name' => 'Имя раздела 1',
        'parentid' => '0'
    ),
    array(
        'id' => '2',
        'name' => 'Имя раздела 2',
        'parentid' => '0'
    ),
    array(
        'id' => '3',
        'name' => 'Имя раздела 3',
        'parentid' => '1'
    ),
    array(
        'id' => '4',
        'name' => 'Имя раздела 4',
        'parentid' => '2'
    ),
    array(
        'id' => '5',
        'name' => 'Имя раздела 5',
        'parentid' => '4'
    ),
    array(
        'id' => '6',
        'name' => 'Имя раздела 6',
        'parentid' => '2'
    ),
);

Функции, для рекурсивного построения дерева:

function form_tree($mess)
{
    if (!is_array($mess)) {
        return false;
    }
    $tree = array();
    foreach ($mess as $value) {
        $tree[$value['parentid']][] = $value;
    }
    return $tree;
}

//$parent_id - какой parentid считать корневым
//по умолчанию 0 (корень)
function build_tree($cats, $parent_id)
{
    if (is_array($cats) && isset($cats[$parent_id])) {
        $tree = '<ul>';
        foreach ($cats[$parent_id] as $cat) {
            $tree .= '<li>' . $cat['name'];
            $tree .= build_tree($cats, $cat['id']);
            $tree .= '</li>';
        }
        $tree .= '</ul>';
    } else {
        return false;
    }
    return $tree;
}

Примеры использования
Вариант А:

$tree = form_tree($arr);
echo build_tree($tree, 0);  
  • Имя раздела 1
    • Имя раздела 3
  • Имя раздела 2
    • Имя раздела 4
      • Имя раздела 5
    • Имя раздела 6

Вариант Б:

$tree = form_tree($arr);
echo build_tree($tree, 2);  
  • Имя раздела 4
    • Имя раздела 5
  • Имя раздела 6

Как работает алгоритм

Исходный массив обрабатывается функцией form_tree();. Она формирует массив следующего вида:

$arr = array(
    0 => array(        
        array(
            'id' => '1',
            'name' => 'Имя раздела 1',
            'parentid' => '0'
        ),
        array(
            'id' => '2',
            'name' => 'Имя раздела 2',
            'parentid' => '0'
        ),
    ),
    1 => array(
        array(
            'id' => '3',
            'name' => 'Имя раздела 3',
            'parentid' => '1'
        ),
    ),
    2 => array(
        array(
            'id' => '4',
            'name' => 'Имя раздела 4',
            'parentid' => '2'
        ),        
        array(
            'id' => '6',
            'name' => 'Имя раздела 6',
            'parentid' => '2'
        ),
    ),
    4 => array(
        array(
            'id' => '5',
            'name' => 'Имя раздела 5',
            'parentid' => '4'
        ),
    ),
);

Как можно видеть, элементы исходного массива были разбиты на группы, согласно их родителю. В итоге получилась схема вида: родитель => массив потомков.

Далее, функция build_tree() рекурсивно обрабатывает этот массив.
Она начинает свою работу с ID раздела, указанного в качестве корневого.
В первую очередь, она стремится перебрать потомков данного раздела. В процессе перебора функция проверяет, а не является ли текущий потомок в свою очередь чьим-то родителем? Для этого функция вызывает саму себя, с указанием в качестве ID корневого раздела ID текущего элемента.

введите сюда описание изображения

Рассмотрим работу алгоритма на примере "Вариант А":

  • Мы начинаем перебор с ID = 0, в качестве корневого.
  • Первый раздел, который мы встречаем во время перебора, это Имя раздела 1.
  • Выводим этот раздел.
    • Начинаем перебор с ID = 1, в качестве корневого.
    • Первый раздел, который мы встречаем во время перебора, это Имя раздела 3.
    • Выводим этот раздел.
      • Мы начинаем перебор с ID = 3, в качестве корневого.
      • Подразделов нет, функция завершает свою работу.
    • Разделов больше нет, функция завершает свою работу.
  • Продолжаем перебор с ID = 0, в качестве корневого.
  • Второй раздел, который мы встречаем во время перебора, это Имя раздела 2.
  • Выводим этот раздел.
    • Начинаем перебор с ID = 2, в качестве корневого.
    • Первый раздел, который мы встречаем во время перебора, это Имя раздела 4.
    • Выводим этот раздел.
      • Мы начинаем перебор с ID = 4, в качестве корневого.
      • Первый раздел, который мы встречаем во время перебора, это Имя раздела 5.
      • Выводим этот раздел.
          •  Мы начинаем перебор с ID = 5, в качестве корневого.
          •  Подразделов нет, функция завершает свою работу.
      • Разделов больше нет, функция завершает свою работу.
    • Второй раздел, который мы встречаем во время перебора, это Имя раздела 6.
    • Выводим этот раздел.
      • Мы начинаем перебор с ID = 6, в качестве корневого.
      • Подразделов нет, функция завершает свою работу.
    • Разделов больше нет, функция завершает свою работу.
  • Разделов больше нет, функция завершает свою работу.

В примере выше, уровень вложенности соответствует тому, в который раз по счету функция build_tree() вызвала сама себя.

2
  • а как работает данный алгоритм?
    – upward
    20 янв 2017 в 13:19
  • @upward, добавил подробное описание работы алгоритма
    – VenZell
    8 фев 2017 в 8:00
0

Если хотите на php алгоритм. то делайте так например:

  1. Пишем функцию, которая будет принимать 1 параметр на вход Ид родителя. Для каждого полученного значения она вызывает сама себя и передеает себе ИД только что полученного значения.

Например:

function get_tree($in=0,$array){
// $xx= mysql_query("select * from tree WHERE parent=$in")
  $tt = mysql_fetch_array($xx){
    $array[$ur][$tt[id]] = $tt['name'];
    get_tree($tt['id'],$array)
    }
}

Думаю суть понятна. Код привел для примера, писал его прям тут. На выходе вы поулчим массив с уровнями

1
  • 2
    Рекурсивные походы в базу. Не надо так.
    – vp_arth
    8 фев 2017 в 8:17

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.