VPF::Рекурсивное удаление ветки из дерева

mark2011

Дата 4.8.2011, 08:23 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 174
Регистрация: 28.6.2011

Репутация: 2
Всего: 2

Доброе утро!

Создавал тему в "Профи", её перенесли сюда... поэтому здесь и спрошу...

Речь идёт про списки смежности. Удаляю ветку из дерева. Но при этом нужно учитывать, что у неё может быть неограниченное количество подуровней, которые, по идее, нужно тоже удалить. Сейчас у меня так: удаляется ветка и её прямые потомки. Если у потомков есть ещё потомки, то они становятся корнями дерева, что не очень-то логично и корректно. Понимаю, что здесь требуется рекурсия, но пока не пойму, каким образом.

Если кто может, подскажите, или дайте ссылку, где можно внятно прочитать про это.

P . S . Вообще пишу свою библиотеку, потому что в инете есть какие-то отрывки, но чёткого класса для работы с деревом нет. Я, по крайней мере, не нашёл. Со вложенными множествами то же самое - dbtree, класс с 2005 года и, похоже, уже не поддерживается. Нужно что-то новое и оптимизированное.

mark2011

Дата 4.8.2011, 09:45 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 174
Регистрация: 28.6.2011

Репутация: 2
Всего: 2

Вот что-то нашёл в инете, начал так, но по-моему очень сложно, есть путь проще, наверняка smile

Возвращаем всех потомков родителя

Код


function tree_list_load_path($k_item)
{
        global $db;
        // Возвращает ложь в случае ошибки

  if(empty($k_item)||!is_numeric($k_item)) return false;

  $a_tree=array();

  while($k_item)
  {
    $db->query("select id, pid, name from test_tree where pid = ".$k_item . " order by id desc");
    
    
    while ($f=$db->parse_query('array'))
    {
        $a_tree= array(
            'k_item' => $f['id'],
            's_name' => $f['name'],
            'a_tree' => $a_tree
          );
    }
    $k_item=$f['pid'];
  }
  return $a_tree;
}

Приводим это всё к нормальному виду:

Код


function parse_recursive_array($array, $result = array())
{
    foreach ($array as $value)
    {
        if (!is_array($value))
        {
            $result[] = $value;
        }
        else
        {
            $result = parse_recursive_array($value, $result);
        }
    }
    
    return $result;
}

Загружаем родителя:

Код


$a = tree_list_load_path(6);
$a = parse_recursive_array($a);

В результате получаем структуру:

Код


Array
(
    [0] => 7
    [1] => 2.1
    [2] => 8
    [3] => 2.2
    [4] => 9
    [5] => 2.3
    [6] => 10
    [7] => 2.4
)

Пытаемся выявить всех потомков на неограниченном уровне вложенности

Код


foreach ($a as $key => $value)
{
    global $db;
    if ($key % 2 == 0)
    {
        print_r(tree_list_load_path($key));
    }
}

Как-то не срабатывает и ошибки не выдаёт...

mark2011

Дата 4.8.2011, 10:26 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 174
Регистрация: 28.6.2011

Репутация: 2
Всего: 2

Вот такой вариант (мой, самописный):

Код


function print_branch($begin_id, $result = array())
{
    global $db;
    $db->query('select * from test_tree where id = ' . $begin_id . ' or pid = ' . $begin_id);
    while ($data = $db->parse_query('array'))
    {
        $result[] = $data;
    }
    
    $ids = array();
    foreach ($result as $key => $value)
    {
        $ids[] = $result[$key]['id'] . '<br>';
    }
    
    foreach ($ids as $value)
    {
        $result = print_branch($value, $result);
    }
    return $result;
}

При выполнении кода:

Код


$a = print_branch(6);
print_r($a);

Выдаёт следующее:

Код


[Thu Aug 04 11:23:30 2011] [error] [client 127.0.0.7] PHP Fatal error:  Allowed memory size of 134217728 bytes exhausted (tried to allocate
 261904 bytes) in D:\\WebSites\\clevercms.ru\\class_tree.php on line 22

Строка 22:

Код


$result = print_branch($value, $result);

Вроде рекурсия правильная (не зацикливается) но почему перерасход памяти??

Добавлено через 3 минуты и 57 секунд
Изменил строку 22 вот на это:

Код


$result = print_branch(&$value, &$result);

В ответ получил:

Код


[Thu Aug 04 11:28:00 2011] [error] [client 127.0.0.7] PHP Fatal error:  Allowed memory size of 134217728 bytes exhausted (tried to allocate 576
bytes) in D:\\WebSites\\clevercms.ru\\classes\\class_mysql.php on line 104

Гораздо лучше! Но всё-таки ещё не то...

Это сообщение отредактировал(а) mark2011 - 4.8.2011, 10:27

Photon

Дата 6.8.2011, 13:56 (ссылка)

(нет голосов)

Загрузка ...

Злобный программер

Профиль
Группа: Участник
Сообщений: 282
Регистрация: 27.2.2009
Где: Таганрог

Репутация: 10
Всего: 12

Есть такая отличная вещь, как Nested Sets
Там, правда, есть некоторые проблемки при добавлении и удалении узла или ветви. Довольно трудоёмкая операция.. Зато получение любых ветвей - одно удовольствие

--------------------

With best regards..

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Общие вопросы \| Следующая тема »