從父子節點集合中查找死節點

我有一個具有父子關係的自定義節點的集合。每個節點可以是複合類型（其中有其他子節點）或簡單類型（葉級節點）從父子節點集合中查找死節點

我想編寫一個函數，該函數將給出所有死點節點的列表。例如這裏是節點集合

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

從父子節點集合中查找死節點

回答

相關問題