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

Question

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

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

[{имя: 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 в его иерархию)

Answer 1

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

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

 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 это маркер, который вы используете для обнаружения зацикливания в очереди.

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