从上到下逐行遍历C#中的树

Question

最近朋友提出的有趣问题:想象一下,你有一棵树中所有节点的List <NodeType>.您将如何从行根节点向下遍历树,以便您找到具有特定值的第一个节点.所以说每个节点都有3个属性:它的名称/位置,它的父节点的身份,以及谁"拥有"节点.问题是你想要找到树中你拥有的最高节点,无论它在哪个分支上.我理解基本逻辑,以找到第一组子项,查找父项设置为第一个节点的所有节点.但是,您将如何递归搜索List <>节点以找到您拥有的最高节点？

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