从父子节点集合中查找死节点

我有一个具有父子关系的自定义节点的集合。每个节点可以是复合类型（其中有其他子节点）或简单类型（叶级节点）从父子节点集合中查找死节点

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

enter image description here

基于以上的情况下，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; 
}

来源

2017-08-21 dev1

p1，p4，p6，L3，c1处于同一水平吗？ – displayName

你有什么试过？树加递归深度优先搜索？从简单的节点开始访问节点队列？什么？ –

看到我的图像附件。 p6，p4，L3是p1的孩子。 c1和p1与001 – dev1

您可以尝试类似的东西。

private List<NodeEntity> GetDeadNodes(List<NodeEntity> originalList) 
    { 
     var rest = originalList.ToList(); 

     // Remove simple nodes and their ascendants. 
     // The rest will be dead nodes. 
     var simpleNodes = originalList.Where(n => n.Type == NodeType.Simple); 
     foreach (var simpleNode in simpleNodes) 
     { 
      rest.Remove(simpleNode); 
      RemoveAscendants(rest, simpleNode); 
     } 

     return rest; 
    } 

    private void RemoveAscendants(List<NodeEntity> rest, NodeEntity node) 
    { 
     var parent = rest.SingleOrDefault(n => n.Code == node.ParentCode); 

     // We have reached the root node. 
     if (parent == null) 
     { 
      return; 
     } 
     rest.Remove(parent); 
     RemoveAscendants(rest, parent); 
    }

来源

2017-08-22 10:10:58 polkduran

（i）为什么使用递归来创建简单的'while'循环？ 'while node！= null {remove node; （ii）注释应该是“我们已经到达根节点或者父节点已经被移除” –

可以进行简单的从每个节点简单扫描了树，收集所有的节点，以保持（在伪代码）：

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

来源

2017-08-21 17:01:04

从父子节点集合中查找死节点

回答

相关问题