如何识别孤立节点

Question

我在数据库中存储了一个节点层次结构。我选择全部，将它们存储在一个数组中，然后迭代它们并在内存中创建一个嵌套数组。

输入如下所示：

[{名称：A}，{名称：B}，{名称：X，父级：A}，{名称：Y，父级：A}，{名称：C}]

输出如下所示：

[{姓名：A，孩子：[{姓名：X}，{姓名：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

是用于检测循环的标记 通过队列。

您的输出数据结构看起来像是包含树木的“森林”。那是， 它包含几棵不同的树。如果有任何可能 给定的节点可以在两棵或多棵树之间共享，上面 算法将无法正常工作。如果一个节点最多可能出现在 “森林”中的一棵树那么上面的应该没问题。