468,251 Members | 1,478 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,251 developers. It's quick & easy.

displaying categories/subcategories using modified preorder tree transversal

I have been working on a ecommerce website for myself. What I needed
some assistance on was when i was trying to display the
categories/subcategories for the different products.
I decided to use the modified preorder tree transversal algorithm. What
I wanted was on the first page is to display the catogories as follows

Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following

Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

In my MYSQL database table, I have the fields catid, name, lft and
rgt. For example for the three categories mentioned above I have the
following entries

catid name lft rgt
1 home 1 1
2 books 2 17
4 fiction 3 10
5 nonfiction 11 16
3 electronics 18 37
The first category home was just used to represent the main root of the
whole tree. If anyone could give me some assistance, it would be much
appreciated. Thank you in advance.

Aug 30 '06 #1
13 3587
the category table should look like the following. it did not display
very well in the first message

catid, name,lft,rgt
1, home,1,1
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37


hornedw wrote:
I have been working on a ecommerce website for myself. What I needed
some assistance on was when i was trying to display the
categories/subcategories for the different products.
I decided to use the modified preorder tree transversal algorithm. What
I wanted was on the first page is to display the catogories as follows

Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following

Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

In my MYSQL database table, I have the fields catid, name, lft and
rgt. For example for the three categories mentioned above I have the
following entries

catid name lft rgt
1 home 1 1
2 books 2 17
4 fiction 3 10
5 nonfiction 11 16
3 electronics 18 37
The first category home was just used to represent the main root of the
whole tree. If anyone could give me some assistance, it would be much
appreciated. Thank you in advance.
Aug 30 '06 #2
hornedw wrote:
the category table should look like the following. it did not display
very well in the first message

catid, name,lft,rgt
1, home,1,1
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37


hornedw wrote:
>>I have been working on a ecommerce website for myself. What I needed
some assistance on was when i was trying to display the
categories/subcategories for the different products.
I decided to use the modified preorder tree transversal algorithm. What
I wanted was on the first page is to display the catogories as follows

Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following

Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

In my MYSQL database table, I have the fields catid, name, lft and
rgt. For example for the three categories mentioned above I have the
following entries

catid name lft rgt
1 home 1 1
2 books 2 17
4 fiction 3 10
5 nonfiction 11 16
3 electronics 18 37
The first category home was just used to represent the main root of the
whole tree. If anyone could give me some assistance, it would be much
appreciated. Thank you in advance.

I guess I'm confused. How do you link from "fiction" or "nonfiction" to
books?

This way of doing it looks quite confusing to me.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Aug 31 '06 #3
Jerry

I was trying to set it up where when a person clicks on books the page
would reload and then display Books and then Nonfiction and Fiction
would appear under it. Like below
Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following
Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

It does not necessaryly have to be spaced over. I may use bulleted list
or something like that. The main two things I was trying to do was use
the modfied preorder tree algorithm and to have it display the main
category and then display the main category and its subcategories and
then the rest of the categories on the page. I was debating on whether
doing it this way or something similar to the way it is done at
Amazon.com on their categories.

David
Jerry Stuckle wrote:
hornedw wrote:
the category table should look like the following. it did not display
very well in the first message

catid, name,lft,rgt
1, home,1,1
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37


hornedw wrote:
>I have been working on a ecommerce website for myself. What I needed
some assistance on was when i was trying to display the
categories/subcategories for the different products.
I decided to use the modified preorder tree transversal algorithm. What
I wanted was on the first page is to display the catogories as follows

Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following

Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

In my MYSQL database table, I have the fields catid, name, lft and
rgt. For example for the three categories mentioned above I have the
following entries

catid name lft rgt
1 home 1 1
2 books 2 17
4 fiction 3 10
5 nonfiction 11 16
3 electronics 18 37
The first category home was just used to represent the main root of the
whole tree. If anyone could give me some assistance, it would be much
appreciated. Thank you in advance.

