#1
  1. No Profile Picture
    Another damn newb...
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2002
    Location
    BodÝ, Norway
    Posts
    94
    Rep Power
    13

    Traversing a non-binary tree i php


    I'm having difficulties with the recursive calls.

    I have this database with a tree structure that stores "id", "parent_id" and "name" for each element. The elements with parent_id=0 is at the root level.

    Anyone able to help me traverse my tree and maybe also print it to screen?

    I also wanted to do this in an effective way with minimum number of queries to mysql. Could it be dnone without recursion as well? Perhaps just select all rows from the table and then iterate through them one by one, placing each record inside an array that simulates the tree...

    Well then there is the problem with traversing this array... It will need recursive calls too....... Argh.

    Whats the more efficient way?
    Torkil Johnsen

    Never underestimate the power of stupid people in large groups...
    ---------------------------(Ú”,)----
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2002
    Location
    NYC
    Posts
    79
    Rep Power
    13
    These are going to be fairly simple observations, but...

    First off, as a general thing, relational databases do not behave well as graphs, which is what a tree is, because and "relationship" only gets you one level.

    Secondly, since you want to traverse the entire tree, it seems, that means going through your entire data structure (several times if it's in a database).

    Third you can iterate just fine (doesn't need to be recursive). We start off finding the leaf nodes (has to be the leaf nodes because you don't have a facility for children).

    Starting off. Find the leaf nodes. These are the ones such that no parent_id of any other row is equal to their id. There is a writeup of how to do this kind of query in the docs of the mysql web site at http://www.mysql.com/doc/en/JOIN.html
    You'll have to adapt it for your own use.

    After this, just examine each element, in turn, to get its parent. If you are hitting the database, it will be a lot of repeated searches. So, depending on size, you could build your own representation within PHP.

    What we need is a graphical database.

    Csaba Gabor
  4. #3
  5. No Profile Picture
    Senior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2003
    Posts
    151
    Rep Power
    0
    to traverse the tree you could use depth first search or breadth first search depending on how you want it displayed. depth first uses a stack while breadth first uses a queue. im not sure if php has these structures builtin, but you could create one using an array.

    if you dont know what the hell depth first search or breadth first search is, then this is probably too much trouble to learn the algorithm and create the appropriate data structures.

    a better way is to use celko nested sets. it is better in terms of optimality when displaying trees, although a bit more complicated when inserting and updating. check it out

    http://www.sitepoint.com/print/1105
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2002
    Location
    NYC
    Posts
    79
    Rep Power
    13
    An array IS a queue right out of the box in PHP. That is to say, if you shove elements in:
    $foo = array();
    $foo[6] = "Hi";
    $foo[3] = "Mom";
    $foo[2] = "and";
    $foo[1] = "Dad";

    and now iterate through the array using a foreach, you get the elements out in the order they went in. Furthermore, if you delete an element by unset (say unset($foo[3]) the remaining elements stay in their originally entered order. So this is a superset of a queue's functionality.

    PHP is also thoughtful enough to provide a method for getting to the last element of a hash table (which is what an array is in PHP) by means of array_splice(...) However, this reindexes the array, which tends to suggest that one cannot claim an out of the box stack by this method (I.e. can't trivially claim O(1) speed). However, if one assumes incremental numeric indeces, then knowledge of the size of the array is sufficient for a trivial implementation.

    Csaba
  8. #5
  9. No Profile Picture
    Senior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2003
    Posts
    151
    Rep Power
    0
    that's great. so now you can write your recursive function.
  10. #6
  11. No Profile Picture
    Senior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2003
    Posts
    151
    Rep Power
    0
    ok, i wasnt sure how much you knew about algorithms and data structures. this is a simple depth first function, it could be made cleaner by adding some if statements in there so that declaring a stack and pushing the root would be apart of the function, but i hope this illustrates the idea. if you want breadth first then use a queue instead of a stack
    Code:
    begin function printTree
      while stack not empty
        temp node = pop stack;
        print temp node;
        push temp node's children on stack (if any);
        call printTree;
    end printTree
    
    declare an empty global stack object;
    push the root on the stack;
    call printTree;

IMN logo majestic logo threadwatch logo seochat tools logo