从上到下逐行递归遍历C#中的树 [英] Recursively traversing a tree in C# from top down by row

问题描述

最近朋友提出的一个有趣的问题:想象一下你有一个 List<;NodeType > 树中所有节点.您将如何从根节点开始逐行遍历树，以便找到具有特定值的第一个节点.因此，假设每个节点都有 3 个属性:它的名称/位置、其父节点的身份以及谁拥有"该节点.问题是你想在树中找到你拥有"的最高节点，不管它在哪个分支上.我了解基本逻辑，以找到您查找的所有节点的第一组子节点，并将父节点集作为第一个节点.但是，您将如何递归搜索 List<> 节点以找到您拥有的最高节点?

Interesting problem posed by a friend recently: Imagine you've got a List< NodeType > of all nodes in a tree. How would you go about traversing down the tree from the root node, by row such that you find the first node with a specific value. So say that each node has 3 attributes: its name/location, the identity of its parent, and who "owns" the node. The problem is you want to find the highest node in the tree that you "own" no matter what branch its on. I understand the basic logic in so much as to find the first set of children you look for all nodes with a parent set as the first node. But how would you go about recursively search through a List<> of nodes to find the highest node you own?

推荐答案

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

You’re looking for breadth-first search. It is normally implemented using a queue:

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

这篇关于从上到下逐行递归遍历C#中的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！