Expression lambda récursive pour parcourir un arbre en C#

Question

Quelqu'un peut-il me montrer comment implémenter une expression lambda récursive pour parcourir une structure arborescente en C#.

Answer 1

Ok, j'ai enfin trouvé du temps libre.
On y va:

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

Une solution appropriée, et en fait la solution idiomatique dans de nombreux langages de programmation fonctionnels, serait l'utilisation d'un combinateur à virgule fixe.En un mot:un combinateur à virgule fixe répond à la question « comment définir une fonction anonyme comme étant récursive ?Mais la solution est si simple que des articles entiers sont écrits pour l’expliquer.

Une alternative simple et pragmatique consiste à « remonter le temps » jusqu’aux pitreries du C :déclaration avant la définition.Essayez ce qui suit (la fonction « factorielle » ):

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

Fonctionne à merveille.

Ou, pour une traversée d'arbre de pré-commande sur un objet de classe TreeNode qui met en œuvre IEnumerable<TreeNode> de manière appropriée pour s'occuper de ses enfants :

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

Answer 3

Une alternative simple consiste à « remonter le temps » jusqu’aux pitreries du C et du C++ :déclaration avant la définition.Essayez ce qui suit :

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

Fonctionne à merveille.

Oui, cela fonctionne, avec une petite mise en garde.C# a des références mutables.Assurez-vous donc de ne pas faire accidentellement quelque chose comme ceci :

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

Bien sûr, cet exemple est un peu artificiel, mais cela peut se produire lors de l'utilisation de références mutables.Si vous utilisez les combinateurs de akules liens, cela ne sera pas possible.

Answer 4

En supposant un objet mythique TreeItem, qui contient une collection Children pour représenter votre hiérarchie.

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

        item(parent);
    }

Maintenant, appelez-le, en passant le lambda qui gère un élément, en imprimant son nom sur la console.

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