c# - 查找不是父/祖 parent /等或子/孙/等的所有链接对象的算法

Question

我有一个名为 Device 的对象。 Device 可以有一个父 Device。一个 Device 也可以有 n 个子 Devices。

我有一个下拉列表，其中显示了所有可选择的设备。我可以很容易地获取数据库中的所有 Devices - db.Devices。

层次结构可以无限深。

我需要获取所有不在树中给定Device之上或之下的Devices。本质上，我要求的是与给定的 Device 无关的 Devices(既不是 parent /祖 parent /曾祖 parent /等，也不是 child /孙/曾孙/等)。我还需要从列表中排除给定的 Device。

最好的方法是什么？我应该使用递归吗？

(我将 C# 和 Entity Framework 与 SQL Server 数据库结合使用，因此我可以使用 Linq To SQL 或使用模型本身。)

Answer 1

我的方法是首先获取设备 D 的所有兄弟:

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

任何 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);