Tree library for PHP using left & right ids

Question

I'm looking for a library in PHP that can create a tree structure from a database (or array of values) with left and right ids. For the result when getting values I am only looking for an array so I can create any type of view. For adding and removing, it would be nice if the library did it all. Even if the library is within another library, I don't mind as I'll probably pull it out and integrate it with my own libraries.

Anyone know of anything?

I'm using PHP & MySQL, so it'd be helpful if it used atleast PHP. If it's a different database I can probably convert it, although maybe the same with PHP if it doesn't use too much language specific functionality.

Answer 1

This is the code i used to build binary tree and its opeartions in php:

  <?php
class Node
{
 public $data;
 public $leftChild;
 public $rightChild;

 public function __construct($data)
  {
   $this->data=$data;
   $this->leftChild=null;
   $this->rightChild=null;
  }
 public function disp_data()
  {
   echo $this->data;
  }


}//end class Node
class BinaryTree
{
 public $root;
 //public $s;
 public function __construct()
  {
   $this->root=null;
   //$this->s=file_get_contents('store');

  }
//function to display the tree
  public function display()
  {
   $this->display_tree($this->root);

  }
  public function display_tree($local_root)
  {

   if($local_root==null) 
     return;
    $this->display_tree($local_root->leftChild);
    echo $local_root->data."<br/>";
    $this->display_tree($local_root->rightChild);

  } 
// function to insert a new node
  public function insert($key)
   {
    $newnode=new Node($key);
      if($this->root==null)
        {
         $this->root=$newnode;
         return;
        }
      else
        {
         $parent=$this->root;
         $current=$this->root;
           while(true)
             {
               $parent=$current;
                 //$this->find_order($key,$current->data);
                if($key==($this->find_order($key,$current->data)))
                  {
                      $current=$current->leftChild;
                       if($current==null)
                         {
                          $parent->leftChild=$newnode;
                          return;
                         }//end if2
                  }//end if1 
                else
                  {
                      $current=$current->rightChild;
                       if($current==null)
                         {
                          $parent->rightChild=$newnode;
                          return;  
                         } //end if1                       
                  } //end else
             }//end while loop 
        }//end else

   } //end insert function

//function to search a particular Node
 public function find($key)
  {
    $current=$this->root;
     while($current->data!=$key)
          {
            if($key==$this->find_order($key,$current->data))
              {
                $current=$current->leftChild;
              }
            else
              {
                $current=$current->rightChild;
              }
            if($current==null)
              return(null);

          }
         return($current->data); 
  }// end the function to search
 public function delete1($key)
  {
    $current=$this->root;
    $parent=$this->root;

    $isLeftChild=true;
     while($current->data!=$key)
          {
           $parent=$current;
           if($key==($this->find_order($key,$current->data)))
             {
              $current=$current->leftChild;
              $isLeftChild=true;
             }   
           else
             {
              $current=$current->rightChild;
              $isLeftChild=false;   
             } 
            if($current==null)
              return(null);
          }//end while loop 

      echo "<br/><br/>Node to delete:".$current->data;
     //to delete a leaf node 
     if($current->leftChild==null&&$current->rightChild==null)
       {
           if($current==$this->root)
              $this->root=null;  
          else if($isLeftChild==true)
           {
            $parent->leftChild=null;
           }  
         else
           {
            $parent->rightChild=null;
           }
         return($current);       
       }//end if1
     //to delete a node having a leftChild 
   else if($current->rightChild==null)
       {
          if($current==$this->root)
           $this->root=$current->leftChild;
          else if($isLeftChild==true)
           {
            $parent->leftChild=$current->leftChild;
           }
          else
           {
            $parent->rightChild=$current->leftChild;
           }   
          return($current);
       }//end else if1
    //to delete a node having a rightChild
   else if($current->leftChild==null)
       {
         if($current==$this->root)
           $this->root=$current->rightChild;
         else if($isLeftChild==true)
           {
            $parent->leftChild=$current->rightChild;
           }  
         else
           {
            $parent->rightChild=$current->rightChild; 
           }  
           return($current);
       }  
   //to delete a node having both childs
    else
       {
        $successor=$this->get_successor($current);
        if($current==$this->root)
          {
            $this->root=$successor; 

          }
        else if($isLeftChild==true)
          {
           $parent->leftChild=$successor;
          }
        else
          {
           $parent->rightChild=$successor;
          }     
         $successor->leftChild=$current->leftChild;
        return($current);
       }   


  }//end the function to delete a node
//Function to find the successor node
 public function get_successor($delNode)
  {
   $succParent=$delNode;
   $successor=$delNode;
   $temp=$delNode->rightChild;
    while($temp!=null)
         {
          $succParent=$successor;
          $successor=$temp;
          $temp=$temp->leftChild;
         }
   if($successor!=$delNode->rightChild)
     {
      $succParent->leftChild=$successor->rightChild;
      $successor->rightChild=$delNode->rightChild;
     }
  return($successor);
  }
//function to find the order of two strings
 public function find_order($str1,$str2)
  {
     $str1=strtolower($str1);
     $str2=strtolower($str2);
     $i=0;
     $j=0;

     $p1=$str1[i];
     $p2=$str2[j]; 
  while(true)
   {  
       if(ord($p1)<ord($p2)||($p1==''&&$p2==''))
         {

           return($str1);
         }
      else
         {
           if(ord($p1)==ord($p2))
             {
              $p1=$str1[++$i];
              $p2=$str2[++$j];
              continue;
             }
          return($str2); 
         }
   }//end while

  } //end function find string order

 public function is_empty()
  {
    if($this->root==null)
      return(true);
    else
      return(false);
  }
}//end class BinaryTree
?>

Answer 2

This approach is called "nested sets"

Searching for the best PHP nested sets class (PEAR class excluded)

basically there is the NSTree library which doesn't seem to be maintained and there is a PEAR library. Probably there are others but that's just a summary of the other post.

Answer 3

ezComponents Tree library has different backends (tie-ins), that you can choose between. The documentation is pretty good as well.

Answer 4

I am in the midst of a project that uses tree structures for navigation and also selection of (what to) update. I must admit that (being self-taught) I wasn't that familiar with the left-right values approach and so opted for what I have just discovered via a very helpful article to be called The Adjacency List Model.

Having thought about it, and now being somewhat more familiar, I still think I'd do the same. With TALM, coding PHP views & updates are easy as you're primarily concerned with the parent relationship of a node.

Then for display you have jQuery Treeview, which I can't recommend highly enough, and for selections there's jquery-checktree which I'm still in the process of incorporating and so can't vouch for, but looks good.