如何在樹中查找重疊/冗餘節點

我有一個大層次結構中的節點列表。我如何有效地確定我的哪個節點是我列表中其他任何人的後代？如何在樹中查找重疊/冗餘節點

具體來說，這是一個ASP.NET控件的列表。我的代碼檢查每個節點及其後代，所以我試圖消除冗餘。

一個簡單的例子是這樣的樹：

  Parent 
     / \ 
    Gladis Arthur 
    / \ 
Jon  Sam

我的列表中包含{ Parent, Jon }。

我想寫一個算法，根據Parent節點包含Jon作爲後代的事實，將列表簡化爲Parent。

這裏是代碼：

public class Node 
    { 
     public Node(string name_, params Node[] children_) 
     { 
      this.children = children_; 
     } 
     public string name; 
     public Node[] children; 
    } 

    public class NodeAnalysis 
    { 
     public Node node; 
     public Node containingAncestor = null; 
    } 

    static void Main(string[] args) 
    { 
     Node jon = new Node("jon"); 
     Node parent = new Node("parent", 
      new Node("Gladis", 
       jon, 
       new Node("Sam")), 
      new Node("Arthur") 
     ); 

     List<NodeAnalysis> results = new List<NodeAnalysis>(); 
     results.Add(new NodeAnalysis{ node = parent }); 
     results.Add(new NodeAnalysis{ node = jon }); 

     foreach (NodeAnalysis item in results) 
     { 
      // ??? populate item.containingAncestor 
     } 
    }

我想不出一個高效的算法來做到這一點。我無法控制節點添加到列表的順序。似乎可以通過檢查樹和我已經在列表中標識的關係來優化它，因爲我正在遍歷它。

**編輯：.parent可在Node結構。使用.parent更容易發現祖先關係。

來源

2012-08-31 tenfour

您如何檢測節點A是否是B節點父？與'A.Controls.Contains（B）'？ – 2012-08-31 19:08:06

定義「高效」。它實際上需要多少效率？嘗試使用低效的天真方法，看看它是否真的太慢了。 – Servy

只是「合理高效」。以同樣的方式，你可以選擇通過氣泡排序的快速排序。例如，我可以說我必須選擇是否最好列舉我的「結果」列表或樹。我的spidy感覺說枚舉樹更有效率... – tenfour

我發現這篇文章，你可能會發現有用： http://www.eng.auburn.edu/files/acad_depts/csse/csse_technical_reports/CSSE01-09.pdf

，你也可能想檢查這篇文章： http://www.dmtcs.org/volumes/abstracts/pdfpapers/dm010116.pdf

我相信第一個直接回答你的問題。

希望它有幫助。

來源

2012-08-31 19:15:01

[只鏈接回答在SO]（http://meta.stackexchange.com/questions/8231/are-answers-that-just-contain-links-elsewhere-really-good-answers）。你應該確保你的答案是獨立的，下面的鏈接是*可選的*和其他信息。您應該總結，引用，解釋或擴展這些鏈接中的信息，或者將鏈接作爲評論發佈。 – Servy

這裏有一個辦法：

public static void RemoveDescendants(IList<Node> list) 
{ 
    for (int index = 0; index < list.Count; index++) 
     RemoveDescendants(list[index], list); 
} 
private static void RemoveDescendants(Node node, IList<Node> list) 
{ 
    foreach (var child in node.children) 
    { 
     list.Remove(child); 
     RemoveDescendants(child, list); 
    } 
}

來源

2012-08-31 19:29:22 phoog

@tenfour是的，沒錯。我已更正了代碼。 – phoog

如何在樹中查找重疊/冗餘節點

回答

相關問題