Displaying a Geneology

cotterman99

I have been struggling with this problem for HOURS. It involves displaying the geneology of a 2x2 forced matrix. The database setup is simple: all this info is stored in a Referrals table, with the fields AffID and ReferredBy.

This is how the output needs to be:

                                            7
                                10                 11
                           28     29         12    14

And so on, down to the 5th level.

For an example of output, visit the following link:
http://www.computersandcash.com/aff/test.php?id=7

Querying the database for member 7's referrals is no problem. The problem arises because the table needs to be built row-by-row, but any function to recursively find referral ID's would need to be done level-by-level.

What I've been trying to do is write a recursive function to store all the ID's into an array, and then simply output the table based on that array structure. Is this even a feasible way to approach the problem? Perhaps another structure would work better, such as a Queue...does PHP have any built-in Queue?

I'm desperate to solve this problem. If anyone can help me, I'd greatly appreciate it.

Weedpacket

Originally posted by cotterman99
does PHP have any built-in Queue?

No, but it has an array and functions that perform queue and stack operations on it (see array_pop, array_push, array_shift, and array_unshift).

Is this a binary tree? Your array elements could include a pair of elements that point to its descendants. Start with the root, look up its descendants. Once you've got them, stick them on the end of the array and set ['leftchild'] and ['rightchild'] to the array index they were stuck into. Go on to the next element in the array (the first one after the root would be one of those you stuck in while dealing with the root). Repeat the process.

Continue until you come to the end of the array.

Now you've got a tree you can walk by following children.

If it's not a binary tree, then instead of ['leftchild'] and ['rightchild'] elements, there'd be a single ['children'] element, which would be an array of indices.

That's just my first idea. My first ideas aren't necessarily the best (or even particularly good). I'd have to work on the problem myself before I could be confident about whatever I suggest.

cotterman99

I think the binary tree is a great idea. It would be simple to create the tree by querying the database. Then, displaying the HTML table is simply a Level-Order Traversal.

Unfortunately, the only object-oriented experience I have is with Java, and classes in PHP are significantly different. It would take much too long to go that route. I might have a working solution, but I'm not getting my hopes up yet.

If anyone has any suggestions, I'm very welcome to them!

Thanks for all your help.

Weedpacket

There is a binary tree class floating around somewhere if I can just recall where I saw it... ah, PHPClasses.org. Not that I've used it at all - just happen to recall seeing it there.

Of course, I figured you weren't going to be needing a full-blown tree-manipulation thingy, which is why I just augmented a straight array with a couple of extra fields per element, and not launching into an exercise in object orientation.