如何在節點樹中找到節點數據？

我有一個Node結構如下，這個節點有stringdata和節點列表，因爲它是子節點。我想搜索的數據在這個樹我寫了一個遞歸函數FindNode（節點intree，目標字符串）如何在節點樹中找到節點數據？

public class Node 
{ 
    public string Data; 
    public List<Node> Children = new List<Node>(); 
    //some code 
    public Node(string r) 
    { 
     this.Data = r; 
    } 

    public string getData() 
    { 
      return this.Data; 
    } 

    //some code 
    public List<Node> getchildren() 
    { 
     return this.Children; 
    } 
     //some code 
}

目標就是我想要找的字符串和intree是樹的開頭（ROOT ） while循環後我有問題，然後應該返回什麼？如果我錯了，我該怎麼寫呢？

public Node FindNode(Node intree,string target) 
{ 
    if(intree.getData()==target) 
      return intree; 
    else 
    { 
     while(intree.getchildren()!=null) 
     { 
      foreach(Node n in intree.getchildren()) 
       { 
        FindNode(n,target); 
       } 
     } 
    } 
}

來源

2012-04-20 Negin Nicki

這裏有什麼不起作用？這已經很好了。 – Tigran 2012-04-20 06:47:43

雖然我有錯誤，但並不是所有的路徑都返回一個節點 – 2012-04-20 06:49:25

@NeginNicki你的Children屬性有一個初始值設定項，因此它永遠不會爲null（除非你在某些未發佈的代碼中將它設置爲null）。結果你打開了一個無限循環。 – 2012-04-20 07:03:58

使用這一個：

public Node FindNode(Node intree,string target) 
{ 
    if(intree.getData()==target) 
      return intree; 
    else 
    { 

       foreach(Node n in intree.getchildren()) 
       {     
        Node node = FindNode(n,target) ; //CHECK FOR RETURN 

        if(node != null) 
         return node;    

       } 

    } 

    return null; 
}

不同的是，我查FindNode方法的回報，如果不是null，返回結果。

請注意，如果樹中有重複節點（節點具有相同的字符串），它將返回第一個出現。

來源

2012-04-20 07:05:53 Tigran

如果intree.getchildren爲null，會發生什麼？它是否正確？這不會產生異常嗎？ – 2012-04-20 07:14:34

@NeginNicki：它不能爲null，通過我在代碼中看到的類定義。 – Tigran 2012-04-20 07:15:04

假設通過intree後會成爲一片葉子它會做什麼？ – 2012-04-20 07:16:38

我會建議你返回null，適用檢查要調用此方法是，如果返回null，則意味着沒有發現節點。代碼如下

public static Node FindNode(Node intree, string target) 
    { 
     if (intree.getData() == target) 
      return intree; 

     foreach (Node node in intree.getchildren()) 
     { 
      Node toReturn = FindNode(node, target); 
      if (toReturn != null) return toReturn; 
     } 

     return null; 
    }

來源

2012-04-20 06:50:22 Waqar

爲什麼this.FindNode，如果你使用this.FindNode然後我認爲只是輸入目標是足夠好 – 2012-04-20 06:54:00

@NeginNicki是你可以刪除這個。你也可以在這種情況下使這個方法是靜態的 – Waqar 2012-04-20 06:59:07

@NeginNicki Tigran的回答和我的答案有什麼區別。 – Waqar 2012-04-20 07:15:55

public Node FindNodeRecursively(Node parentNode, string keyword) 
     { 
      if(parentNode.getData() == keyword) 
      { 
       return parentNode; 
      } 
      else 
      { 
       if(parentNode.Children != null) 
       { 
        foreach(var node in parentNode.Children) 
        { 
         var temp = FindNodeRecursively(node, keyword); 
         if(temp != null) 
          return temp; 
        } 
       } 
       return null; 
      } 
     }

來源

2012-04-20 06:58:49 daryal

是的，如果陳述比我的陳述更好謝謝 – 2012-04-20 07:01:21

你能否告訴我，如果在你的foreach的原因？你爲什麼不簡單地調用Find？ – 2012-04-20 07:02:29

您需要在某個時刻從方法中實際返回。調用Find（）方法最終返回的方法不會導致調用方法返回該查找的結果。 – 2012-04-20 07:05:31

鑑於樹中可能存在多個匹配項，您最好返回IEnumerable<Node>。你也不需要把那些奇怪的get方法放在那裏。最後，你是說只搜索葉節點還是你想搜索所有節點（else語句）？

public IEnumerable<Node> FindNode(Node intree,string target) 
{ 
    if(intree.Data ==target) 
     yield return intree; 

    foreach (var node in intree.Children.SelectMany(c => FindNode(c, target)) 
     yield return node; 
}

如果您想要第一個匹配節點，只需調用First()就可以得到結果。如果你想確保只有一個，請致電Single()。

來源

2012-04-20 07:05:54

我想搜索整個樹，但如果在搜索之間它找到了第一個節點然後完成它，所以它有更好的速度。我只是需要一個匹配。不多匹配 – 2012-04-20 07:10:03

此代碼只會達到1級 – Sadaf 2012-04-20 07:14:49

但這就是'.First（）'會爲你做的。 LINQ很懶，它會搜索直到找到一個然後停止。但是這是一個更好的API，因爲如果你以後決定你需要一個API來找到所有的API，或者你需要確保只有1個API，那麼它就可以處理它。 – 2012-04-20 07:15:35

如何在節點樹中找到節點數據？

回答

相關問題