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

Question

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

вход выглядит следующим образом:

[{имя: A}, {имя: B}, {имя: Х, родитель: А}, {имя: Да, родитель: A}, { название: С}]

выход выглядит следующим образом:

[{имя: А, дети: [{имя: X}, {имя: Y}]}, {B}, {C}]

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

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

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

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

Edit 1 - код Это важный бит:

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

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

Answer 1

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

Я полагаю, ваш algorithim выглядит как

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 , заставляя узел перерабатывать.

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

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

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