PHP中遍历树的数据结构？

Question

我没有 CS 或数据结构背景。我想制作一个 PHP 类来存储 修改后的预序横向树，用于操作和与数据库同步。

基本上我需要存储如下数据：

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

我正在考虑使用数组，但它看起来很麻烦。如果是这样的数组数组：array( 'name'=> "PORTABLE ELECTRONICS", 'lft' => 10, 'rgt' = 19 )，那么就会变得很麻烦重复循环该数组以确保所有数字都存在，等等。

由于 PHP 有一些新的可用数据结构，我想知道这些结构中的任何一个是否会给我带来比使用数组更好的好处？

• SplDoubly
• LinkedList
• SplStack
• SplQueue
• SplHeap
• SplMaxHeap
• SplMinHeap
• SplPriorityQueue
• SplFixedArray
• SplObjectStorage

---

编辑：此类不会成为存储在数据库表中的树的网关。 （如果是的话，我只会查询类。）它只是某种 PHP 数据结构中的独立 mmpt。

Answer 1

编辑：好的，我对此进行了更多研究。我认为术语中存在混淆。您并不是在 PHP 中寻找横向树的数据结构。您想要在 PHP 中使用树作为数据结构，并且想要使用一种称为修改的先序树遍历算法的方法从该树中恢复数据。

引用：

当使用树时，我们工作从左到右，一次一层，下降到每个节点的子节点，然后分配右侧编号并继续向右移动。这种方法称为改进的先序树遍历算法。

---

这是关于在 PHP 和 MySQL 中存储分层数据的问题。在 PHP 中我们可以使用一个简单的树。问题在于，在MySQL这样的平面数据库中存储一棵树并不容易。一种选择是获取 PHP 并从中检索邻接表。这本质上是每个项目及其父项的列表。这种做事方式有一些缺点。

另一种方法是从 PHP 树中提取信息，该信息描述了可以由分层数据构成的嵌套集。为了从 PHP 树中获取此信息，我们需要使用修改的先序树遍历算法。这是一种在树上上下运行以从中提取某些信息的方法。

无论我们使用邻接表模型还是修改后的先序树遍历来检索信息，我们都使用完全相同的 PHP Tree。区别在于我们如何从树中检索信息以及如何将信息存储在 MySQL 中。如何从 MySQL 中提取信息的代码已经位于 您引用的页面上。要在 PHP 和 MySQL 之间同步数据，您只需使用该页面上描述的 MySQL 技术和 PHP 树类。

为此，我在 PHP 中创建了一个存储树的类。它使用一个节点。每个节点都可以被认为是完整树的根，因为可以从每个节点访问完整的子树。将节点从树中分离出来更容易，而且开销也更少。

该类的重要部分是 showAdjacency 方法。这将使用修改后的前序树遍历来运行树，并显示每个名称的 lft 和 rgt 数量，使您能够将数据作为嵌套集存储在 MySQL 中。

您还可以显示树，以便将其可视化。该类缺少删除方法。当您实现它时，您必须将已删除节点的子节点传递给该节点的父节点。也许我稍后会这样做。

我将在帖子底部包含整个类，但以下是如何检索修改后的前序树遍历的数据：

      // The modified preorder tree traversal.
    private function showAdjacency($root, $spaces)
    {
          // Print the data first
        if ($root)
        {
              // On the way down the tree, we get lft.
            $left = ++$spaces;                
            foreach( $root->next as $child)
            {                    
                if ($child)
                {
                    $spaces = $this->showAdjacency($child, $spaces);                      
                }
            }
        }
          // On the way back up, we get rgt.
        $right = ++$spaces;
        echo "$left - $right - $root->data <br/>";                
        return $spaces;
    }

您显然可以将 $root->data、$rgt 和 $lft 存储在一个数组中您用来与数据库同步。

这是全班同学。课后，我使用 您链接到的页面中的示例数据创建一棵树，我输出 lft 和 rgt 值以及树可视化。

您可以在Codepad上运行代码

<?php  
  // Class defintions and methods:
  // It's easier to use separate nodes. Each node still points to an entire and complete subtree.
class Node
{
    public $data;
    public $next = array();
}

  // A first try at creating a tree with any number of branches from its nodes
  // by Peter Ajtai - feel free to use and modify
