Recursive non-binar, non-sorted tree search using C # lambas

Question

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


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

1) How would you write a recursive lambda expression to return a TreeNode with a specific value (or null if not found) if the values ​​are unique? Of course # 1 can be answered using # 2, but I think there might be a more efficient way if you know that there are no duplicates.

2) Assuming the values ​​are not unique and now return a list of matches instead?

Answer 1

Change . The corrected code, I really collected and tested both code fragments, but I had to be inserted in the version before I fixed them in VS. Sorry.

Subversion , , , , , "", .

---

:

1:

Func<TreeNode, String, TreeNode> findNode = null; // satisfy recursion re-use
findNode = (n, value) =>
{
    if (n == null) return n;
    if (n.Value == value) return n;
    foreach (var subNode in n.Nodes)
    {
        TreeNode foundNode = findNode(subNode, value);
        if (foundNode != null) return foundNode;
    }
    return null;
};

, , , , . , , .

2:

Func<TreeNode, String, List<TreeNode>> findNodes = null;
findNodes = (n, value) =>
{
    var result = new List<TreeNode>();
    if (n == null) return result;
    if (n.Value == value) result.Add(n);
    foreach (var subNode in n.Nodes)
    {
        result.AddRange(findNodes(subNode, value));
    }
    return result;
};

, .

Answer 2

..

public class Node<T> where T:IComparable
{
    public T Value { get; set; }

    public IList<Node<T>> Children { get; set; }

    public override string ToString()
    {
        return Value.ToString();
    }

    public static Func<T, Node<T>, Node<T>> GetFindFirstFunc()
    {
        Func<T, Node<T>,Node<T>> func = null;
        func = (value,currentNode) =>
            {
                if (currentNode.Value.CompareTo(value) == 0)
                {
                    return currentNode;
                }
                if (currentNode.Children != null)
                {
                    foreach (var child in currentNode.Children)
                    {                            
                        var result = func(value, child);
                        if (result != null)
                        {
                            //found the first match, pass that out as the return value as the call stack unwinds
                            return result;
                        }
                    }
                }
                return null;
            };
        return func;
    }

    public static Func<T, Node<T>, IEnumerable<Node<T>>> GetFindAllFunc()
    {
        Func<T, Node<T>, IEnumerable<Node<T>>> func = null;
        List<Node<T>> matches = new List<Node<T>>();
        func = (value, currentNode) =>
        {
            //capture the matches  List<Node<T>> in a closure so that we don't re-create it recursively every time.
            if (currentNode.Value.CompareTo(value) == 0)
            {
                matches.Add(currentNode);
            }
            if (currentNode.Children != null)
            {
                //process all nodes
                foreach (var child in currentNode.Children)
                {
                    func(value, child);
                }
            }
            return matches;
        };
        return func;
    }       
}

:

static void Main(string[] args)
    {
        Node<int> rootNode = new Node<int>
        {
            Value = 1,
            Children = new List<Node<int>>
             {
                 new Node<int>
                 {  Value = 2,
                                 Children = new List<Node<int>>
                                 {
                                     new Node<int>{ Value = 7},
                                     new Node<int>{ Value = 4}                                                            
                                 }
                 },
                 new Node<int>
                 {  Value = 5,
                                 Children = new List<Node<int>>
                                 {
                                     new Node<int>{ Value = 6},
                                     new Node<int>{ Value = 7}                                                            
                                 }
                 }
             }
        };


        Func<int, Node<int>, Node<int>> findFirst = Node<int>.GetFindFirstFunc();
        var firstValue = findFirst(7, rootNode);           



        Func<int, Node<int>, IEnumerable<Node<int>>> findAll = Node<int>.GetFindAllFunc();
        var allvalues = findAll(7, rootNode);           
    }