I guess I'm confused. How do you link from "fiction" or "nonfiction" to
books?

This way of doing it looks quite confusing to me.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Sep 1 '06 #4
hornedw wrote:
Jerry

I was trying to set it up where when a person clicks on books the page
would reload and then display Books and then Nonfiction and Fiction
would appear under it. Like below
Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following
Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

It does not necessaryly have to be spaced over. I may use bulleted list
or something like that. The main two things I was trying to do was use
the modfied preorder tree algorithm and to have it display the main
category and then display the main category and its subcategories and
then the rest of the categories on the page. I was debating on whether
doing it this way or something similar to the way it is done at
Amazon.com on their categories.

David
Jerry Stuckle wrote:
>>hornedw wrote:
>>>the category table should look like the following. it did not display
very well in the first message

catid, name,lft,rgt
1, home,1,1
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37


hornedw wrote:
I have been working on a ecommerce website for myself. What I needed
some assistance on was when i was trying to display the
categories/subcategories for the different products.
I decided to use the modified preorder tree transversal algorithm. What
I wanted was on the first page is to display the catogories as follows

Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following

Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

In my MYSQL database table, I have the fields catid, name, lft and
rgt. For example for the three categories mentioned above I have the
following entries

catid name lft rgt
1 home 1 1
2 books 2 17
4 fiction 3 10
5 nonfiction 11 16
3 electronics 18 37
The first category home was just used to represent the main root of the
whole tree. If anyone could give me some assistance, it would be much
appreciated. Thank you in advance.

I guess I'm confused. How do you link from "fiction" or "nonfiction" to
books?

This way of doing it looks quite confusing to me.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================

Yes, I'm aware of what you're trying to do. What I'm confused about is
how, from the information you provided, the system is supposed to know
that fiction and nonfiction fall under books. The example you have
doesn't show any way to determine if something is a top level category
or a subcategory - and if the latter, which is its parent category.

P.S. Please don't top post.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Sep 1 '06 #5

Jerry Stuckle wrote:
hornedw wrote:
Jerry

I was trying to set it up where when a person clicks on books the page
would reload and then display Books and then Nonfiction and Fiction
would appear under it. Like below
Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following
Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

It does not necessaryly have to be spaced over. I may use bulleted list
or something like that. The main two things I was trying to do was use
the modfied preorder tree algorithm and to have it display the main
category and then display the main category and its subcategories and
then the rest of the categories on the page. I was debating on whether
doing it this way or something similar to the way it is done at
Amazon.com on their categories.

David
Jerry Stuckle wrote:
>hornedw wrote:

the category table should look like the following. it did not display
very well in the first message

catid, name,lft,rgt
1, home,1,1
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37


hornedw wrote:
I have been working on a ecommerce website for myself. What I needed
some assistance on was when i was trying to display the
categories/subcategories for the different products.
I decided to use the modified preorder tree transversal algorithm. What
I wanted was on the first page is to display the catogories as follows

Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following

Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

In my MYSQL database table, I have the fields catid, name, lft and
rgt. For example for the three categories mentioned above I have the
following entries

catid name lft rgt
1 home 1 1
2 books 2 17
4 fiction 3 10
5 nonfiction 11 16
3 electronics 18 37
The first category home was just used to represent the main root of the
whole tree. If anyone could give me some assistance, it would be much
appreciated. Thank you in advance.
I guess I'm confused. How do you link from "fiction" or "nonfiction" to
books?

This way of doing it looks quite confusing to me.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================

Yes, I'm aware of what you're trying to do. What I'm confused about is
how, from the information you provided, the system is supposed to know
that fiction and nonfiction fall under books. The example you have
doesn't show any way to determine if something is a top level category
or a subcategory - and if the latter, which is its parent category.

P.S. Please don't top post.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
I got most of my information from
http://dev.mysql.com/tech-resources/...ical-data.html
Under the section where it says "Nested Set"

I will try to explain using the example I gave.

