递归搜索嵌套列表并获取父级

Question

我有一个类：

public class Node
{
    public string name;
    public List<Node> children;

    public Node()
    {
        children = new List<Node>();
    }
}

我已经成功地递归搜索并获取了特定的项目。如何获取其父级？

public static Node Find(Node node, string name)
{

    if (node == null)
        return null;

    if (node.name == name)
        return node;

    foreach (var child in node.children)
    {
        var found = Find(child, name);
        if (found != null)
            return found;
    }

    return null;
}

- Ramzy Abourafeh

---

你的节点是否有任何与父级属性相关的内容？ - nrsharma

Answer 1

如果您不想添加父节点以保持结构简单，您可以更改返回类型并同时返回节点和父节点。

class SearchResult {
 public Node Found;
 public Node Parent;
}

public static SearchResult Find(Node node, string name)
{

    if (node == null)
        return null;

    if (node.name == name)
        return new SearchResult { Found =  node, Parent = null};

    foreach (var child in node.children)
    {
        var found = Find(child, name);
        if (found != null)
                    return new SearchResult { Found =  found, Parent = node};
    }

    return null;
}

- Stefano Altieri

Answer 2

简短回答：你需要跟踪它。

例如：List<Node> children 可以是一些自定义集合，比如

public class Children : List<Node> {

    public Node Parent {get;set;}; 
    public Children(Node pr) {
        Parent = pr;
    }
}

所以：

  .....
  public Node()
  {
    children = new Children (this);
  }
  ...

如果我正确理解你的逻辑：

    //node IS a parent of found node.
    foreach (var child in node.children)
    {
        var found = Find(child, name);
        if (found != null)
            return found;
    }

- Tigran

Answer 3

最好的方法是在您的结构中保留对父级的引用。

如果您不想这样做，那么可以稍微修改Find函数。像这样（注意，它是在浏览器中编写的）。

public static Tuple<Node, Node> Find(Node node, string name)
{
   return Find(node, name, null);
}

public static Tuple<Node, Node> Find(Node node, string name, Node parent)
{
    if (node == null)
        return null;

    if (node.name == name)
        return new Tuple<Node, Node>(node, parent);

    foreach (var child in node.children)
    {
        var found = Find(child, name, node);
        if (found != null)
            return found;
    }

    return null;
}

- Marius Bancila