Как определить осиротевшие узлы - PullRequest
Новая
       18

Как определить осиротевшие узлы

0 голосов
/ 04 июня 2010

У меня есть иерархия узлов, хранящихся в БД. Я выбираю все, сохраняю их в массиве, затем перебираю их и создаю вложенный массив в памяти.

Вход выглядит так:

[{имя: A}, {имя: B}, {имя: X, родитель: A}, {имя: Y, родитель: A}, {имя: C}]

Вывод выглядит так:

[{name: A, дети: [{name: X}, {name: Y}]}, {B}, {C}]

Нет предела тому, насколько глубоко может быть вложенность.

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

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

Полагаю, мне удастся понять, что я снова и снова повторяю одни и те же вещи?

Редактировать 1 - код Это важный бит: 

    $cnt = count($array);
    do {
        $item = array_shift($array);
        if ($this->push($item)) {
            $cnt--;
        } else {
            array_push($array, $item);
        }
    } while ($cnt > 0);

($ this-> push () - это метод, который пытается найти родителя и, в случае успеха, вставляет $ item в его иерархию)

1 Ответ

1 голос
/ 04 июня 2010

Похоже, вы используете очередь (уберите спереди, добавьте сзади) структуры данных для хранения необработанных узлов. Как узлы вставлены в вашу структуру выходных данных, они удаляются из очереди. Если узел не может быть добавлен к выводу (потому что его «родитель» не имеет был перемещен в структуру выходных данных еще) это в очереди. В конце концов очередь должна стать пустой если нет узлов, в которых «родитель» не существует (сироты).

Я думаю, ваш алгоритм выглядит примерно так: 

 Do While not QueueEmpty()
    node = Dequeue() ' Remove from the front
    if not AddNodeToTree(node) then Queue(node) 'add to the back
 end

Где AddNodeToTree - это функция, которая успешно принимает узел добавляет его к выводу и возвращает True. В противном случае возвращается False вызывая перезапуск узла.

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

set NodeProcessed to False
Queue(SentinalNode) ' marker to identify cycle through queue
Do while not QueueEmpty()
  node = Dequeue()
  if isSentinalNode(node) then
     if NodeProcessed then 
        Queue(node)
        set NodeProcessed to False
     else
        ' Queue contains only orphans or is empty
     end
  end
  if AddNodeToTree(node) then
     set NodeProcessed to True
  else
     Queue(node)
  end
end

SentinalNode - это маркер, который вы используете для обнаружения зацикливания через очередь.

Ваша структура выходных данных выглядит так, как будто она содержит «лес» деревьев. То есть, это содержит несколько отличных деревьев. Если есть возможность что данный узел может быть общим для двух или более деревьев, выше Алгоритм не будет работать должным образом. Если узел может появиться не более одно дерево в «лесу», тогда выше должно быть хорошо.

...