I noticed on my example that the rgt value for home should have been 38
Here is the datbase values I had in my previous post
catid, name,lft,rgt
>>1, home,1,38
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37

Basically this algorithm sets up the data you are working in as a tree
diagram.Each block has a left and right value. You start on the left of
the root of the tree and go around the diagram and number the blocks. .
If the item has a child, you will number the parent's left value and
the child's left value. If the item is a child, you wll number the left
value and then go to the right value of the child. The difference
between the right and left value of a child is always 1. Once you have
given the child its right value, you will go back up the tree and give
the parent its right value Once you have reached the main parent under
the root, you go to the next main parent that is under the root. You
continue this until you have given the last main parent its right value
and then you give the root its right value.

In the example above, Home has the biggest difference between its right
and left values and therefore is the root. Books is the first main
parent category. The left and right values of fiction and nonfiction
fall between the left and right values of books. That is how books is
the parent category of fiction and nonfiction. Electronics is another
main category in the table. The list I gave above is not a full list
of al the categories and subcategories For example, I do not have any
child subcategories listed. I know this not a very good explanation,
but the website listed above may be of greater help of explaining what
I am trying to do.

David

Sep 1 '06 #6
hornedw wrote:
Jerry Stuckle wrote:
>>hornedw wrote:
>>>Jerry

I was trying to set it up where when a person clicks on books the page
would reload and then display Books and then Nonfiction and Fiction
would appear under it. Like below
Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following
Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

It does not necessaryly have to be spaced over. I may use bulleted list
or something like that. The main two things I was trying to do was use
the modfied preorder tree algorithm and to have it display the main
category and then display the main category and its subcategories and
then the rest of the categories on the page. I was debating on whether
doing it this way or something similar to the way it is done at
Amazon.com on their categories.

David
Jerry Stuckle wrote:
hornedw wrote:
>the category table should look like the following. it did not display
>very well in the first message
>
>catid, name,lft,rgt
>1, home,1,1
>2, books,2,17
>4, fiction,3,10
>5, nonfiction, 11,16
>3, electronics,18, 37
>
>
>
>
>
>
>hornedw wrote:
>
>
>
>>I have been working on a ecommerce website for myself. What I needed
>>some assistance on was when i was trying to display the
>>categories/subcategories for the different products.
>>I decided to use the modified preorder tree transversal algorithm. What
>>I wanted was on the first page is to display the catogories as follows
>>
>>Books (35)
>>Electronics(23)
>>
>>The number inside the parenthesis being the number of products in that
>>category. When Books is clicked on, it would display the following
>>
>>Books(35)
>>Fiction(18)
>>Nonfiction(17)
>>Electronics(23)
>>
>>In my MYSQL database table, I have the fields catid, name, lft and
>>rgt. For example for the three categories mentioned above I have the
>>following entries
>>
>>catid name lft rgt
>>1 home 1 1
>>2 books 2 17
>>4 fiction 3 10
>>5 nonfiction 11 16
>>3 electronics 18 37
>>
>>
>>The first category home was just used to represent the main root of the
>>whole tree. If anyone could give me some assistance, it would be much
>>appreciated. Thank you in advance.
>
>
I guess I'm confused. How do you link from "fiction" or "nonfiction" to
books?

This way of doing it looks quite confusing to me.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================

Yes, I'm aware of what you're trying to do. What I'm confused about is
how, from the information you provided, the system is supposed to know
that fiction and nonfiction fall under books. The example you have
doesn't show any way to determine if something is a top level category
or a subcategory - and if the latter, which is its parent category.

P.S. Please don't top post.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================


I got most of my information from
http://dev.mysql.com/tech-resources/...ical-data.html
Under the section where it says "Nested Set"

I will try to explain using the example I gave.

I noticed on my example that the rgt value for home should have been 38
Here is the datbase values I had in my previous post
catid, name,lft,rgt
>>>>>1, home,1,38
>2, books,2,17
>4, fiction,3,10
>5, nonfiction, 11,16
>3, electronics,18, 37

