views:

912

answers:

4

I have a large result set assembled in a parent/child relationship. I need to walk the tree and display the results to the user.

I've done this before using recursion, but because my result set may be large, I want to avoid the possibility of receiving a StackOverflowException.

I found the following example on MSDN which uses a Stack. The problem I'm having is because a stack is last-in first-out, my data doesn't appear properly. I'd like it to look like the following:


LeveL 1
Level 1.1
Level 1.1.1 
Level 1.1.2 
Level 1.2 
Level 1.2.1 
Level 1.2.2

But it looks like:


LeveL 1
Level 1.2 
Level 1.2.2 
Level 1.2.1 
Level 1.1 
Level 1.1.2 
Level 1.1.1 

Any ideas?

Here is an example of my code. Assuming the DataTable dt has the following columns: ID, ParentID, and Text

    private struct Item
    {
        public string Text;
        public int ID;
        public int ParentID;
    }

    private void BuildView()
    {
        Stack<Item> itemTree = new Stack<Item>(40);

        //Get All Parent Nodes
        DataView dv = new DataView(dt);
        dv.RowFilter = "ParentID = 0";

        //Add the parent nodes to the stack
        foreach (DataRowView drv in dv)
        {
            Item item = new Item();
            item.Text = drv["Text"].ToString();
            item.ID = drv["ID"].ToString();
            item.ParentID = drv["ParentID"].ToString();
            itemTree.Push(item);
        }

        //Go through the stack one node at a time
        while (itemTree.Count > 0)
        {
            Item currentItem = itemTree.Pop();
            Debug.WriteLine(currentItem.Text);

            //Get children of current node
            dv.RowFilter = String.Format("ParentID = {0}", currentItem.ID);
            if (dv.Count > 0)
            {
                //Add child nodes to the stack
                foreach (DataRowView drvChild in dv)
                {
                    Item item = new Item();
                    item.Text = drvChild["Text"].ToString();
                    item.ID = drvChild["ID"].ToString();
                    item.ParentID = drvChild["ParentID"].ToString();
                    itemTree.Push(item);
                }
            }
        }

    }
+3  A: 

In the current algorithm you are going for the right child first.

Make it left child first. Thats all.

For example, in your code there may be something like:

node = node.rightChild()

Change it to

node = node.leftChild()

This is the general solution for this kind of issues.

Since the MSDN implementation does not expose this kind of code, I cannot comment on that.

Niyaz
I think there's a typo there... both lines of code are identical.
Zach Scrivena
How would I do this, using my example code above?
+1  A: 

Push your items onto the stack in the reverse order, i.e. 2 before 1.

Example:

// suppose I want to push children[] onto the stack

for (int i = children.Length - 1; i >= 0; i--)
{
   stack.Push(children[i]);
}

To do this in your code, try the following for-each statement:

foreach (DataRowView drvChild in dv.Reverse())
Zach Scrivena
I don't know whether it will work this way. Can you explain?
Niyaz
@Niyaz: Updated my answer with an example.
Zach Scrivena
Yeah. But can you explain how this will give the required answer? I cannot understand.
Niyaz
@Niyaz: I think this works for the OP's particular way of using the stack. Guess it depends on how you are using the stack for the traversal.
Zach Scrivena
Is there a better way to do this?
@djdouma: I think your way is optimal for the desired output.
Zach Scrivena
A: 

If it's simply the ordering that is providing concern, change from using a Stack to using a Queue. They're the same for practical purposes with the difference that a Queue is first in first out.

Jacob Proffitt
Using a queue changes it to a breadth-first traversal, instead of the desired depth-first traversal.
Zach Scrivena
Zach, Not necessarily. It becomes breadth first only if you do breadth first.But usually we use queue in breadth first searches.
Niyaz
If I use a queue, the data appears like this.Level 1 Level 1.1 Level 1.2 Level 1.1.1 Level 1.1.2 Level 1.2.1 Level 1.2.2
A: 

By changing my iteration of the child nodes in reverse order, they display as desired


                    //Add child nodes to the stack
                    for (int i = dv.Count - 1; i >= 0; i--)
                    {
                        DataRowView drvChild = dv[i];
                        Item item = new Item();
                        item.Text = drvChild["Text"].ToString();
                        item.ID = drvChild["ID"].ToString();
                        item.ParentID = drvChild["ParentID"].ToString();
                        itemTree.Push(item);
                    }
Typo? Index i doesn't seem to be used.
Zach Scrivena
Oops - fixed now.