c# - C# 从上到下逐行递归遍历树

Question

一个 friend 最近提出的一个有趣的问题:假设你有一个树中所有节点的List 。您将如何从根节点开始逐行向下遍历树，以便找到具有特定值的第一个节点。所以说每个节点都有 3 个属性:它的名称/位置、其父节点的身份以及谁“拥有”该节点。问题是你想找到你“拥有”的树中的最高节点，无论它在哪个分支上。我对基本逻辑的理解如此之多，以至于找到第一组子节点，您将查找所有节点，父节点设置为第一个节点。但是，您将如何递归搜索节点列表 <> 以找到您拥有的最高节点？

Answer 1

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

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;
}