Expressão lambda recursiva para percorrer uma árvore em C#

Question

Alguém pode me mostrar como implementar uma expressão lambda recursiva para percorrer uma estrutura de árvore em C#.

Answer 1

Ok, finalmente encontrei algum tempo livre.
Aqui vamos nós:

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

Uma solução adequada, e na verdade a solução idiomática em muitas linguagens de programação funcional, seria o uso de um combinador de ponto fixo.Resumindo:um combinador de ponto fixo responde à pergunta “como defino uma função anônima como recursiva?”.Mas a solução é tão nada trivial que artigos inteiros são escritos para explicá-la.

Uma alternativa simples e pragmática é “voltar no tempo” às palhaçadas de C:declaração antes da definição.Tente o seguinte (a função “fatorial”):

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

Funciona como um encanto.

Ou, para uma travessia de árvore de pré-ordem em um objeto de classe TreeNode que implementa IEnumerable<TreeNode> apropriadamente para repassar seus filhos:

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

Answer 3

Uma alternativa simples é “voltar no tempo” às palhaçadas de C e C++:declaração antes da definição.Experimente o seguinte:

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

Funciona como um encanto.

Sim, isso funciona, com uma pequena ressalva.C# possui referências mutáveis.Portanto, certifique-se de não fazer algo assim acidentalmente:

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

Claro, este exemplo é um pouco artificial, mas isso pode acontecer ao usar referências mutáveis.Se você usar os combinadores de aku's, isso não será possível.

Answer 4

Assumindo um objeto mítico TreeItem, que contém uma coleção Children para representar sua hierarquia.

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

        item(parent);
    }

Agora, para chamá-lo, passando o lambda que trata de um item, imprimindo seu nome no console.

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