用于查找非父/祖父/ /等或子/孙等的所有链接对象的算法
我有一个名为Device的对象。 Device可以有一个父 Device 。 Device也可以有n个子Devices 。
我有一个下拉列表，显示所有可选Devices 。 我可以很容易地获得数据库中的所有Devices – db.Devices 。
层次结构可以是无限级别的。
我需要让所有不在树中给定Device之上或之下的Device 。 基本上我要求与给定Device无关的Device （父母/祖父母/祖父母/祖父母/等或儿童/孙子/曾孙子等）。 我还需要从列表中排除给定的Device 。
做这个的最好方式是什么？ 我应该使用递归吗？
（我使用C＃和Entity Framework与SQL Server数据库，所以我可以使用Linq To SQL或使用模型本身。）
我的方法是首先获得设备D所有兄弟姐妹：
P = parent of the device sibs = {all children of P that are not D}
d in sibs中任何d in sibs任何后代都与D无关。 继续走上家谱：
G = grandparent of the device sibs = sibs union {all children of G that are not P}
继续这样，集合sibs及其所有后代都是你所追求的集合。
在伪代码中：
D = device; siblings = {}; while (D has parent) { P = parent(D); siblings = siblings union (children(P) \ D); D = P; } return descendants(siblings);
同意Denis – 这取决于您的数据的存储方式。
我建议您使用TSQL HierarchyId数据类型实现层次结构 。 然后，您可以使用IsDescendent非常轻松地检查行是否是另一行的后代
DECLARE @searchId HierarchyId -- select your id SELECT @searchId = HierarchyId FROM Devices WHERE DeviceId = 1 SELECT * FROM Devices WHERE -- not children DeviceHierarchyId.IsDescendantOf(@seachId) = 0 -- not parents AND @searchId.IsDescendantOf(DeviceHierarchyId) = 0
编辑
要简要说明HierarchyId数据类型及其工作原理，请考虑每个项目在根节点下的层次结构中都有一个位置。 （如果您有多个自然根，则将每个根置于超根之下）。 每个hierarchyid列存储item的完整层次结构位置。 例如
Id | ParentId | HierarchyId 1 | null | \1 2 | 1 | \1\2 3 | 1 | \1\3 4 | 3 | \1\3\4
等等。 要检查项是否是另一个项的子项，只需检查hierarchyId是否包含在另一行的hierarchyId中 – 例如4是3的子项，因为整个\1\3包含在其hierarchyId \1\3\4 ，但是4不是2的子元素，因为\1\2不包含在hierarchyId中。
要查看itemA是否是itemB的父项，请检查itemB是否为itemA的子项。
最后，您实际上不需要进行任何比较。 TSQL HierarchyId类型包含许多方法，其中一个方法是我在上面突出显示的IsDescendantOf方法。 因此像hierarcyId1.IsDescendantOf(hierarchyId2)这样的用法会执行我在此处描述的那种检查。 hierarchyIds是二进制的，并且在数据库中非常快速地进行比较。
在处理数据库层次结构时，我会尽可能使用hierarchyId。
如果您有父母的索引，您可以尝试
select * from devices as child where exists(select null from devices as parent where parent.id = child.parent)
我的SQL并不完美，但这是我会使用的基本方法。
我的下意识算法解决方案是一种“标记 – 扫描”类型的解决方案（来自垃圾收集器理论）。
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Na.C3.AFve_mark-and-sweep
基本上，您遍历整个设备层次结构并标记“可追踪”的设备，这意味着它们可以通过另一个设备“使用递归”“到达”。
任何没有标记的东西，你都会“扫”出GC。 在您的情况下，任何未标记的是您正在寻找的集合。
这取决于您如何将树存储在数据库中。 有嵌套集模型 ，允许直接在数据库中进行此类查询。