Basically this algorithm sets up the data you are working in as a tree
diagram.Each block has a left and right value. You start on the left of
the root of the tree and go around the diagram and number the blocks. .
If the item has a child, you will number the parent's left value and
the child's left value. If the item is a child, you wll number the left
value and then go to the right value of the child. The difference
between the right and left value of a child is always 1. Once you have
given the child its right value, you will go back up the tree and give
the parent its right value Once you have reached the main parent under
the root, you go to the next main parent that is under the root. You
continue this until you have given the last main parent its right value
and then you give the root its right value.

In the example above, Home has the biggest difference between its right
and left values and therefore is the root. Books is the first main
parent category. The left and right values of fiction and nonfiction
fall between the left and right values of books. That is how books is
the parent category of fiction and nonfiction. Electronics is another
main category in the table. The list I gave above is not a full list
of al the categories and subcategories For example, I do not have any
child subcategories listed. I know this not a very good explanation,
but the website listed above may be of greater help of explaining what
I am trying to do.

David
David,

All I can say is - that has got to be one of the WORST implementations
I've ever seen. Talk about making a simple problem complex - this takes
the cake.

I wouldn't even try implementing something like this.

Rather, keep it simple:

id parent description
1 null books
2 1 nonfiction
3 1 fiction
4 null electronics

The only thing I'm not sure of is if MySQL will support recursive
queries - haven't tried it. If so, you can get your info in one sql
statement. Otherwise you'll have to do a little recursion in your PHP code.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Sep 1 '06 #7
OK, back to the original problem....

I presume that when you select a node, you are actually having trouble
writing the SQL query to correctly return the higher level nodes as
showing....

Books
-->Fiction
-->-->Classic
-->-->Sci-Fi
-->NonFiction
Video

This is a perfect example of where javascript and CSS would be handy.
Why not return all the elements and contain each one within a <DIV>
with the visible poperty set to false and an onClick() event for the
parent category that sets the visible property of the child div to true
or false.

Obiron

Sep 1 '06 #8
Jerry Stuckle wrote:
All I can say is - that has got to be one of the WORST implementations
I've ever seen. Talk about making a simple problem complex - this takes
the cake.

I wouldn't even try implementing something like this.

Rather, keep it simple:

id parent description
1 null books
2 1 nonfiction
3 1 fiction
4 null electronics
At first glance, something like a preorder-tree traversal setup is
needlessly complex. I agree that the example you provided is much
easier to visualize conceptually.

I agree because I have made that mistake in the past. We had a project
that involved massive trees (we're talking the bill of materials for an
entire automobile down to an individual screw), and went with the
simple 'parent' scheme, but were too deep into the project before we
suddenly regretted it. A scheme like that is easy to set up, but a
nightmare to use and maintain.