class Tree
{
    // The root
    private $root;
    public function __construct()
    {
        $this->root = NULL;
    }

      // The public wrapper. 
      // This is needed because we must start the recursive functions
      // at the root, and we do not want to give public access to root.
      // I am not familiar w overloading in PHP, maybe __set should be used for this
    public function insertPub($data, $parent)
    {
        $root =& $this->root;
        $this->insert($root, $data, $parent);
    }

    private function insert(&$root, $data, $parent)
    {

          // Create the root of the entire tree if no parent is passed in        
        if (!$root && !$parent)
        {
            $root = new Node;
            $temp =& $root;
            $temp->data = $data;
            // Create space for next insertion
            $temp->next[] = NULL;                     
        } else if ($root->data == $parent)
        {

              // Add data as a child if we're at the parent, and we're done.
              // Find the empty node to insert at
            foreach($root->next as &$child)
            {
                  // Insert at the first (and only) NULL
                if (!$child)
                {
                    $child = new Node;
                    $temp =& $child;
                    $temp->data = $data;                        
                    // Create space for next insertion
                    $temp->next[] = NULL;
                }
            }
              // Create space for the next insertion
            $root->next[] = NULL;
        } else
        {
              // Keep searching for the parent as default behavior.
            foreach($root->next as $child)
            {
                if ($child)
                {
                    $this->insert($child, $data, $parent);
                }
            }
        }
    }
      // Public wrapper for the display function.
    public function showAdjPub()
    {
        echo "The neighbors:<br/><br/>";
        $root =& $this->root;
        $this->showAdjacency($root, 0);
        echo "<br/>";
    }

      // The display function.
    private function showAdjacency($root, $spaces)
    {
          // Print the data first
        if ($root)
        {
            $left = ++$spaces;                
            foreach( $root->next as $child)
            {                    
                if ($child)
                {
                    $spaces = $this->showAdjacency($child, $spaces);                      
                }
            }
        }
        $right = ++$spaces;
        echo "$left - $right - $root->data <br/>";                
        return $spaces;
    }
      // Public wrapper for the display function.
    public function showAllPub()
    {
        echo "The tree:<br/><br/>";
        $root =& $this->root;
        $this->showAll($root, 0);
        echo "<br/>";
    }

      // The display function.
    private function showAll($root, $spaces)
    {
          // Print the data first
        if ($root)
        {
            for ($i=0; $i < $spaces; ++$i)
                echo "---> ";
            echo "$root->data <br/>";
            ++$spaces;
            foreach( $root->next as $child)
            {                    
                if ($child)
                {
                    $this->showAll($child, $spaces);
                }
            }
        }
    }        
}

  // Create a new instance of the tree
$myTree = new Tree;

  // Insert the data into the tree.    
  // The following data would be retrieved using MySQL
$name = 'Electronics'; $parent = NULL;
$myTree->insertPub($name, $parent);
$name = 'Televisions'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);
$name = 'Tube'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);    
$name = 'Lcd'; $parent = 'Televisions';
$myTree->insertPub($name, $parent); 
$name = 'Plasma'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);    
$name = 'Portable Electronics'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);    
$name = 'MP3 Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);    
$name = 'Flash'; $parent = 'MP3 Players';
$myTree->insertPub($name, $parent);    
$name = 'CD Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);    
$name = '2 Way Radios'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);    

  // Display adjacency
$myTree->showAdjPub();

  // Show hierarchy    
$myTree->showAllPub();      
?>

---

PS：存储像你建议的那样，PHP 中的嵌套数组中的数据将非常困难。在上面的类中，如果删除数据成员，则树被修改（包括添加整个子树等），lft 和 rgt 值仍将被正确检索。

如果您使用数组来存储信息，那么删除同时具有父项和子项的项目将非常困难，并且更新 lft 和 rgt 值也将非常困难。最后向数组添加大集合（子树）也将非常困难。

树确实是存储此类分层数据的理想方式。它模仿了我们的集合概念。问题是，虽然 PHP 可以轻松地存储树，但 MySQL 却不能，因此我们需要完成修改后的先序树遍历的所有困难工作，以便从 PHP 树中提取信息，以便我们可以将其存储在 MySQL 数据库中。

