Re: Tree Traversal / Storage Algorithm

2005-02-15 Thread Keith Gaughan
Jeff Chastain wrote:
  
 I am trying to remember my old CS days, but the memory is going.  I need to
 simulate a tree with n-nodes per branch ... i.e. a nested folder structure
 with 0 to n objects in each folder.  The folders can be nested infinitely
 deep.  So, what is the algorithm for traversing this type of tree?
  
 Most everything I have found thus far is for building binary trees ... i.e.
 a given node only has two children.  I need n children per node.  One
 article said that any type of tree can be represented as a binary tree, but
 I am failing to see that.
  
 Any suggestions or pointers?

Pick up a copy of Joe Celko's SQL for Smarties. He might look like
Ming the Merciless, but he's bloody good. The book goes into a lot of
detail about representing hierarchies in RDBMSs. And even if you can't
justify it for that alone, there's lots of other stuff covered in it.

Take a peek on Amazon.

K.

~|
Logware (www.logware.us): a new and convenient web-based time tracking 
application. Start tracking and documenting hours spent on a project or with a 
client with Logware today. Try it for free with a 15 day trial account.
http://www.houseoffusion.com/banners/view.cfm?bannerid=67

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194715
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


RE: Tree Traversal / Storage Algorithm

2005-02-15 Thread Jeff Chastain
Thanks everybody for the recommendation.  I guess with this many people
saying it, I had better go check out this book.

-- Jeff 

