copyPasteGhost
asked on
Nested Loop Question..Easy one.
Hello,
This might be very simple, but I seem to be missing something..
I have this type of tree structure:
Root
Parent
child
child
grandchild
Parent
child
grandchild
grandgrandchild
Parent
Basically n parents and n deep.
I'm trying to write a loop that will print out this structure. So far I have this.
foreach(Query database and get all items where the parent == root) {
print out the parent item.
check if it has children
if(has children) {
print out the child
foreach(children of the child){
print them out.
HERE IS THE PROBLEM HOW CAN I GO "N" DEEP WITHOUT HAVING "N" NESTED LOOPS?
}
}
}
Thanks.
This might be very simple, but I seem to be missing something..
I have this type of tree structure:
Root
Parent
child
child
grandchild
Parent
child
grandchild
grandgrandchild
Parent
Basically n parents and n deep.
I'm trying to write a loop that will print out this structure. So far I have this.
foreach(Query database and get all items where the parent == root) {
print out the parent item.
check if it has children
if(has children) {
print out the child
foreach(children of the child){
print them out.
HERE IS THE PROBLEM HOW CAN I GO "N" DEEP WITHOUT HAVING "N" NESTED LOOPS?
}
}
}
Thanks.
ASKER
ok recursion was what I meant.
if you look at my sample you will see that's what I'm doing..
for your example. what if "child c" has children? then what?
if you look at my sample you will see that's what I'm doing..
for your example. what if "child c" has children? then what?
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
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);
}
}
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.
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--;
}
}
ASKER
Perhaps my question was not structured right..
I've got what I want working... but it's not dynamic... You will see immediatly what I mean..
Check out the sample code... this is what I'm looking for...
I've got what I want working... but it's not dynamic... You will see immediatly what I mean..
Check out the sample code... this is what I'm looking for...
void FillMainCats(TreeNode node) {
foreach (Category oCategory in Category.GetAllRootLevelCategories()) {
string sCatName = (from c in oCategory.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault();
if (sCatName != null) {
TreeNode oParentNode = new TreeNode(sCatName, oCategory.Code);
oParentNode.SelectAction = TreeNodeSelectAction.Expand;
List<Category> oChildCats = Category.GetAllChildCats(oCategory.id);
while (oChildCats.Count != 0) {
foreach (Category oChildCat in oChildCats) {
TreeNode oChildNode = new TreeNode((from c in oChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oChildCat.Code);
oChildNode.SelectAction = TreeNodeSelectAction.Expand;
oParentNode.ChildNodes.Add(oChildNode);
oChildCats = Category.GetAllChildCats(oChildCat.id);
while (oChildCats.Count != 0) {
foreach (Category oGrandChildCat in oChildCats) {
TreeNode oGrandChildNode = new TreeNode((from c in oGrandChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oGrandChildCat.Code);
oGrandChildNode.SelectAction = TreeNodeSelectAction.Expand;
oChildNode.ChildNodes.Add(oGrandChildNode);
oChildCats = Category.GetAllChildCats(oGrandChildCat.id);
while (oChildCats.Count != 0) {
foreach (Category oGGChildCat in oChildCats) {
TreeNode oGGChildNode = new TreeNode((from c in oGGChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oGrandChildCat.Code);
oGGChildNode.SelectAction = TreeNodeSelectAction.Expand;
oGrandChildNode.ChildNodes.Add(oGGChildNode);
oChildCats = Category.GetAllChildCats(oGGChildCat.id);
while (oChildCats.Count != 0) {
foreach (Category oGGGChildCat in oChildCats) {
TreeNode oGGGChildNode = new TreeNode((from c in oGGGChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oGrandChildCat.Code);
oGGGChildNode.SelectAction = TreeNodeSelectAction.Expand;
oGGChildNode.ChildNodes.Add(oGGGChildNode);
oChildCats = Category.GetAllChildCats(oGGGChildCat.id);
while (oChildCats.Count != 0) {
foreach (Category oGGGGChildCat in oChildCats) {
TreeNode oGGGGChildNode = new TreeNode((from c in oGGGGChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oGrandChildCat.Code);
oGGGGChildNode.SelectAction = TreeNodeSelectAction.Expand;
oGGGChildNode.ChildNodes.Add(oGGGGChildNode);
oChildCats = Category.GetAllChildCats(oGGGGChildCat.id);
}
}
}
}
}
}
}
}
}
}
node.ChildNodes.Add(oParentNode);
}
}
}
>> 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.
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...
See all other posts...
ASKER
The category object is cached locally. That will not be a issue. The problem I'm running into is that if I have a 10 level deep category according to the code I just posted I will need to have 10 nested loops.
There must be a better way to do it. I just can't seem to figure it out right now...thus the question :)
There must be a better way to do it. I just can't seem to figure it out right now...thus the question :)
ASKER
the building of the tree is static in all the examples. I need something dynamic.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
exactly! thanks.
http://en.wikipedia.org/wiki/Tree_traversal
I attached a simple recursive pseduocode snippet that should get you started.
Open in new window