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

问题描述

最近一位朋友提出的有趣问题:假设您有一个List<树中所有节点的NodeType>.您将如何逐行从根节点向下遍历树，以便找到具有特定值的第一个节点.可以这么说，每个节点具有3个属性:其名称/位置，其父节点的身份以及拥有"该节点的人.问题是，无论分支上的哪个分支，您都希望在拥有"的树中找到最高的节点.我了解基本逻辑的目的在于找到要查找以父集为第一个节点的所有节点的第一个子集.但是，您将如何递归地搜索节点列表以找到您拥有的最高节点呢?

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屋！