-Original Message-
From: Michael T. Tangorre [mailto:[EMAIL PROTECTED] 
Sent: Monday, February 14, 2005 10:35 PM
To: CF-Talk
Subject: RE: Tree Traversal / Storage Algorithm

 

 From: Rob Munn [mailto:[EMAIL PROTECTED] Joe Celko has a great 
 example of tree modelling using nested sets in  SQL for Smarties. In 
 fact, he has a PHP class for doing just this released under gpl. Check 
 it out:

I don't know about the PHP class, but I can attest to Joe Celko's tree using
nested sets as a great concept to learn! I use it a lot with hierarchies of
permissions, etc. The SQL For Smarties book is one that makes you just say,
damn, I thought I knew a lot of SQL!!

Mike





~|
Discover CFTicket - The leading ColdFusion Help Desk and Trouble 
Ticket application

http://www.houseoffusion.com/banners/view.cfm?bannerid=48

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194718
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


RE: Tree Traversal / Storage Algorithm

2005-02-15 Thread Matthew Small
You can represent any hierarchy with a binary tree. You just have to
consider that all children of a node cumulatively is the number n instead of
2, although each node has exactly 2 children nodes. 

If you go with the binary tree, consider an AVL tree, which is perfectly
balanced at all times.

You may be also interested in the B tree, which grows up instead of down and
has as many node divisions as you want, although there is still a defined
limit on the number of nodes in a branch - there has to be in order to
define a new root.

But I think the real thing you're looking for here is something akin to a
linked list.  If you consider that a node could four pointers:

Up
Down
Left
Right

Up goes to the parent node
Down goes to the first child node
Left goes to the previous sibling
Right goes to the next sibling

You ought to be able to represent a node with n children nodes, nested
infinitely deep.

A language that uses pointers or allows for infinite (or near infinite)
growth of an array (like C++ or CF) should be able to provide you what you
need.

I think that XML is a structure like what you're talking about.

- Matt Small


Jeff Chastain wrote:
  
 I am trying to remember my old CS days, but the memory is going.  I need
to
 simulate a tree with n-nodes per branch ... i.e. a nested folder structure
 with 0 to n objects in each folder.  The folders can be nested infinitely
 deep.  So, what is the algorithm for traversing this type of tree?
  
 Most everything I have found thus far is for building binary trees ...
i.e.
 a given node only has two children.  I need n children per node.  One
 article said that any type of tree can be represented as a binary tree,
but
 I am failing to see that.
  


~|
Find out how CFTicket can increase your company's customer support 
efficiency by 100%
http://www.houseoffusion.com/banners/view.cfm?bannerid=49

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194721
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


Re: Tree Traversal / Storage Algorithm

2005-02-15 Thread Deanna Schneider
He has a new book specifically on trees. I'm not sure how much this is just 
rehashing what's in sql for smarties, but you might want to check this out:
http://www.amazon.com/exec/obidos/ASIN/1558609202/qid=1108476965/sr=2-1/ref=pd_ka_b_2_1/002-6823342-1106443

- Original Message - 
From: Jeff Chastain [EMAIL PROTECTED]
To: CF-Talk cf-talk@houseoffusion.com
Sent: Tuesday, February 15, 2005 7:52 AM
Subject: RE: Tree Traversal / Storage Algorithm


 Thanks everybody for the recommendation.  I guess with this many people
 saying it, I had better go check out this book.

 -- Jeff

 -Original Message-
 From: Michael T. Tangorre [mailto:[EMAIL PROTECTED]
 Sent: Monday, February 14, 2005 10:35 PM
 To: CF-Talk
 Subject: RE: Tree Traversal / Storage Algorithm



 From: Rob Munn [mailto:[EMAIL PROTECTED] Joe Celko has a great
 example of tree modelling using nested sets in  SQL for Smarties. In
 fact, he has a PHP class for doing just this released under gpl. Check
 it out:

 I don't know about the PHP class, but I can attest to Joe Celko's tree 
 using
 nested sets as a great concept to learn! I use it a lot with hierarchies 
 of
 permissions, etc. The SQL For Smarties book is one that makes you just 
 say,
 damn, I thought I knew a lot of SQL!!

 Mike





 

~|
Find out how CFTicket can increase your company's customer support 
efficiency by 100%
http://www.houseoffusion.com/banners/view.cfm?bannerid=49

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194725
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


Re: Tree Traversal / Storage Algorithm

2005-02-15 Thread Roger B.
Jeff: I never had any old CS days to forget, but the best approach
to tree-building that I've found is a single id/parentid query wed to
a set of parallel structures that are connected by reference.

cfquery
FETCH YOUR IDs and PARENTIDs
/cfquery

!--- CREATE PARALLEL STRUCTURES ---
cfset stcTree = StructNew()
cfset stcFlat = StructNew()

cfloop query=qryNodes
cfset node = StructNew()
cfset node.id = id
cfset node.parentid = parentid
cfset stcFlat[n#id#] = node
cfif NOT StructKeyExists(stcFlat, n#parentid#)
cfset stcTree[n#id#] = stcflat[n#id#]
cfelse
cfset stcflat[n#parentid#][n#id#] = stcflat[n#id#]
/cfif
/cfloop

You can recursively walk stcTree to display it graphically, or use
node.parentid and node.id to quickly crawl up the stcFlat to create a
breadcrumb trail. And unlike other methods, it also gives you an easy
way to snap a branch off the tree and do something with it.

--
Roger Benningfield
free blog hosting for MX people
http://mxblogspace.journurl.com/

~|
Logware (www.logware.us): a new and convenient web-based time tracking 
application. Start tracking and documenting hours spent on a project or with a 
client with Logware today. Try it for free with a 15 day trial account.
http://www.houseoffusion.com/banners/view.cfm?bannerid=67

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194820
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: 
http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=11502.10531.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


Tree Traversal / Storage Algorithm

2005-02-14 Thread Jeff Chastain
 
I am trying to remember my old CS days, but the memory is going.  I need to
simulate a tree with n-nodes per branch ... i.e. a nested folder structure
with 0 to n objects in each folder.  The folders can be nested infinitely
deep.  So, what is the algorithm for traversing this type of tree?
 
Most everything I have found thus far is for building binary trees ... i.e.
a given node only has two children.  I need n children per node.  One
article said that any type of tree can be represented as a binary tree, but
I am failing to see that.
 
Any suggestions or pointers?
 
Thanks
-- Jeff



~|
Logware (www.logware.us): a new and convenient web-based time tracking 
application. Start tracking and documenting hours spent on a project or with a 
client with Logware today. Try it for free with a 15 day trial account.
http://www.houseoffusion.com/banners/view.cfm?bannerid=67

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194644
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: 
http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=11502.10531.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


RE: Tree Traversal / Storage Algorithm

2005-02-14 Thread Paul Vernon
Looks like you will be needing a recursive type of function to do this...

Funnily enough, I just wrote something for a manufacturers stock control
system where they have an end product and the component tree used to
describe the item can be n levels deep and a items wide. I ended up using
the function below to build a structure recursively by calling itself so
that it traversed the entire structure one layer at a time.


cffunction name=retrieveItemComponents access=public
returnType=struct output=true
hint=Recursively lists all the child items for a specific
parent item

cfargument name=ItemID type=numeric required=true

cfquery name=q datasource=#instance.dsn#
SELECT I.ItemName, S.ItemID AS ChildItemID
FROM Items I, SubItems S
WHERE I.ItemID = cfqueryparam
value=#arguments.ItemID# cfsqltype=CF_SQL_INTEGER 
AND I.ItemID = S.ParentItemID
/cfquery  

cfif q.recordcount GT 0
cfset var ItemStruct = StructNew()

cfset ItemStruct.siblings = 
cfloop query=q
cfset var currentItem =
listItems(-1,ChildItemID,-1)
cfset ItemStruct.ItemID = ChildItemID
cfset ItemStruct.ItemName =
currentItem.ItemName
cfset ItemStruct.ItemCode =
currentItem.ItemCode
!--- here we go with the recursive bit ---
cfset StructInsert(ItemStruct,
ItemID#ChildItemID#, retrieveItemComponents(ChildItemID,
arguments.enabledOutput))
cfset ItemStruct.siblings =
ListAppend(ItemStruct.siblings, ChildItemID)
/cfloop   
cfreturn ItemStruct
cfelse
cfreturn var ItemStruct = StructNew()
/cfif
/cffunction


Essentially, we have to tables, Items is the one storing the items and
SubItems has just two fields.. ItemID and ParentItemID. This allows me to
represent a tree structure of any width and depth... 

There are probably ways to do this in some forms of SQL but this method was
my only option. It's reasonably neat and produces a nice little structure to
use...

Paul


~|
Discover CFTicket - The leading ColdFusion Help Desk and Trouble 
Ticket application

http://www.houseoffusion.com/banners/view.cfm?bannerid=48

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194646
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: 
http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=11502.10531.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


Re: Tree Traversal / Storage Algorithm

2005-02-14 Thread Joe Rinehart
It can also be done w/o recursion using what's known as modified
preorder tree traversal, which is a really neat extension of the
adjancency list model.  There's a good tutorial on it at
http://www.sitepoint.com/article/hierarchical-data-database one
day I'll blog it into CF.

-joe



On Tue, 15 Feb 2005 01:57:52 -, Paul Vernon
[EMAIL PROTECTED] wrote:
 Looks like you will be needing a recursive type of function to do this...
 
 Funnily enough, I just wrote something for a manufacturers stock control
 system where they have an end product and the component tree used to
 describe the item can be n levels deep and a items wide. I ended up using
 the function below to build a structure recursively by calling itself so
 that it traversed the entire structure one layer at a time.
 
 cffunction name=retrieveItemComponents access=public
 returnType=struct output=true
 hint=Recursively lists all the child items for a specific
 parent item
 
 cfargument name=ItemID type=numeric required=true
 
 cfquery name=q datasource=#instance.dsn#
 SELECT I.ItemName, S.ItemID AS ChildItemID
 FROM Items I, SubItems S
 WHERE I.ItemID = cfqueryparam
 value=#arguments.ItemID# cfsqltype=CF_SQL_INTEGER
 AND I.ItemID = S.ParentItemID
 /cfquery
 
 cfif q.recordcount GT 0
 cfset var ItemStruct = StructNew()
 
 cfset ItemStruct.siblings = 
 cfloop query=q
 cfset var currentItem =
 listItems(-1,ChildItemID,-1)
 cfset ItemStruct.ItemID = ChildItemID
 cfset ItemStruct.ItemName =
 currentItem.ItemName
 cfset ItemStruct.ItemCode =
 currentItem.ItemCode
 !--- here we go with the recursive bit ---
 cfset StructInsert(ItemStruct,
 ItemID#ChildItemID#, retrieveItemComponents(ChildItemID,
 arguments.enabledOutput))
 cfset ItemStruct.siblings =
 ListAppend(ItemStruct.siblings, ChildItemID)
 /cfloop
 cfreturn ItemStruct
 cfelse
 cfreturn var ItemStruct = StructNew()
 /cfif
 /cffunction
 
 Essentially, we have to tables, Items is the one storing the items and
 SubItems has just two fields.. ItemID and ParentItemID. This allows me to
 represent a tree structure of any width and depth...
 
 There are probably ways to do this in some forms of SQL but this method was
 my only option. It's reasonably neat and produces a nice little structure to
 use...
 
 Paul
 
 

~|
Logware (www.logware.us): a new and convenient web-based time tracking 
application. Start tracking and documenting hours spent on a project or with a 
client with Logware today. Try it for free with a 15 day trial account.
http://www.houseoffusion.com/banners/view.cfm?bannerid=67

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194652
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: 
http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=11502.10531.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


RE: Tree Traversal / Storage Algorithm

2005-02-14 Thread Jeff Chastain
I was looking at this earlier and it looked like a really nice solution.
However, I am not following if/how it would work for a non-binary tree?  How
would this work for a node that had 3 or more children?

-- Jeff
 

-Original Message-
From: Joe Rinehart [mailto:[EMAIL PROTECTED] 
Sent: Monday, February 14, 2005 8:27 PM
To: CF-Talk
Subject: Re: Tree Traversal / Storage Algorithm

It can also be done w/o recursion using what's known as modified preorder
tree traversal, which is a really neat extension of the adjancency list
model.  There's a good tutorial on it at
http://www.sitepoint.com/article/hierarchical-data-database one day I'll
blog it into CF.

-joe



On Tue, 15 Feb 2005 01:57:52 -, Paul Vernon
[EMAIL PROTECTED] wrote:
 Looks like you will be needing a recursive type of function to do this...
 
 Funnily enough, I just wrote something for a manufacturers stock 
 control system where they have an end product and the component tree 
 used to describe the item can be n levels deep and a items wide. I 
 ended up using the function below to build a structure recursively by 
 calling itself so that it traversed the entire structure one layer at a
time.
 
 cffunction name=retrieveItemComponents access=public
 returnType=struct output=true
 hint=Recursively lists all the child items for a 
 specific parent item
 
 cfargument name=ItemID type=numeric 
 required=true
 
 cfquery name=q datasource=#instance.dsn#
 SELECT I.ItemName, S.ItemID AS ChildItemID
 FROM Items I, SubItems S
 WHERE I.ItemID = cfqueryparam 
 value=#arguments.ItemID# cfsqltype=CF_SQL_INTEGER
 AND I.ItemID = S.ParentItemID
 /cfquery
 
 cfif q.recordcount GT 0
 cfset var ItemStruct = StructNew()
 
 cfset ItemStruct.siblings = 
 cfloop query=q
 cfset var currentItem = 
 listItems(-1,ChildItemID,-1)
 cfset ItemStruct.ItemID = ChildItemID
 cfset ItemStruct.ItemName = 
 currentItem.ItemName
 cfset ItemStruct.ItemCode = 
 currentItem.ItemCode
 !--- here we go with the recursive bit
---
 cfset StructInsert(ItemStruct, 
 ItemID#ChildItemID#, retrieveItemComponents(ChildItemID,
 arguments.enabledOutput))
 cfset ItemStruct.siblings = 
 ListAppend(ItemStruct.siblings, ChildItemID)
 /cfloop
 cfreturn ItemStruct
 cfelse
 cfreturn var ItemStruct = StructNew()
 /cfif
 /cffunction
 
 Essentially, we have to tables, Items is the one storing the items and 
 SubItems has just two fields.. ItemID and ParentItemID. This allows me 
 to represent a tree structure of any width and depth...
 
 There are probably ways to do this in some forms of SQL but this 
 method was my only option. It's reasonably neat and produces a nice 
 little structure to use...
 
 Paul
 
 



~|
Logware (www.logware.us): a new and convenient web-based time tracking 
application. Start tracking and documenting hours spent on a project or with a 
client with Logware today. Try it for free with a 15 day trial account.
http://www.houseoffusion.com/banners/view.cfm?bannerid=67

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194668
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


Re: Tree Traversal / Storage Algorithm

2005-02-14 Thread Rob Munn
Joe Celko has a great example of tree modelling using nested sets in  SQL
for Smarties. In fact, he has a PHP class for doing just this released
under gpl. Check it out:

http://phpclasses.mirrors.nyphp.org/browse/package/1374.html




- Original Message - 
From: Joe Rinehart [EMAIL PROTECTED]
To: CF-Talk cf-talk@houseoffusion.com
Sent: Monday, February 14, 2005 6:26 PM
Subject: Re: Tree Traversal / Storage Algorithm


 It can also be done w/o recursion using what's known as modified
 preorder tree traversal, which is a really neat extension of the
 adjancency list model.  There's a good tutorial on it at
 http://www.sitepoint.com/article/hierarchical-data-database one
 day I'll blog it into CF.

 -joe



 On Tue, 15 Feb 2005 01:57:52 -, Paul Vernon
 [EMAIL PROTECTED] wrote:
  Looks like you will be needing a recursive type of function to do
this...
 
  Funnily enough, I just wrote something for a manufacturers stock control
  system where they have an end product and the component tree used to
  describe the item can be n levels deep and a items wide. I ended up
using
  the function below to build a structure recursively by calling itself so
  that it traversed the entire structure one layer at a time.
 
  cffunction name=retrieveItemComponents access=public
  returnType=struct output=true
  hint=Recursively lists all the child items for a
specific
  parent item
 
  cfargument name=ItemID type=numeric
required=true
 
  cfquery name=q datasource=#instance.dsn#
  SELECT I.ItemName, S.ItemID AS ChildItemID
  FROM Items I, SubItems S
  WHERE I.ItemID = cfqueryparam
  value=#arguments.ItemID# cfsqltype=CF_SQL_INTEGER
  AND I.ItemID = S.ParentItemID
  /cfquery
 
  cfif q.recordcount GT 0
  cfset var ItemStruct = StructNew()
 
  cfset ItemStruct.siblings = 
  cfloop query=q
  cfset var currentItem =
  listItems(-1,ChildItemID,-1)
  cfset ItemStruct.ItemID = ChildItemID
  cfset ItemStruct.ItemName =
  currentItem.ItemName
  cfset ItemStruct.ItemCode =
  currentItem.ItemCode
  !--- here we go with the recursive
bit ---
  cfset StructInsert(ItemStruct,
  ItemID#ChildItemID#, retrieveItemComponents(ChildItemID,
  arguments.enabledOutput))
  cfset ItemStruct.siblings =
  ListAppend(ItemStruct.siblings, ChildItemID)
  /cfloop
  cfreturn ItemStruct
  cfelse
  cfreturn var ItemStruct = StructNew()
  /cfif
  /cffunction
 
  Essentially, we have to tables, Items is the one storing the items and
  SubItems has just two fields.. ItemID and ParentItemID. This allows me
to
  represent a tree structure of any width and depth...
 
  There are probably ways to do this in some forms of SQL but this method
was
  my only option. It's reasonably neat and produces a nice little
structure to
  use...
 
  Paul
 
 

 

~|
Logware (www.logware.us): a new and convenient web-based time tracking 
application. Start tracking and documenting hours spent on a project or with a 
client with Logware today. Try it for free with a 15 day trial account.
http://www.houseoffusion.com/banners/view.cfm?bannerid=67

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194673
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


Re: Tree Traversal / Storage Algorithm

2005-02-14 Thread Dick Applebaum
I was going to suggest Joe Celko, too... it is worth the ea!

Dick

On Feb 14, 2005, at 8:12 PM, Rob Munn wrote:

 Joe Celko has a great example of tree modelling using nested sets in  
 SQL
 for Smarties. In fact, he has a PHP class for doing just this released
 under gpl. Check it out:

 http://phpclasses.mirrors.nyphp.org/browse/package/1374.html




 - Original Message -
 From: Joe Rinehart [EMAIL PROTECTED]
 To: CF-Talk cf-talk@houseoffusion.com
 Sent: Monday, February 14, 2005 6:26 PM
 Subject: Re: Tree Traversal / Storage Algorithm


 It can also be done w/o recursion using what's known as modified
 preorder tree traversal, which is a really neat extension of the
 adjancency list model.  There's a good tutorial on it at
 http://www.sitepoint.com/article/hierarchical-data-database one
 day I'll blog it into CF.

 -joe



 On Tue, 15 Feb 2005 01:57:52 -, Paul Vernon
 [EMAIL PROTECTED] wrote:
 Looks like you will be needing a recursive type of function to do
 this...

 Funnily enough, I just wrote something for a manufacturers stock 
 control
 system where they have an end product and the component tree used to
 describe the item can be n levels deep and a items wide. I ended up
 using
 the function below to build a structure recursively by calling 
 itself so
 that it traversed the entire structure one layer at a time.

 cffunction name=retrieveItemComponents access=public
 returnType=struct output=true
 hint=Recursively lists all the child items for a
 specific
 parent item

 cfargument name=ItemID type=numeric
 required=true

 cfquery name=q datasource=#instance.dsn#
 SELECT I.ItemName, S.ItemID AS ChildItemID
 FROM Items I, SubItems S
 WHERE I.ItemID = cfqueryparam
 value=#arguments.ItemID# cfsqltype=CF_SQL_INTEGER
 AND I.ItemID = S.ParentItemID
 /cfquery

 cfif q.recordcount GT 0
 cfset var ItemStruct = StructNew()

 cfset ItemStruct.siblings = 
 cfloop query=q
 cfset var currentItem =
 listItems(-1,ChildItemID,-1)
 cfset ItemStruct.ItemID = 
 ChildItemID
 cfset ItemStruct.ItemName =
 currentItem.ItemName
 cfset ItemStruct.ItemCode =
 currentItem.ItemCode
 !--- here we go with the recursive
 bit ---
 cfset StructInsert(ItemStruct,
 ItemID#ChildItemID#, retrieveItemComponents(ChildItemID,
 arguments.enabledOutput))
 cfset ItemStruct.siblings =
 ListAppend(ItemStruct.siblings, ChildItemID)
 /cfloop
 cfreturn ItemStruct
 cfelse
 cfreturn var ItemStruct = StructNew()
 /cfif
 /cffunction

 Essentially, we have to tables, Items is the one storing the items 
 and
 SubItems has just two fields.. ItemID and ParentItemID. This allows 
 me
 to
 represent a tree structure of any width and depth...

 There are probably ways to do this in some forms of SQL but this 
 method
 was
 my only option. It's reasonably neat and produces a nice little
 structure to
 use...

 Paul





 

~|
Find out how CFTicket can increase your company's customer support 
efficiency by 100%
http://www.houseoffusion.com/banners/view.cfm?bannerid=49

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194674
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54


RE: Tree Traversal / Storage Algorithm

2005-02-14 Thread Michael T. Tangorre
 

 From: Rob Munn [mailto:[EMAIL PROTECTED] 
 Joe Celko has a great example of tree modelling using nested 
 sets in  SQL
 for Smarties. In fact, he has a PHP class for doing just 
 this released
 under gpl. Check it out:

I don't know about the PHP class, but I can attest to Joe Celko's tree using
nested sets as a great concept to learn! I use it a lot with hierarchies of
permissions, etc. The SQL For Smarties book is one that makes you just say,
damn, I thought I knew a lot of SQL!!

Mike



~|
Discover CFTicket - The leading ColdFusion Help Desk and Trouble 
Ticket application

http://www.houseoffusion.com/banners/view.cfm?bannerid=48

Message: http://www.houseoffusion.com/lists.cfm/link=i:4:194675
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations  Support: http://www.houseoffusion.com/tiny.cfm/54