如何识别孤立节点
我有一个存储在数据库中的节点层次结构。我选择全部,将它们存储在一个数组中,然后迭代它们并在内存中创建一个嵌套数组。
输入看起来像这样:
[{名称: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 插入其层次结构中)
I have a hierarchy of nodes stored in DB. I select all, store them in an array, then iterate over them and create a nested array in memory.
The input looks like this:
[{name: A}, {name: B}, {name: X, parent: A}, {name: Y, parent: A}, {name: C}]
The output looks like this:
[{name: A, children:[{name: X}, {name: Y}]}, {B}, {C}]
There is no limit on how deep the nesting can go.
The problem I have is that if one of the records has an invalid parent reference, it cannot be put in the hierarchy and the script ends in an infinite loop, trying to find the parent.
I bet there's a way to tell when I've fallen into the infinite loop. For the record, when in the loop I realize there's no parent to insert the item into, I push the item at the end of the array because the parent might exists down the line.
I suppose I should be able to realize that I'm cycling the same items over and over again?
Edit 1 - the code
This is the important bit:
$cnt = count($array);
do {
$item = array_shift($array);
if ($this->push($item)) {
$cnt--;
} else {
array_push($array, $item);
}
} while ($cnt > 0);
($this->push() is a method that tries to find a parent and, if it succeeds, inserts $item into its hierarchy)
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
看起来您正在使用队列(从前面删除,添加到后面)类型
存储未处理节点的数据结构。由于节点是
插入到输出数据结构中,它们将从队列中删除。如果
无法将节点添加到输出中(因为它的“父节点”还没有
已移至输出数据结构)
它被重新排队。最终队列应该变空
除非有“父节点”不存在的节点(孤儿)。
我想你的算法看起来像
其中
AddNodeToTree
是一个成功获取节点的函数将其添加到输出并返回
True
。否则返回False
导致节点回收。
您唯一需要做的就是将一个哨兵节点添加到队列的后面
以及一个标志,指示队列中至少有一个节点已被消耗
在一个完整的循环中。上述算法变为:
SentinalNode
是一个用于检测循环的标记通过队列。
您的输出数据结构看起来像是包含树木的“森林”。那是,
它包含几棵不同的树。如果有任何可能
给定的节点可以在两棵或多棵树之间共享,上面
算法将无法正常工作。如果一个节点最多可能出现在
“森林”中的一棵树那么上面的应该没问题。
Looks like you are using a queue (remove from the front, add to the back) kind
of data structure to store unprocessed nodes. As nodes are
inserted into your output data structure they are dropped from the queue. If
a node cannot be added to the output (because its 'parent' has not
been moved to the output data structure yet)
it is re-queued. Eventually the queue should become empty
unless there are nodes where the 'parent' does not exist (orphans).
I imagine your algorithim looks something like
Where
AddNodeToTree
is a function that takes a node, successfullyadds it to the output and returns
True
. Otherwise it returnsFalse
causing the node to recycle.
The only thing you should have to do is add a sentinal node to the back of the queue
and a flag to indicate that at least one node was consumed from the queue
during one complete cycle through it. The above algorithm becomes:
The
SentinalNode
is a marker that you use to detect loopingthrough the queue.
Your output data structure looks like it contains a 'forest' of trees. That is,
it contains several distinct trees. If there is any possibility
that a given node may be shared among two or more trees, the above
algorithm will not work properly. If a node may appear in at most
one tree in the 'forest' then the above should be fine.