CODEWITHSUNDEEP
c#vb.netlinq
John Bustos
John Bustos

Reputation: 19574

LINQ to get deepest level nodes in a treeview

Suppose I have a WinForms Treeview that looks as follows:

Parent1
   Child1
      Sub-Child1
         DeepestNode1
         DeepestNode2
         DeepestNode3
      Sub-Child2
         DeepestNode4
         DeepestNode5
         DeepestNode6
   Child2
      Sub-Child3
      Sub-Child4
      Sub-Child5
      Sub-Child6
   Child3
      (no children)

I would like to create a function along the lines of:

Function GetDeepestChildren(MyNode as Treenode) as List(Of Treenode)

Where, if the results would look like:

GetDeepestChildren(Parent1) = {DeepestNode1, DeepestNode2, DeepestNode3, DeepestNode4, DeepestNode5, DeepestNode6}

GetDeepestChildren(Sub-Child1) = {DeepestNode1, DeepestNode2, DeepestNode3}

GetDeepestChildren(Child2) = {Sub-Child3, Sub-Child4, Sub-Child5, Sub-Child6}

GetDeepestChildren(Child3) = Empty list

... In other words, always go to the deepest level you can from the node given and return the children - Even if they're split between different parents (as was the case in Parent1).

I have created a function that will tell me how many levels deeper a node goes that looks like:

    Public Function GetDeepestChildNodeLevel(ByVal ParentNode As TreeNode) As Integer
        Dim subLevel = ParentNode.Nodes.Cast(Of TreeNode).Select(Function(subNode) GetDeepestChildNodeLevel(subNode))
        Return If(subLevel.Count = 0, 0, subLevel.Max() + 1)
    End Function

So I know from what level to get the children, what i'm looking for is a function that can do this - Somethign along the lines of:

Function GetDeepestChildren(MyNode as Treenode) as List(Of Treenode)
       Return All child nodes where level = GetDeepestChildNodeLevel(MyNode)
End function

I hope this makes sense - Thanks!

Upvotes: 5

Views: 7459

Answers (7)

John Bustos
John Bustos

Reputation: 19574

This is a VB.Net re-make I created of @dasblinkenlight's solution - It worked perfectly and I'm just putting it here in case anyone in the future needs the solution in VB.

    Public Function GetDeepestChildNodes(ByVal ParentNode As TreeNode) As List(Of TreeNode)
        Dim RetVal As New List(Of TreeNode)

        If ParentNode.Nodes.Count > 0 Then
            RetVal = (From nd As TreeNode In ParentNode.Nodes
                   Where nd.Nodes.Count = 0
                   Select nd).ToList

            For Each nd In ParentNode.Nodes
                RetVal.AddRange(GetDeepestChildNodes(nd))
            Next
        End If

        Return RetVal
    End Function

Thank you all again for your help!!!

Upvotes: 1

Hogan
Hogan

Reputation: 70538

Here is a version using XML -- the translation should be easy. I used linqPad which I recommend for this kind of stuff, you can run this and see it work directly in linkPad

WalkDeep(tree,getDeep(tree)) returns:

<DeepestNode1 /> 
<DeepestNode2 /> 
<DeepestNode3 /> 
<DeepestNode4 /> 
<DeepestNode5 /> 
<DeepestNode6 />

The C# code is nicer because you can use yield

VB Code

function getDeep( e as XElement) as integer
  if (e.HasElements)
    return 1 + e.Elements().Select(Function(c) getDeep(c)).Max()
  else
    return 1
  end if  
end function

function WalkDeep(root as XElement,find as integer,optional mylevel as integer = 1) as IEnumerable(of XElement)
  Dim result As New List(Of XElement)

  if find = mylevel 
    result.Add(root)
  else 
    if root.HasElements
      for each c as XElement in root.Elements()
        for each r as XElement in WalkDeep(c,find,mylevel+1)
            result.Add(r)
        next
      next  
    end if
  end if

  return result
end function

Sub Main
  dim tree as XElement = <Parent1>
     <Child1>
        <Sub-Child1>
           <DeepestNode1/>
           <DeepestNode2/>
           <DeepestNode3/>
        </Sub-Child1>   
        <Sub-Child2>
           <DeepestNode4/>
           <DeepestNode5/>
           <DeepestNode6/>
        </Sub-Child2>   
     </Child1>      
     <Child2>
        <Sub-Child3/>
        <Sub-Child4/>
        <Sub-Child5/>
        <Sub-Child6/>
     </Child2>   
     <Child3 />
  </Parent1>   

  WalkDeep(tree,getDeep(tree)).Select(function(x) x.Name.LocalName).Dump()
End Sub

C# Code:

int getDeep(XElement e)
{
  if (e.HasElements)
    return 1 + e.Elements().Select(c => getDeep(c)).Max();
  else
    return 1;
}

