Hi,

I wish to able to produce a list of links, like this:
link1/
link1/link2/
link1/link2/link3
link1/link2/link3/link4/
link1/link2/link3/link4/link4a
link1/link2/link3/link4/link5
I am using a Modified Preorder Tree Traversal algorithm to produce the hierachical structure.
The database table looks like this:
Code:
+-------------------+
| lft | name  | rgt |
+-------------------+
|  1  | link1 |  16 |
+-------------------+
|  2  | link2 |  15 |
+-------------------+
|  3  | link3 |  14 |
+-------------------+
|  4  | link4 |  13 |
+-------------------+
|  5  | link4a|  6  |
+-------------------+
|  7  | link4b| 10  |
+-------------------+
|  8  | link5 |  9  |
+-------------------+
|  11 | link4c| 12  |
+-------------------+
I have produced a class which does everything I need, such as determine parent<-->children relationships,
insert new nodes, etc. The bit I am struggling with is printing the information in the format I showed up top.
I want to "walk" down the tree and produce the link list as shown. I just don't seem to be able to get it right.
I have been able to produce an indented link list:
Code:
link1
	link2
		link3
			link4
				link4a
				link4b
				link4c
				link5
The method where all this takes place in displayTree().
Any help most appreciated!
Thanks
Code follows:
PHP Code:
<?php
  
include('DB.php');
  class 
tree
  
{
      var 
$newName;
      function 
tree($parent
      {
          
$dbh = new DB();
          
$dbh->connect();
          
$this->_parent $parent;
          
$qry "SELECT lft, name, rgt FROM subcategory1 WHERE name = '$this->_parent'";
          
          
$dbh->execute($qry);
          
$this->_parentValues $dbh->fetch_assoc();   
      }      
      function 
getChildren()
      {
          
$dbh = new DB();
          
$dbh->connect();
          
$qry  "SELECT * ";
          
$qry .= "FROM subcategory1 ";
          
$qry .= sprintf("WHERE lft BETWEEN %s AND %s "$this->_parentValues['lft'], $this->_parentValues['rgt']);
          
$qry .= "ORDER BY lft";  
          
          
$dbh->execute($qry);
          return 
$dbh->fetch_all_assoc();       
      }
      function 
addChild($name)
      {
          
$dbh = new DB();
          
$dbh->connect();
          
$this->newNode $name;          
          
$this->_updExistingValues();   
          
$qry['new'] = sprintf("INSERT INTO subcategory1 VALUES (%s, '%s', %s)"$this->_parentValues['lft'] + 1$this->newNode$this->_parentValues['lft'] + 2);            
          
$dbh->execute($qry['new']);     
          return;
      }
      function 
displayTree($branch
      {
          
$_stack = array();
          foreach(
$branch as $row) {
              if (
count($_stack) > 0) {
                 while(
$_stack[count($_stack) - 1] < $row['rgt']) {
                     
array_pop($_stack);
                 }
              }
              
//print str_repeat('    ', count($_stack)) . $row['name'] . "\n";
              
$_stack[] = $row['rgt'];
          }
      }      
      function 
_updExistingValues()
      {
          
$dbh = new DB();
          
$dbh->connect();
          
$qry['rgt'] = "UPDATE subcategory1 SET rgt = rgt + 2 WHERE rgt > {$this->_parentValues['lft']}";
          
$qry['lft'] = "UPDATE subcategory1 SET lft = lft + 2 WHERE lft > {$this->_parentValues['lft']}";
          
$dbh->execute($qry['rgt']);
          
$dbh->execute($qry['lft']);     
          return;          
      }
  }
 
  
$myTree = new tree('link1');
  
$branch $myTree->getChildren();
  
$myTree->displayTree($branch);
  
/*
  $myTree->addChild('link4c');
  print_r($myTree->getChildren());
*/
?>