1

我有一个节点结构如下，这个节点有字符串数据和节点列表作为它的子节点。我想在这棵树中搜索一个数据我写了一个递归函数 FindNode(Node intree,string target)

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
}

target 是我要查找的字符串，而 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);
              }
         }
     }
}
4

4 回答 4

2

我建议您返回 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-20T06:50:22.807 回答
2

使用这个：

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-20T07:05:53.627 回答
2

鉴于树中可能有多个匹配项，您最好返回一个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-20T07:05:54.687 回答
0 
   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-20T06:58:49.240 回答