在PHP中将数组作为树形结构遍历

Question

我有一个描述层次结构的数据库表。以下是其结构：

。

 id | pid | uid 
  1    5     2
  2    2     3
  3    2     4
  4    2     6
  5    3     7

在树形结构中，它看起来是这样的。这只是一个例子，可能会有更多的节点。

         2 
      /  |  \
     3   4   6
    /      
   7 

在php和mysql中，我提取所有这些数据并将其保存到数组中。

我想遍历该数组以确定例如特定级别中id的数量，并且我希望能够检索来自一个级别的所有节点。

我如何在php中实现呢？

编辑

这是我创建数组的方式：

foreach ( $resultSet as $row ) {
    $entry = array();
    $entry['id'] = $row->id;
    $entry['uid'] = $row->uid;
    $entry['rid'] = $row->rid;
    $entry['date'] = $row->date;
    $entries [] = $entry;
}

现在我使用答案创建树的方法如下：

$tree = array();
foreach($entries as $key){
   $this->adj_tree($tree, $key);
}
return $tree;

但是当我打印$tree时，输出了一些奇怪的内容。

Array ( [24] => Array ( [id] => 6 [uid] => 24 [rid] => 83 [date] => 2011-06-15
17:54:14 ) [] => Array ( [_children] => Array ( [0] => Array ( [id] => 6 [uid] => 24 
[rid] => 83 [date] => 2011-06-15 17:54:14 ) [1] => Array ( [id] => 6 [uid] => 24 [rid] =>
83 [date] => 2011-06-15 17:54:14 ) ) ) ) 

实际上，应该有一个父级带有uid 24和两个子级带有rid 82和83

- DarkLeafyGreen

---

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html - dynamic

你是不知道如何在PHP中完成它？还是你不知道该如何在任何编程语言中完成它？ - dynamic

@yes123 你应该把那个变成一个答案。 ;) - Yoshi

可能是在MySQL中检索具有分层结构的数据的重复问题。 - NikiC

我会将数组制作为 $tree[$row['pid']][] = $row（而不是 $tree[] = $row），这样可以更轻松地检索任何节点的所有子节点。 - binaryLV

Answer 1

你没有说明你如何使用你的表格，但我猜想它是用于存储类别树或类似的东西，即一个不需要复杂存储的小数据集。你可以一次读取整个表格，并使用php动态构建树形结构。步骤如下：

function adj_tree(&$tree, $item) {
    $i = $item['uid'];
    $p = $item['pid'];
    $tree[$i] = isset($tree[$i]) ? $item + $tree[$i] : $item;
    $tree[$p]['_children'][] = &$tree[$i];
}

例子：

$tree = array();
$rs = my_query("SELECT * FROM categories");
while($row = my_fetch($rs))
    adj_tree($tree, $row);

在最后，你会得到一个包含每个项的'_children'子数组的项目数组，这个子数组又包含对其他项的引用（或为空）。

完整示例，使用来自问题的数据。

$entries = array(
  array('id' => 1, 'pid' => 5, 'uid' => 2),
  array('id' => 2, 'pid' => 2, 'uid' => 3),
  array('id' => 3, 'pid' => 2, 'uid' => 4),
  array('id' => 4, 'pid' => 2, 'uid' => 6),
  array('id' => 5, 'pid' => 3, 'uid' => 7),
);

$tree = array();
foreach($entries as $row)
    adj_tree($tree, $row);

function print_tree($node, $indent) {
    echo str_repeat('...', $indent) . $node['uid'], "<br>\n";
    if(isset($node['_children']))
        foreach($node['_children'] as $child)
            print_tree($child, $indent + 1);
}

print_tree($tree[2], 0);

- user187291

---

谢谢，我尝试了你的例子，但是输出有些奇怪，请看一下我的编辑。我使用我的表格作为一个引用系统，用户可以招募其他用户。 - DarkLeafyGreen

请问您能否解释一下这段代码的具体作用？$tree[$i] = isset($tree[$i]) ? $item + $tree[$i] : $item; 谢谢。 - themhz

Answer 2

与其他面向对象的语言一样，创建适合您需求的树和节点类。

另一种方法是使用数组创建树（在PHP中，数组是关联的并且可以嵌套）。

我同意Vinicius Kamakura的观点 - 如果数据集非常大，您不应将数据加载到PHP中。

- Daimon

Answer 3

我基于user187291的答案构建了一个类。

class Tree
{
    protected $tree;
    protected $rootid;

    public function __construct($entries)
    {
        $this->tree = array();
        $this->rootid = PHP_INT_MAX;

        /* Build tree under each node */
        foreach($entries as $node)
            $this->buildTree($this->tree, $node);
    }


    /* Build tree */
    protected function buildTree(&$tree, $node) 
    {
        $i = $node['id'];
        $p = $node['pid'];
        $this->rootid = min($this->rootid, $p);
        $tree[$i] = isset($tree[$i]) ? $node + $tree[$i] : $node;
        $tree[$p]['_children'][] = &$tree[$i];
    }


    /* Print tree */
    public function printTree() 
    {
        $this->printSubtree($this->tree[$this->rootid]);
    }


    /* Print subtree under given node */
    protected function printSubtree($node, $depth=0) 
    {
        /* Root node doesn't have id */
        if(isset($node['id']))
        {
            echo str_repeat('...', $depth) . $node['id'], "<br>\n";
        }

        /* Explore children */
        if(isset($node['_children']))
        {
            foreach($node['_children'] as $child)
                $this->printSubtree($child, $depth + 1);
        }
    }


    /* Destroy instance data */
    public function __destruct() 
    {
        $this->tree = null;
    }
}

使用示例

$entries = array(
  array('pid' => 2, 'id' => 3),
  array('pid' => 0, 'id' => 2),
  array('pid' => 3, 'id' => 7),
  array('pid' => 2, 'id' => 4),
  array('pid' => 2, 'id' => 6),
  array('pid' => 3, 'id' => 8),
  array('pid' => 0, 'id' => 9),
);

$tree = new Tree($entries);
$tree->printTree();

希望能对某些人有所帮助。当然，您可以向“entries”元素添加字段，只需记得如果要打印它们，则更改“printSubtree”方法。

注意事项： 该类假定节点具有“id”和“pid”的数字值，并且父节点的“id”比其子节点低（这在树结构中很常见）。

- Giorgio