Populating the TreeNode Children
The last thing we'll cover is actually re-creating our exact structure by populating the Children collection of our TreeNode. As you've seen - in many situations you don't actually need to do this - but it's still a very useful thing to understand.
We can use a similar method that we used in dfTreeGetSubChildren (except with less restrictions) to fetch all rows of a tree (underneath a specified root node). It will then be up to our .NET class to actually create the appropriate structure of TreeNode objects.
CREATE PROCEDURE dfTreeGetTree ( @id INT ) AS
SELECT * FROM dfTree
WHERE lineage LIKE (SELECT lineage
FROM dfTree
WHERE id = @id) + '%'
ORDER BY lineage, name
As before, we're going to ensure that when we query the database, the rows are sorted in ascending order by the lineage column. This makes things much easier to deal with, as it will mean that
- The root of the tree we're fetching will be the first row in the resultset (because it will have the shortest
lineage value).
- The rows will be ordered such that if the depth column increases in value, then we'll be dealing with children of the last node we saw, and as such the depth will only have increased by one.
With this knowledge in hand, we can devise an algorithm using a stack in order to create the TreeNode's we need. Let's also suppose we have a tree and a corresponding resultset that looks something like the ones below - with any luck we'll then be able to relate the steps in the algorithm using this concrete example.
| id |
parentId |
name |
depth |
lineage |
| 1 |
NULL |
Root Node |
0 |
/1/ |
| 2 |
1 |
A (Child of Root) |
1 |
/1/2/ |
| 3 |
2 |
B (Child of A) |
2 |
/1/2/3/ |
| 4 |
3 |
C (Child of B) |
3 |
/1/2/3/4/ |
| 5 |
2 |
D (Child of Root) |
1 |
/1/5/ |
One of our requirements was that the first row in the result set is the root of the tree- so we can use our existing TreeNodeFromDataReader function to create our root TreeNode object - this will represent the row with id 1 in the table above. In addition, a variable currentNode is set to this node, a currentDepth variable initialized to zero, and a nodes variable initialized to an empty stack.
- Now, for each subsequent row in the resultset, we'll be adding the rows to the Children property of whatever
TreeNode object is at the top of the stack.
Obviously, on the first iteration we don't have anything in the stack, so we're going to need to consider some cases before trying to do this:
- if the depth of the row we're looking at has increased since the last iteration (which it certainly will have in the first iteration), we now know that we're dealing with a child of the current node. Therefore, we add
currentNode to the stack to save its current value (and so that the top of the stack contains the thing we want to add children to), and increment our currentDepth variable by one. - if the depth of the row has decreased then we know we've finished with the children of whatever was at the top of the stack. We now need to chuck items back off the stack so we can get back to the correct element for adding children to - and we simply chuck off the amount the depth has decreased by.
For example, suppose using the resultset listed above we have reached node D (row 5). At this point, currentDepth is 3, currentNode points to the row with id 4, and the nodes stack will contain the root node, node A, node B and node C. The difference between currentDepth and the depth of node D is 2 - so we pop 2 items off the stack - leaving us with node A at the top - which is exactly the node we want to add D to.
- We then set
currentNode to be a new TreeNode representing the node we've just read from the data reader - and add it to the children collection of whatever is at the top of the stack.
Once we've run out of items, the original TreeNode will contain all appropriate children - each with their own children populated. The code is below.
protected TreeNode PopulateTreeNodesFromReader(SqlDataReader dr)
{
//Stack<TreeNode> nodes = new Stack();
Stack nodes = new Stack();
// if we have no rows, then we don't have a tree!
if (!dr.Read())
return null;
TreeNode rootNode = TreeNodeFromDataReader(dr);
// we're currently at the root, so the
// depth is zero
int currentDepth = 0;
TreeNode currentNode = rootNode;
// now that we've got a "root" of our tree,
// start populating its children
while (dr.Read())
{
if ((int)dr["depth"] > currentDepth)
{
// assert dr["depth"] = currentDepth + 1
// assert currentCategory!=null
// we now have a child of the last category
nodes.Push(currentNode);
// set the current depth
currentDepth = (int)dr["depth"];
}
else if ((int)dr["depth"] < currentDepth)
{
// pop off appropriate number of items from stack
while ((int)dr["depth"] < currentDepth)
{
--currentDepth;
nodes.Pop();
}
}
currentNode = TreeNodeFromDataReader(dr);
((TreeNode)nodes.Peek()).Children.Add(currentNode);
}
nodes.Clear();
// return the children
return rootNode;
}
So, to get a TreeNode representing the a tree structure in the database, we can use this method:
public TreeNode GetTree(int uniqueID)
{
return ProcessTree("dfTreeGetTree",
new SqlParameter("id",uniqueID));
}
This TreeNode could then be passed to your business logic layer - for example - whilst totally abstracting the underlying representation with which you used to store the tree. In fact - we could modify all our existing calls to ProcessList (used by GetChildren, GetPath etc) and replace them with ProcessTree - changing the return type from ArrayList to TreeNode, you'll then get the expected structure as a TreeNode with populated Children rather than simply a list.
Conclusion
Hopefully by now you've got a much better idea of how you can deal with tree structures - and how you could create a web directory-like system in ASP.NET using the code provided here. I've also included a demonstration project available for download.
If you've got any questions - or think something in the article needs clarifying, then just drop me a line!