Recursive Tree Structure, how ?

Results 1 to 3 of 3

Thread: Recursive Tree Structure, how ?

  1. #1
    Paul Watson Guest

    Default Recursive Tree Structure, how ?

    I am developing an in house intranet system in ASP. Luckily everyone in the company has IE5 so I can basically go wild and include some pretty fancy tricks and layouts. However I have a problem.<BR>One section of the intranet is a library of articles, with each article being able to be listed under a category. Naturally I also want categories to host their own categories (i.e HTML, then DHTML or XML then XSL). Seeing as the intranet is a "push the boundaries" project I dont want the number of sub categories to be restricted in any way.<BR><BR>I have setup a very simple prototype table in SQL7 called Categories with fields for the categories Name, Description and then a field called ParentID which holds the unique ID of the category which the current category is under. So if XML had an id of 123 then XSL would have an ID of whatever (125) and a parent ID of 123.<BR><BR>All simple so far... However how in the world do I then create a tree like structure which lists each category in its proper place ? There has already been an article on 4Guys about this, but it had a limit of 12 items deep. <BR><BR>Any hints would be greatly appreciated.<BR><BR>thank you

  2. #2
    DamonF Guest

    Default RE: Recursive Tree Structure, how ?

    There are two ways to do what you are asking. The first is a structure called a general tree. The best way I see to implement this is to have each node have a pointer to for children and a pointer for sibling. The sibling pointer would serve as the next node in a linked-list. And the child pointer would serve as a link to the head of the list containing all of the child nodes for a specific node. ie<BR><BR>&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp2&nbsp-&nbsp1&nbsp-&nbsp3&nbsp-&nbsp8<BR>&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp<BR>&nbsp&nbsp&nbsp&nbsp& nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp4&nbsp &nbsp&nbsp5&nbsp&nbsp&nbsp&nbsp9 <BR>&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp& nbsp&nbsp&nbsp/&nbsp<BR>&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp& nbsp&nbsp&nbsp6&nbsp&nbsp&nbsp7<BR><BR>would be stored as<BR>1<BR>&#124<BR>2 - 3 - 4 - 5<BR>&nbsp&nbsp&nbsp&nbsp&nbsp&#124&nbsp&nbsp&nbsp &nbsp&#124<BR>&nbsp&nbsp&nbsp&nbsp&nbsp&#124&nbsp& nbsp&nbsp&nbsp6 - 7<BR>&nbsp&nbsp&nbsp&nbsp&nbsp&#124<BR>&nbsp&nbsp& nbsp&nbsp&nbsp8 - 9 <BR><BR>Or depending on what you want to do with the data, you might want to store it as a graph. Since trees are usually unidirectional structures keeping track of parent nodes could become a burden when searching and such. However, a bidirectional acyclic graph might be better suited for the task. This could be done by storing the data in an adjacency list. Then to print them out you would need to do a depth-first traversal of the graph. Or you could use the former solution and use doubly linked-lists and it would make keeping track of the parent nodes a little more painless.<BR><BR>1 : 2 - 3 - 4 - 5<BR>2 : 1<BR>3 : 1 - 8 - 9<BR>4 : 1 - 6 - 7<BR>5 : 1<BR>6 : 4<BR>7 : 4<BR>8 : 3<BR>9 : 3<BR>

  3. #3
    Paul Watson Guest

    Default RE: Recursive Tree Structure, how ?

    woooooooooo, thanks for the help Damon. Ill just have to get my thinking cap on to interpret it all (I am more a designer than serious coder, my maths is shocking too).<BR><BR>thanks again :)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts