算法找到所有链接的对象不是父母/祖父母/等或子女/孙子的/ etc [英] Algorithm to find all linked objects that aren't a parent/grandparent/etc or a child/grandchild/etc

问题描述

我有一个名为对象设备。 A 设备可以有一个父 设备。 A 设备也可以有 N 孩子设备。

I have an object called Device. A Device can have one parent Device. A Device can also have n child Devices.

我有一个下拉列表，显示所有可选择的设备。我可以得到所有的设备在数据库中很容易 - db.Devices

I have a drop down list that shows all the selectable Devices. I can get all the Devices in the database quite easily - db.Devices.

的层次可以是无限级深。

The hierarchy can be infinite levels deep.

我需要获得所有设备是不高于或给定设备在下方树。基本上我所要求的设备无关的给定设备（既不是父母/祖父母/外祖父母很大的/ etc或一个孩子/孙子/孙子大的/ etc）。我还需要排除给定的设备从列表中。

I need to get all Devices that aren't above or below a given Device in the tree. Essentially I'm asking for Devices unrelated to a given Device (neither a parent/grandparent/great grandparent/etc or a child/grandchild/great grandchild/etc). I also need to exclude the given Device from the list.

什么是做到这一点的最好方法是什么？我应该使用递归？

What is the best way to do this? Should I use recursion?

（我使用C＃和实体框架与SQL Server数据库，这样我就可以使用的LINQ to SQL或使用模式本身。）

(I am using C# and Entity Framework with an SQL Server database, so I can use Linq To SQL or use the model itself.)

推荐答案

我的做法是首先把所有的设备 D 的兄弟姐妹：

My approach would be first to get all of the siblings of the device D:

P = parent of the device
sibs = {all children of P that are not D}

任何 D的同胞的任何后裔无关 D 。持续上涨的家谱：

Any descendants of any d in sibs is unrelated to D. Keep going up the family tree:

G = grandparent of the device
sibs = sibs union {all children of G that are not P}

继续这样，集上海生命科学研究院及其所有的后代被设定你后。

Continuing this way, the set sibs and all their descendants is the set you're after.

在伪code：

D = device;
siblings = {};
while (D has parent) {
    P = parent(D);
    siblings = siblings union (children(P) \ D);
    D = P;
}
return descendants(siblings);

这篇关于算法找到所有链接的对象不是父母/祖父母/等或子女/孙子的/ etc的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！