Рекурсивное лямбда-выражение для обхода дерева в C #

Question

Может кто-нибудь показать мне, как реализовать рекурсивное лямбда-выражение для обхода древовидной структуры в C #.

Answer 1

Хорошо, я наконец нашел немного свободного времени.
Вот и мы:

class TreeNode
{
    public string Value { get; set;}
    public List<TreeNode> Nodes { get; set;}


    public TreeNode()
    {
        Nodes = new List<TreeNode>();
    }
}

Action<TreeNode> traverse = null;

traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};

var root = new TreeNode { Value = "Root" };
root.Nodes.Add(new TreeNode { Value = "ChildA"} );
root.Nodes[0].Nodes.Add(new TreeNode { Value = "ChildA1" });
root.Nodes[0].Nodes.Add(new TreeNode { Value = "ChildA2" });
root.Nodes.Add(new TreeNode { Value = "ChildB"} );
root.Nodes[1].Nodes.Add(new TreeNode { Value = "ChildB1" });
root.Nodes[1].Nodes.Add(new TreeNode { Value = "ChildB2" });

traverse(root);

Answer 2

Надлежащим решением, а на самом деле идиоматическим решением во многих функциональных языках программирования, было бы использование комбинатора с фиксированной точкой . В двух словах: комбинатор с фиксированной запятой отвечает на вопрос «как определить рекурсивную анонимную функцию?». Но решение настолько нетривиально, что для их объяснения написаны целые статьи.

Простая, прагматичная альтернатива состоит в том, чтобы «вернуться назад во времени» к выходкам C: объявление перед определением. Попробуйте следующее (функция «факториал»):

Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);

Работает как шарм.

Или, для обхода дерева предзаказа на объекте класса TreeNode, который соответствующим образом реализует IEnumerable<TreeNode> для обхода его потомков:

Action<TreeNode, Action<TreeNode>> preorderTraverse = null;
preorderTraverse = (node, action) => {
    action(node);
    foreach (var child in node) preorderTraverse(child, action);
};

Answer 3

Простая альтернатива - «вернуться в прошлое» к выходкам C и C ++: объявление перед определением. Попробуйте следующее:

Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);

Работает как шарм.

Да, это работает, с одной маленькой оговоркой. C # имеет изменяемые ссылки. Поэтому убедитесь, что вы случайно не делаете что-то подобное:

Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);

// Make a new reference to the factorial function
Func<int, int> myFact = fact;

// Use the new reference to calculate the factorial of 4
myFact(4); // returns 24

// Modify the old reference
fact = x => x;

// Again, use the new reference to calculate
myFact(4); // returns 12

Конечно, этот пример немного надуманный, но это может произойти при использовании изменяемых ссылок. Если вы используете комбинаторы из ссылок aku , это будет невозможно.

Answer 4

Предполагая мифический объект TreeItem, который содержит коллекцию Children для представления вашей иерархии.

    public void HandleTreeItems(Action<TreeItem> item, TreeItem parent)
    {
        if (parent.Children.Count > 0)
        {
            foreach (TreeItem ti in parent.Children)
            {
                HandleTreeItems(item, ti);
            }
        }

        item(parent);
    }

Теперь, чтобы вызвать его, передав лямбду, которая обрабатывает один элемент, напечатав его имя на консоли.

HandleTreeItems(item => { Console.WriteLine(item.Name); }, TreeItemRoot);