Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Get next item in a tree

Tags:

c#

recursion

tree

Having a tree (logical in DB) with items in the form

  1. List item A
  2. List item B
    1. List item C
      1. List item D
  3. List Item E
  4. List Item F
    1. List Item G

and so on (nesting depth not limited), I want to get the next node down (or up), starting from an arbitrary node.

Let's say, List Item D is given I want to write a function GetNextNode() that would return List Item E.

My idea would be to do some recursion stuff, but maybe there is a more clever way to handle this?

My question:

How would you solve this?

EDIT 1:

The tree can be accessed with functions like:

  • GetParentNode()
  • GetChildrenNodes()
  • GetNextSiblingNode()
  • etc.

So it's similar to e.g. e Windows Forms TreeView.

like image 996
Uwe Keim Avatar asked Apr 14 '11 09:04

Uwe Keim


3 Answers

I've had to do this several times. From memory:

public Node GetBelowNode()
{
    if (GetChildrenNodes().count > 0)
        return GetChildrenNodes()[0];
    else
        if (GetNextSiblingNode() != null)
            return GetNextSiblingNode();
        else
        {
            Node curr = this;
            Node parent; 
            while (true)
            {
                parent = curr.GetParentNode();
                if (parent == null)
                    return null;
                else
                {
                    if (parent.GetNextSiblingNode() != null)
                        return parent.GetNextSiblingNode();
                    else
                        curr = parent;
                }
            }
        }
}
like image 64
Vincent Vancalbergh Avatar answered Sep 21 '22 00:09

Vincent Vancalbergh


You can handle this via recursion or... worst xD

I think there are only 3 basic cases:

private string getNext(TreeNode node)
{
    if (node.FirstNode != null)
    {
        return node.FirstNode.Name;
    }
    else
    {
        if (node.NextNode != null)
        {
            return node.NextNode.Name;
        }
        else if (node.Parent.NextNode != null)
        {
            return node.Parent.NextNode.Name;
        }
    }

    return "";
}

This doesn't works for every scenario. You should search the parent's next node too. Thanks to Vincent Vancalbergh for the comment ;-)

like image 27
zapico Avatar answered Sep 19 '22 00:09

zapico


public Party Next {
    get {
        if (this.children.Count > 0) return this.children[0];

        Party target = this;
        do {
            if (target.NextSibling != null) return target.NextSibling;
        } while ((target = target.Parent) != null);

        return null;
    }
}

public Party Previous {
    get {
        if (Parent != null && Parent.children.Count > 0 && this == Parent.children[0]) {
            return Parent;
        }

        Party target = this;

        do {
            if (target.PreviousSibling != null) { target = target.PreviousSibling; break; }
        } while ((target = target.Parent) != null);

        if (target != null) {
            while (target.children.Count > 0) {
                target = target.children[target.children.Count - 1];
            }
        }

        return target;
    }
}
like image 26
nonocast Avatar answered Sep 19 '22 00:09

nonocast