IEnumerable<XElement> WalkDeep(XElement root,int find, int mylevel=1)
{   
  if (find == mylevel) yield return root;

  if (root.HasElements)
  {
    foreach(XElement c in root.Elements())
    {
      foreach(XElement r in WalkDeep(c,find,mylevel+1))
        yield return r;

    }
  }

  yield break;
}

void Main()
{
  XElement tree = XElement.Parse (@"
  <Parent1>
     <Child1>
        <Sub-Child1>
           <DeepestNode1/>
           <DeepestNode2/>
           <DeepestNode3/>
        </Sub-Child1>   
        <Sub-Child2>
           <DeepestNode4/>
           <DeepestNode5/>
           <DeepestNode6/>
        </Sub-Child2>   
     </Child1>      
     <Child2>
        <Sub-Child3/>
        <Sub-Child4/>
        <Sub-Child5/>
        <Sub-Child6/>
     </Child2>   
     <Child3 />
  </Parent1>   
  ");

  WalkDeep(tree,getDeep(tree)).Dump();
}

Upvotes: 1

Fredou
Fredou

Reputation: 20120

it is not linq, since i think in this case it should not be done by linq sorry if it's not what you asked but this work. it is not fullproof but at least you wont get stackoverflow if you get a crazy tree

Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
    Dim test1 = GetDeepestChildren(TreeView1.Nodes(0))
    Dim test2 = GetDeepestChildren(TreeView1.Nodes(0).Nodes(0).Nodes(0))
    Dim test3 = GetDeepestChildren(TreeView1.Nodes(0).Nodes(1))
    Dim test4 = GetDeepestChildren(TreeView1.Nodes(0).Nodes(2))
End Sub

Private Function GetDeepestChildren(ByVal node As TreeNode) As List(Of TreeNode)
    Dim deepestList As New List(Of TreeNode)

    If node.Nodes.Count = 0 Then
        Return deepestList
    End If

    Dim nodes As New Stack(Of TreeNode)
    For Each n As TreeNode In node.Nodes
        nodes.Push(n)
    Next

    Dim deepest As Integer = 0
    Do Until nodes.Count = 0
        node = nodes.Pop
        If node.Nodes.Count = 0 Then
            If deepest < node.Level Then
                deepest = node.Level
                deepestList.Clear()
                deepestList.Add(node)
            ElseIf deepest = node.Level Then
                deepestList.Add(node)
            End If
        Else
            For Each n As TreeNode In node.Nodes
                nodes.Push(n)
            Next
        End If
    Loop

    Return deepestList
End Function

Upvotes: 0

JerKimball
JerKimball

Reputation: 16934

This is just a slight modification of @dasblinkenlight 's answer, so don't upvote this!

Just a matter of personal style, but I rather like the recursive call as such:

IEnumerable<TreeNode> WalkNodes(TreeNode root)
{   
    yield return root;
    var children = root.Nodes.Cast<TreeNode>();
    foreach (var child in children)
    {
        foreach(var subChild in WalkNodes(child))
        {
            yield return subChild;
        }
    }
}

And called via:

foreach (var node in treeView.Nodes.Cast<TreeNode>())
{
    var walkedFrom = WalkNodes(node);
    foreach (var subNode in walkedFrom)
    {
        Console.WriteLine(subNode.Text);
    }
}

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726839

In C# you can do it with yield return or with a recursive lambda. Here is an example of the second approach:

Func<TreeNode,IEnumerable<TreeNode>> getChildren = null;
getChildren = n => {
    if (n.Nodes.Count != 0) {
        var list = new List<TreeNode>(n.Nodes.Where(c => c.Nodes.Count == 0));
        foreach (var c in n.Nodes) {
            // Note the recursive call below:
            list.AddRange(getChildren(c));
        }
        return list;
    } else {
        return new TreeNode[0];
    }
};
var res = getChildren(myTree);

Upvotes: 4

gfyans
gfyans

Reputation: 1256

I'm not familiar with the TreeView control, but is the Level property of the TreeNode any good to you?

http://msdn.microsoft.com/en-us/library/system.windows.forms.treenode.level.aspx

If you know the deepest level, you could do this:

C#

private List<TreeNode> GetDeepestChildren(int level)
{
    return (from p in treeView1.Nodes.Cast<TreeNode>() where p.Level == level select p).ToList();
}

VB

Private Function GetDeepestChildren(level As Integer) As List(Of TreeNode)
    Return (From p In treeView1.Nodes.Cast(Of TreeNode)() Where p.Level = levelp).ToList()
End Function

Greg.

Upvotes: 0

Stokedout
Stokedout

Reputation: 11055

Tried a recursive function yet? Not sure in VB.Net but C# would look like

public List<TreeNode> GetDeepestChildren(Treenode MyNode)
{
   if (MyNode.Children.Count > 0)
        GetDeepestChildren(Treenode MyNode);
   else
        return MyNode.Children;
}

This hasnt been compiled or tested but the idea is there and should return the deepest children for any given node.

Upvotes: 0

Related Questions