To get a node and its children from the example you gave (known as the
Adjacency model), you have to rely either on recursion or knowing
exactly how many levels exist. The former introduces significant
overhead while the latter is just bad hard-coding. Using a more
advanced tree algorithm allows for a much easier time working with
nodes and children. The link provided earlier
(http://dev.mysql.com/tech-resources/...ical-data.html)
is a great resource for seeing the different queries required to work
with either scheme.

I doubt the OP will be dealing with trees quite as large as the ones I
needed to use, but if you can deal with a bit of complexity up front,
you can save yourself a lot of extra work later on.

And speaking of the original post...I didn't quite understand what you
were asking. If you were asking for advice on getting the # of items
in each category, perhaps you could use the examples on that page
linked to for getting all the children of a node, and then WHERE'ing it
to include only those nodes whose lft & rgt are 1 apart (meaning they
have no children).

Sep 1 '06 #9
mo*******************@yahoo.com wrote:
Jerry Stuckle wrote:
>>All I can say is - that has got to be one of the WORST implementations
I've ever seen. Talk about making a simple problem complex - this takes
the cake.

I wouldn't even try implementing something like this.

Rather, keep it simple:

id parent description
1 null books
2 1 nonfiction
3 1 fiction
4 null electronics


At first glance, something like a preorder-tree traversal setup is
needlessly complex. I agree that the example you provided is much
easier to visualize conceptually.

I agree because I have made that mistake in the past. We had a project
that involved massive trees (we're talking the bill of materials for an
entire automobile down to an individual screw), and went with the
simple 'parent' scheme, but were too deep into the project before we
suddenly regretted it. A scheme like that is easy to set up, but a
nightmare to use and maintain.
Interesting. I've implemented this for things like a flight database -
all scheduled flights throughout the world, with each departure and
destination airport, etd and eta, etc. And been able to use recursive
queries to find possible flight combinations to get from one destination
to another - one single query would get it. And although there are a
lot of parts in an automobile, there are also a lot of scheduled flights
in the world for a year.

If you can do recursive queries, it works quite well. And this was with
DB2, which handles recursive queries quite well.
To get a node and its children from the example you gave (known as the
Adjacency model), you have to rely either on recursion or knowing
exactly how many levels exist. The former introduces significant
overhead while the latter is just bad hard-coding. Using a more
advanced tree algorithm allows for a much easier time working with
nodes and children. The link provided earlier
Not that much overhead if you can do the recursion in SQL. One query
can get everything.
(http://dev.mysql.com/tech-resources/...ical-data.html)
is a great resource for seeing the different queries required to work
with either scheme.

I doubt the OP will be dealing with trees quite as large as the ones I
needed to use, but if you can deal with a bit of complexity up front,
you can save yourself a lot of extra work later on.
And if you can do your recursion in your SQL statements you don't even
need the complexity.
And speaking of the original post...I didn't quite understand what you
were asking. If you were asking for advice on getting the # of items
in each category, perhaps you could use the examples on that page
linked to for getting all the children of a node, and then WHERE'ing it
to include only those nodes whose lft & rgt are 1 apart (meaning they
have no children).

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Sep 1 '06 #10
Jerry Stuckle wrote:
>
If you can do recursive queries, it works quite well. And this was with
DB2, which handles recursive queries quite well.
Hmm. The DB we were using didn't support recursive queries, so I never
got to explore that path, unfortunately. I suspect that, as you say,
it would handle well enough performance-wise, seeing that all the
recursing is done on the DB itself rather than via recursive queries
coming from the code. Still, though, even the most efficient recursion
carries along with it some degree of overhead. That's just the nature
of recursion.

If I had the time spare time, I would love to implement a number of
tree algorithms and see how they scale in performance as the size of
the tree increases. That is the kind of assignment I WISH they had
given back in college. Practical and educational.

Sep 1 '06 #11

mo*******************@yahoo.com wrote:
Jerry Stuckle wrote:

If you can do recursive queries, it works quite well. And this was with
DB2, which handles recursive queries quite well.

Hmm. The DB we were using didn't support recursive queries, so I never
got to explore that path, unfortunately. I suspect that, as you say,
it would handle well enough performance-wise, seeing that all the
recursing is done on the DB itself rather than via recursive queries
coming from the code. Still, though, even the most efficient recursion
carries along with it some degree of overhead. That's just the nature
of recursion.

If I had the time spare time, I would love to implement a number of
tree algorithms and see how they scale in performance as the size of
the tree increases. That is the kind of assignment I WISH they had
given back in college. Practical and educational.
Thanks everyone for your help. I probably will either use Javascript or
CSS in displaying the child categories or set it up similar to
Amazon.com's categories(main categories display on one page, and the
category selected and its subcategories on the second page. Thanks
mootmail--I will look back at the link I provided earlier as to display
the number of items.

David

Sep 2 '06 #12
On 2006-09-01 22:48:44 -0600, "hornedw" <ho*****@yahoo.comsaid:
>
mo*******************@yahoo.com wrote:
>Jerry Stuckle wrote:
>>>
If you can do recursive queries, it works quite well. And this was with
DB2, which handles recursive queries quite well.

Hmm. The DB we were using didn't support recursive queries, so I never
got to explore that path, unfortunately. I suspect that, as you say,
it would handle well enough performance-wise, seeing that all the
recursing is done on the DB itself rather than via recursive queries
coming from the code. Still, though, even the most efficient recursion
carries along with it some degree of overhead. That's just the nature
of recursion.

If I had the time spare time, I would love to implement a number of
tree algorithms and see how they scale in performance as the size of
the tree increases. That is the kind of assignment I WISH they had
given back in college. Practical and educational.

Thanks everyone for your help. I probably will either use Javascript or
CSS in displaying the child categories or set it up similar to
Amazon.com's categories(main categories display on one page, and the
category selected and its subcategories on the second page. Thanks
mootmail--I will look back at the link I provided earlier as to display
the number of items.

David
What if your result set is in the thousands? Tens of thousands?
JavaScript probably wouldn't do so well with that.

Here's a way to do it, ugly proof of concept but it works while letting
you control how much data is loaded into memory:

Tables:
================================

Table 1: categories
cat_id cat_parent cat_name
1 0 books
2 1 fiction
3 2 classic
4 2 sci-fi
5 1 non-fiction

Table 2: Items
item_id item_cat item_name item_description
1 3 'hamlet' 'shakespeare'
2 3 'romeo & juliet' 'shakespeare'
3 4 'episode 1' 'star wars'
4 4 'episode 2' 'star wars'

PHP:
================================

<pre>
<?php

//
// usage: array load_tree(int cat_id, int child depth);
//
function load_tree($cat_id, $depth, $cur_level = 0) {
if ($cur_level $depth) {return;}

$ret = array();
$cats = mysql_fetch_assoc(mysql_query("SELECT * FROM categories WHERE
cat_id='$cat_id'"));
$ret[$cats['cat_name']] = array();

$sub_cats = mysql_query("SELECT * FROM categories WHERE
cat_parent='".$cats['cat_id']."'");

$cur_level++;
while ($cats2 = mysql_fetch_assoc($sub_cats)) {
$ret[$cats['cat_name']][] = load_tree($cats2['cat_id'], $depth, $cur_level);
}
$cur_level--;

$items = mysql_query("SELECT * FROM items WHERE item_cat='$cat_id'");
while ($item = mysql_fetch_assoc($items)) {
$ret[$cats['cat_name']][] = $item;
}
return $ret;
}

function print_tree($tree, $indent = ' ') {
if (!is_array($tree)) {return;}
if (isset($tree['item_name'])) {
echo $indent.$tree['item_name'].' '.$tree['item_description'].'<br />';
} else {
foreach ($tree as $key =$val) {
echo $indent.$key.'<br />';
if (count($val) 0) {
foreach ($val as $val2) {
print_tree($val2, $indent.$indent);
}
}
}
}
}

$tree = load_tree(1, 3);

//print_r($tree);
echo "\n\n";
print_tree($tree);
?>

Output:
================================

books
fiction
classic
hamlet (shakespeare)
romeo & juliet (shakespeare)
sci-fi
episode 1 (star wars)
episode 2 (star wars)
non-fiction
================================

You could do the same thing in reverse, recursively querying for the
parent instead of the children, but you would only end up with a single
main category (categories other than 'books' would be ignored).

Hope this gives you another idea. I've used this method many times to
create download pages and other things, works quite well (even though
the '$tree' array is ugly).

Sep 2 '06 #13

onembk wrote:
On 2006-09-01 22:48:44 -0600, "hornedw" <ho*****@yahoo.comsaid:

mo*******************@yahoo.com wrote:
Jerry Stuckle wrote:

If you can do recursive queries, it works quite well. And this was with
DB2, which handles recursive queries quite well.
Hmm. The DB we were using didn't support recursive queries, so I never
got to explore that path, unfortunately. I suspect that, as you say,
it would handle well enough performance-wise, seeing that all the
recursing is done on the DB itself rather than via recursive queries
coming from the code. Still, though, even the most efficient recursion
carries along with it some degree of overhead. That's just the nature
of recursion.

If I had the time spare time, I would love to implement a number of
tree algorithms and see how they scale in performance as the size of
the tree increases. That is the kind of assignment I WISH they had
given back in college. Practical and educational.
Thanks everyone for your help. I probably will either use Javascript or
CSS in displaying the child categories or set it up similar to
Amazon.com's categories(main categories display on one page, and the
category selected and its subcategories on the second page. Thanks
mootmail--I will look back at the link I provided earlier as to display
the number of items.

David

What if your result set is in the thousands? Tens of thousands?
JavaScript probably wouldn't do so well with that.

Here's a way to do it, ugly proof of concept but it works while letting
you control how much data is loaded into memory:

Tables:
================================

Table 1: categories
cat_id cat_parent cat_name
1 0 books
2 1 fiction
3 2 classic
4 2 sci-fi
5 1 non-fiction

Table 2: Items
item_id item_cat item_name item_description
1 3 'hamlet' 'shakespeare'
2 3 'romeo & juliet' 'shakespeare'
3 4 'episode 1' 'star wars'
4 4 'episode 2' 'star wars'

PHP:
================================

<pre>
<?php

//
// usage: array load_tree(int cat_id, int child depth);
//
function load_tree($cat_id, $depth, $cur_level = 0) {
if ($cur_level $depth) {return;}

$ret = array();
$cats = mysql_fetch_assoc(mysql_query("SELECT * FROM categories WHERE
cat_id='$cat_id'"));
$ret[$cats['cat_name']] = array();

$sub_cats = mysql_query("SELECT * FROM categories WHERE
cat_parent='".$cats['cat_id']."'");

$cur_level++;
while ($cats2 = mysql_fetch_assoc($sub_cats)) {
$ret[$cats['cat_name']][] = load_tree($cats2['cat_id'], $depth, $cur_level);
}
$cur_level--;

$items = mysql_query("SELECT * FROM items WHERE item_cat='$cat_id'");
while ($item = mysql_fetch_assoc($items)) {
$ret[$cats['cat_name']][] = $item;
}
return $ret;
}

function print_tree($tree, $indent = ' ') {
if (!is_array($tree)) {return;}
if (isset($tree['item_name'])) {
echo $indent.$tree['item_name'].' '.$tree['item_description'].'<br />';
} else {
foreach ($tree as $key =$val) {
echo $indent.$key.'<br />';
if (count($val) 0) {
foreach ($val as $val2) {
print_tree($val2, $indent.$indent);
}
}
}
}
}

$tree = load_tree(1, 3);

//print_r($tree);
echo "\n\n";
print_tree($tree);
?>

Output:
================================

books
fiction
classic
hamlet (shakespeare)
romeo & juliet (shakespeare)
sci-fi
episode 1 (star wars)
episode 2 (star wars)
non-fiction
================================

You could do the same thing in reverse, recursively querying for the
parent instead of the children, but you would only end up with a single
main category (categories other than 'books' would be ignored).

Hope this gives you another idea. I've used this method many times to
create download pages and other things, works quite well (even though
the '$tree' array is ugly).
Thanks onembk, I will give that a try.

Sep 3 '06 #14

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by Brian | last post: by
2 posts views Thread by Troy Lynch | last post: by
reply views Thread by Reed | last post: by
1 post views Thread by Neil McGuigan | last post: by
reply views Thread by Manuel | last post: by
reply views Thread by NPC403 | last post: by
reply views Thread by kermitthefrogpy | last post: by
reply views Thread by zattat | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.