Nested Loop Question..Easy one.

You *must* use a loop? It would be much easier with recursion, which is the standard way of iterating trees. Check the wikipedia entry, it has pseudocode for inorder, preorder, and postorder traversal:

http://en.wikipedia.org/wiki/Tree_traversal

I attached a simple recursive pseduocode snippet that should get you started.

// print node and all children of that node
void PrintTree(Node n)
{
   foreach(child c of n) PrintTree(c);
   Console.WriteLine(n.ToString());
}

Select all Open in new window

Hi copyPasteGhost;

You can as you stated use recursion to solve this problem. The code sample below gives an example using a user defined class as elements of the tree and will print out the following.

 Parent1
      Child1
      Child2
           Grandchild1
 Parent2
      Child1
           Grandchild1
                Grandgrandchild1
 Parent3

Fernando

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }
 
    List<MyTreeStructure> Root = new List<MyTreeStructure>();
 
    private void button1_Click(object sender, EventArgs e)
    {
        // Create Tree structure
        //Parent 1
        MyTreeStructure parent1 = new MyTreeStructure("Parent1", "Parent", null);
        Root.Add(parent1);
        MyTreeStructure child1 = new MyTreeStructure("Child1", "Child", null);
        parent1.Descendent.Add(child1);
        MyTreeStructure child2 = new MyTreeStructure("Child2", "Child", null);
        parent1.Descendent.Add(child2);
        MyTreeStructure gChild1 = new MyTreeStructure("Grandchild1", "Grandchild", null);
        child2.Descendent.Add(gChild1);
        //Parent 2
        MyTreeStructure parent2 = new MyTreeStructure("Parent2", "Parent", null);
        Root.Add(parent2);
        MyTreeStructure child21 = new MyTreeStructure("Child1", "Child", null);
        parent2.Descendent.Add(child21);
        MyTreeStructure gchild22 = new MyTreeStructure("Grandchild1", "Grandchild", null);
        child21.Descendent.Add(gchild22);
        MyTreeStructure ggChild1 = new MyTreeStructure("Grandgrandchild1", "Grandgrandchild1", null);
        gchild22.Descendent.Add(ggChild1);
        //Parent 3
        MyTreeStructure parent3 = new MyTreeStructure("Parent3", "Parent", null);
        Root.Add(parent3);
    }
 
    private void button2_Click(object sender, EventArgs e)
    {
        // Iterate through the parents 
        foreach (MyTreeStructure node in Root)
        {
            // Print the parents sub tree
            PrintTree(node);
        }
    }
 
    int indent = 1;
    
    private void PrintTree(MyTreeStructure node)
    {
        Console.WriteLine("{0," + indent.ToString() + "}{1}", " ", node.Name);
        if (node.Descendent != null)
        {
            indent += 5;
            foreach (MyTreeStructure child in node.Descendent)
            {
                // This is a recursive call to itself
                PrintTree(child);
            }
            indent -= 5;
        }
    }
}
 
// The objects that make up the tree
public class MyTreeStructure
{
    public string Name;
    public string Type;
    public List<MyTreeStructure> Descendent = new List<MyTreeStructure>();
    public MyTreeStructure(string name, string type, MyTreeStructure descendent)
    {
        Name = name;
        Type = type;
        if(descendent != null)
            Descendent.Add(descendent);
    }
}

Select all Open in new window

Extending from Fippy's post, his method "PrintTree" takes a parameter which determines which node to print.  This assumes that both the root node and all subsequent child nodes are represented by or inherit from the same base object.

The PrintTree routine prints out whatever properties you are interested in and then calls itself on the passed node.  Initially, the root node is passed.  In doing so, the child nodes are iterated and then passed to a new run of the PrintTree routine.  If a child has its own children, the PrintTree routine is called again passing those and so on.

My code sample below differs slightly from Fippy's.  His prints the current node after iterating the children and mine prints the current node before iterating the children (this is usually what I want to happen, YMMV).

In my code, the following happens:

    PrintTree(tree)             --> prints "tree"
    PrintTree(child1)          --> prints "--child1"
    PrintTree(gchild1a)      --> prints "----gchild1a"
    PrintTree(ggchild1ai)   --> prints "------ggchild1ai"
    PrintTree(gchild1b)      --> prints "----gchild1b"
    PrintTree(child2)          --> prints "--child2"
    PrintTree(gchild2a)      --> prints "----gchild2a"    
    PrintTree(gchild2b)      --> prints "----gchild2b"

If ggchild1ai has a child, the PrintTree method would call itself again, passing that child.  This is the founding principal of recursion -- because the method calls itself with another parameter, exactly the same thing will happen as happened to all the other nodes.

J.

    public class Node 
    {
        private readonly List<Node> children = new List<Node>();
        private readonly string foo;
 
        public Node(string foo) { this.foo = foo; }
 
        public string Foo { get; set; }
        public ICollection<Node> Children { get { return children; } }
    }
 
    public static class Program
    {
        public static int Main(string[] args)
        {
            // create tree
            Node tree = new Node("tree");
            Node child1 = new Node("child1");
            Node child2 = new Node("child2");
            Node gchild1a = new Node("gchild1a");
            Node gchild1b = new Node("gchild1b");
            Node gchild2a = new Node("gchild2a");
            Node gchild2b = new Node("gchild2b");
            Node ggchild1ai = new Node("ggchild1ai");
 
            tree.Children.Add(child1);
            tree.Children.Add(child2);
            child1.Children.Add(gchild1a);
            child1.Children.Add(gchild1b);
            child2.Children.Add(gchild2a);
            child2.Children.Add(gchild2b);
            gchild1a.Children.Add(ggchild1ai);
 
            // start recursion
            PrintTree(tree);
        }
 
        private int printIndent = 0;
 
        private void PrintTree(Node n)
        {
            Console.Write('-', printIndent);
            Console.WriteLine(n.Foo);
            printIndent++;
            foreach (Node c in n.Children) PrintTree(c);
            printIndent--;
        }
    }

Select all Open in new window

>> foreach(Query database and get all items where the parent == root)
This leads to a more interesting problem.  Namely, can you afford the hit of going back to the database to get the children, inside the loop?

You will probably find that going to the database once for each child adds a significant overhead to your program.  It may be preferable to retrieve all of the tree'd data from the database and iterate through the rows.

Depending on your database of choice, there will be a different way of doing this (e.g. SQL Server 2005+ uses the WITH statement, Oracle uses the CONNECT BY statement).  

If you need it to be database agnostic, you need to refactor the database tree to use Joe Celko's nested set principal (http://www.intelligententerprise.com/001020/celko.jhtml).

J.

>> I've got what I want working... but it's not dynamic... You will see immediatly what I mean..
See all other posts...