C# 从上到下逐行递归遍历一棵树

Question

最近一位朋友提出了一个有趣的问题：假设你有一个 List<节点类型>树中的所有节点。您将如何从根节点逐行遍历树，以便找到具有特定值的第一个节点。假设每个节点都有 3 个属性：名称/位置、父节点的身份以及谁“拥有”该节点。问题是你想要找到你“拥有”的树中的最高节点，无论它在哪个分支上。我了解基本逻辑，以便找到您查找以父集作为第一个节点的所有节点的第一组子集。但是您将如何递归地搜索 List<> ？的节点来找到你拥有的最高节点？

Answer 1

public static Control FindChildControlByDepth(this Control Page, string ControlID, int depth)
        {
            if (depth > 10)
                throw new ArgumentException("Cannot search beyond a depth of 10", "depth"); 
            foreach (Control c in Page.Controls)
            {
                if (c.ID == ControlID)
                    return c;
                if (depth > 0)
                {
                    foreach (Control c1 in c.Controls)
                    {
                        if (c1.ID == ControlID)
                            return c1;
                        if (depth > 1)
                        {
                            foreach (Control c2 in c1.Controls)
                            {
                                if (c2.ID == ControlID)
                                    return c2;
                                if (depth > 2)
                                {
                                    foreach (Control c3 in c2.Controls)
                                    {
                                        if (c3.ID == ControlID)
                                            return c3;
                                        if (depth > 3)
                                        {
                                            foreach (Control c4 in c3.Controls)
                                            {
                                                if (c4.ID == ControlID)
                                                    return c4;
                                                if (depth > 4)
                                                {
                                                    foreach (Control c5 in c4.Controls)
                                                    {
                                                        if (c5.ID == ControlID)
                                                            return c5;
                                                        if (depth > 5)
                                                        {
                                                            foreach (Control c6 in c5.Controls)
                                                            {
                                                                if (c6.ID == ControlID)
                                                                    return c6;
                                                                if (depth > 6)
                                                                {
                                                                    foreach (Control c7 in c6.Controls)
                                                                    {
                                                                        if (c7.ID == ControlID)
                                                                            return c7;
                                                                        if (depth > 8)
                                                                        {
                                                                            foreach (Control c8 in c7.Controls)
                                                                            {
                                                                                if (c8.ID == ControlID)
                                                                                    return c8;
                                                                                if (depth > 9)
                                                                                {
                                                                                    foreach (Control c9 in c8.Controls)
                                                                                    {
                                                                                        if (c9.ID == ControlID)
                                                                                            return c9;
                                                                                    }
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }

                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }

                }
            }
            return null;
        }

Answer 2

更新：哈哈，哇，这是完全错误的，我刚刚意识到（因为它没有做你要求的事情）。没关系——无论如何，看起来你已经得到了正确的答案:)

---

我想我理解你的问题。如果我有什么问题请告诉我。

您有一个看起来像这样的 NodeType 类：

class NodeType
{
    public string Name { get; }
    public NodeType Parent { get; }
    public int OwnderId { get; }
}

首要任务是编写一个接受 NodeType 参数的函数，并给定一些可枚举的 集合NodeType 对象，以递归方式返回其所有后代：

IEnumerable<NodeType> GetNodeChildren(NodeType node, IEnumerable<NodeType> nodes)
{
    var children = nodes.Where(n => n.Parent == node);

    if (children.Any())
    {
        foreach (NodeType child in children)
        {
            yield return child;

            var grandchildren = GetNodeChildren(child);
            foreach (NodeType grandchild in grandchildren)
            {
                yield return grandchild;
            }
        }
    }
}

下一步：编写一个函数，该函数接受 NodeType 对象并查找具有指定 OwnerId 的最高后代>。这确实是一个非常简单的操作，所以我什至不会定义一个合适的函数；我将只使用 lambda：

Func<NodeType, int, NodeType> findHighestDescendent = (node, id) => {
    return GetNodeChildren(node).FirstOrDefault(child => child.OwnerId == id);
};

现在对于任何给定的 Id 值，找到最高匹配的 NodeType 是非常简单的：

int id = 10; // just for example

NodeType highestOwnedNode = nodes
    .Select(n => findHighestDescendent(n, id))
    .FirstOrDefault(n => (n != null));

Answer 3

算法：

Put the root node in a queue.

Repeat
    Take item from queue;
    Matching?  return Item
    Add all children to the queue
Until Queue is empty

Answer 4

您正在寻找广度优先搜索。通常使用队列来实现：

public Node FindFirstByBreadthFirst(this Node node, Predicate<Node> match)
{
    var queue = new Queue<Node>();
    queue.Enqueue(tree.RootNode);

    while (queue.Count > 0)
    {
        // Take the next node from the front of the queue
        var node = queue.Dequeue();

        // Process the node 'node'
        if (match(node))
            return node;

        // Add the node’s children to the back of the queue
        foreach (var child in node.Children)
            queue.Enqueue(child);
    }

    // None of the nodes matched the specified predicate.
    return null;
}