Getting a table's values into a tree

Question

So, I have a table like such:

id|root|kw1|kw2|kw3|kw4|kw5|name
 1|   A|  B|  C|  D|  E|  F|fileA
 2|   A|  B|   |   |   |   |fileB
 3|   B|  C|  D|  E|   |   |fileC
 4|   A|  B|   |   |   |   |fileD

(several hundred rows...)

And I need to get it into a tree like the following:

*A
 *B
  -fileB
  -fileD
 *C
  *D
   *E
    *F
     -fileA
*B
 *C
  *D
   *E
    -fileC

I'm pretty sure the table is laid out poorly but it's what I have to live with.

I've read a little about Adjacency List Model & Modified Preorder Tree Traversal but I don't think my data is laid out correctly. I think this requires a recursive function, but I'm not at all sure how to go about that.

I'm open to any ideas of how to get this done even if it means extracting the data into a new table just to process this.

Are there any good options available to me or any good ways to do this? (Examples are a bonus of course)

Answer 1

Here's the simplest working solution I could come up with.

Assumptions:

1. You have an array of arrays (your result set); it is named $rows.
2. Empty column values in the result set you give above are equal to null.
3. There are no branches in your tree whose names are string representations of integers.

The code:

$tree = array();

foreach($rows as $row) {
    // Second parameter: array of 6 items as per your sample result set
    place_in_tree($tree, array($row['root'], ... $row['kw5']), $row['file']);
}

function place_in_tree(array $tree, array $path, $item) {
    // While there are more branches to be taken in $path
    while(($branch = array_shift($path)) !== null) {
        // Create the new branch if it doesn't exist
        if(!isset($tree[$branch])) {
            $tree[$branch] = array();
        }

        // Select the subtree in that branch for the next iteration
        $tree = $tree[$branch];
    }

    // Finally, add the item
    $tree[] = $item;
}

This creates an array with nested arrays. This array contains a number of items with string keys (these are "branches", and are of type array) and a number of items with numeric keys (these are "files", and are of type string). Child arrays are populated in the same way.

If you require something more close to your business model than a big honking array, you can tweak the branch selection and item storage logic in function place_in_tree above.

Also, if assumption #3 above does not hold in your case, you will need to get a little involved in the same manner, either choosing a non-ambiguous way to tell apart the branches and leaves of the tree, or choosing another structure to represent it.