Рекурсивный обход дерева в C # сверху вниз по строке

Question

Интересная проблема, которую недавно поставил друг: представьте, что у вас есть список всех узлов в дереве.Как бы вы пошли по обходу дерева от корневого узла, построчно, чтобы найти первый узел с определенным значением.Итак, скажем, что у каждого узла есть 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;
}

Answer 2

Алгоритм:

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 3

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 4

Обновление : Хаха, вау, это совершенно неправильно, я только что понял (поскольку в этом не делает то, что вы просили). Не бери в голову - похоже, ты уже получил правильный ответ:)

---

Мне кажется, я понимаю вашу проблему. Дайте мне знать, если я что-то не так делаю.

У вас есть 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. Это действительно довольно простая операция, поэтому я даже не буду определять правильную функцию; Я просто использую лямбду:

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