c# - 从父子节点集合中查找死节点

Question

我有一组具有父子关系的自定义节点。每个节点可以是复合类型(其中有其他子节点)或简单类型(叶级节点)

我想写一个函数来给我所有死节点的列表。 例如这里是节点集合

基于上述情况，p2、p3、p8、p9、p10、p6、c1 是死节点(因为在它们的层次结构中没有任何简单节点)

我需要一个函数作为

private List<NodeEntity> GetDeadNodes(List<NodeEntity> originalList) 

这是拥有原始列表的函数

private List<NodeEntity> GetOriginalList()
{
    var list = new List<NodeEntity>()
    {
        new NodeEntity() {Code = "P1", ParentCode = "001", Type = NodeType.Composite},
        new NodeEntity() {Code = "C1", ParentCode = "001", Type = NodeType.Composite},
        new NodeEntity() {Code = "P2", ParentCode = "P1", Type = NodeType.Composite},
        new NodeEntity() {Code = "P3", ParentCode = "P2", Type = NodeType.Composite},
        new NodeEntity() {Code = "P8", ParentCode = "P3", Type = NodeType.Composite},
        new NodeEntity() {Code = "P9", ParentCode = "P3", Type = NodeType.Composite},
        new NodeEntity() {Code = "P4", ParentCode = "P1", Type = NodeType.Composite},
        new NodeEntity() {Code = "L3", ParentCode = "P1",  Type = NodeType.Simple},
        new NodeEntity() {Code = "P6", ParentCode = "P1",  Type = NodeType.Composite},
        new NodeEntity() {Code = "P10", ParentCode = "P4",  Type = NodeType.Composite},
        new NodeEntity() {Code = "L2", ParentCode = "P4",  Type = NodeType.Simple},
        new NodeEntity() {Code = "P5", ParentCode = "P4",  Type = NodeType.Composite},
        new NodeEntity() {Code = "L1", ParentCode = "P5",  Type = NodeType.Simple}
    };
    return list;
}

Answer 1

您可以从每个简单节点向上执行简单扫描，以收集要保留的所有节点(伪代码):

put Simple nodes in a Set

while node in Set
  add node to a 'seen' list
  add parent to Set

dead nodes = all nodes except 'seen' nodes