递归搜索嵌套列表。

Question

我已经阅读和搜索，但仍然无法找到相对简单的问题的答案。

我有一个类：

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

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

该列表使用一系列在此情况下并不重要的函数进行填充，但我正在寻找一种方法来搜索列表中所有子项，查找特定的“name”值，如果找到，则返回该列表。

以最简单的方式实现这个目标，并且对性能影响最小的是什么？谢谢-我已经为这一点困惑了几天...

- HeWhoWas

---

你想要返回一个列表还是一个项目？ - H H

它应该是一个项目。只应返回一个结果...现在我想想，也许它应该是一个列表。我总是可以检查其中有多少项。 - HeWhoWas

但是列出所有项目的搜索清单比只找第一个项目要昂贵得多。 - H H

那我也可以不需要它 :-) 如果代码能够正常工作，我总是可以修改它以考虑其他属性，如果名称不够唯一的话。 - HeWhoWas

Answer 1

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

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

    public static AccessibleTreeItem Find(AccessibleTreeItem 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;
    }
}

- Petar Ivanov

---

没错，但这是深度优先搜索。在递归之前检查所有子节点可能更有效率。 - H H

所以你的意思是DFS比BFS不那么高效...嗯，不 - 他们完全一样 - 都是通过仅访问每个节点一次来进行遍历。如果您不想进行递归，可以迭代地执行BFS和DFS。 - Petar Ivanov

我已经测试了代码，但不知何故它总是返回 null？我设置了断点并手动检查了 AccessibleTreeItem 节点 - 子对象在其中，但它嵌套在 4 层内。由于嵌套的层数没有限制，这是否会改变需要进行的操作方式？ - HeWhoWas

抱歉，你是对的，它确实可以运行。一个拼写错误让我犯了错 :-P ，用两个名字如此相似的变量，这是我的错。它完美地运行了，谢谢你的帮助 :-) - HeWhoWas

你能帮我找到并返回父级项目吗？提前谢谢 :-) - HeWhoWas