Answer 2

一个带有 Node 和 Tree 对象的简单运行程序。闲话少说，女士们先生们，代码如下：

<?php
#Create a node class
#-----------------------------------------------------------------------------
class Node
{
    #The node properties
    public $value;
    public $leftChild;
    public $rightChild;

    #Set the properties for the node
    public function set_value($passedValue)
    {
        $this->value = $passedValue;
    }

    public function set_left_child($passedChild)
    {
        $this->leftChild = $passedChild;
    }

    public function set_right_child($passedChild)
    {
        $this->rightChild = $passedChild;
    }

    #Get the properties for the node
    public function get_value()
    {
        return $this->value;
    }

    public function get_left_child()
    {
        return $this->leftChild;
    }

    public function get_right_child()
    {
        return $this->rightChild;
    }
}





#Create a tree class with a function to transverse the node
#-----------------------------------------------------------------------------
class Tree
{
    #The node properties
    public $treeNodes = array();
    public $preorderedNodes = array();
    public $nodeArray = array();

    #Set the tree nodes from the passed array
    public function set_tree_nodes($nodeArray)
    {
        $this->nodeArray = $nodeArray;
        #Set each node with its children based on the passed array
        foreach($this->nodeArray AS $node) array_push($this->treeNodes, $this->set_node_object($node));
    }


    public function set_node_object($node)
    {
        $nodeObject = new Node();
        $nodeObject->set_value($node['value']);
        if(!empty($node['left_child'])) $nodeObject->set_left_child($this->nodeArray[$node['left_child']]);
        if(!empty($node['right_child'])) $nodeObject->set_right_child($this->nodeArray[$node['right_child']]);

        return $nodeObject;
    }

    #perfom a preorder transversal on the tree and return the tree nodes in the expected order
    public function do_preorder_transversal($node)
    {
        #If the node is empty, end the recursion
        if(empty($node)) return $this->preorderedNodes;
        #Start the transversal
        if($node == 'head' && !empty($this->treeNodes[0])) $node=$this->treeNodes[0]; 

        #Add the node to the pre-ordered node list
        array_push($this->preorderedNodes, $node);

        $leftChild = $node->get_left_child(); 
        $rightChild = $node->get_right_child(); 
        if(!empty($leftChild)) $this->do_preorder_transversal($this->set_node_object($leftChild));
        if(!empty($rightChild)) $this->do_preorder_transversal($this->set_node_object($rightChild));
    }


    #Get the preordered nodes
    public function get_preordered_nodes()
    {
        return $this->preorderedNodes;
    }
}









#-----------------------------------------------------------------------------
# Test the objects
#-----------------------------------------------------------------------------
#Call the class in an example
$sampleTree = new Tree();

$seedData = array();
#Seed data array is in the format [value, [key to left child], [key to right child]]
$seedData[0] = array('value'=>2, 'left_child'=>1, 'right_child'=>2);
$seedData[1] = array('value'=>7, 'left_child'=>3, 'right_child'=>4);
$seedData[2] = array('value'=>5, 'left_child'=>'', 'right_child'=>7);
$seedData[3] = array('value'=>2, 'left_child'=>'', 'right_child'=>'');
$seedData[4] = array('value'=>6, 'left_child'=>5, 'right_child'=>6);
$seedData[5] = array('value'=>5, 'left_child'=>'', 'right_child'=>'');
$seedData[6] = array('value'=>11, 'left_child'=>'', 'right_child'=>'');
$seedData[7] = array('value'=>9, 'left_child'=>8, 'right_child'=>'');
$seedData[8] = array('value'=>4, 'left_child'=>'', 'right_child'=>'');

$sampleTree->set_tree_nodes($seedData);
#Create the root node to start the tree transversal
$sampleTree->do_preorder_transversal('head');

#Now get the preordered nodes and print out their values
$preordered = $sampleTree->get_preordered_nodes();
foreach($preordered AS $count=>$node) echo "<BR>[".$count."] ".$node->get_value();
?>

结果如下：

[0] 2

[1] 7

[2] 2

[3] 6

[4] 5

[5] 11

[6] 5

[7 ] 9

[8] 4

Answer 3

这是我在 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
?>