将一系列父子关系转换为分层树？

Question

将一系列父子关系转换为分层树？

109

我有很多名称-父名称的对，我希望将它们转化为尽可能少的层级树结构。例如，这些可能是配对：

Child : Parent
    H : G
    F : G
    G : D
    E : D
    A : E
    B : C
    C : E
    D : NULL

需要转换为（一个）层次树：

D
├── E
│   ├── A
│   │   └── B
│   └── C   
└── G
    ├── F
    └── H

我想要的最终结果是嵌套的一组 <ul> 元素，每个 <li> 包含子项的名称。

这些配对没有任何不一致之处（子项是其自身的父项，父项是子项的子项等），因此可能可以进行大量的优化。

在 PHP 中，如何从包含子项=>父项配对的数组中转换为一组嵌套的 <ul>？

我有一种感觉需要使用递归，但我的头脑还不够清醒。

- Eric

11个回答

64

又一个制作树形结构的函数（不涉及递归，使用引用）：

$array = array('H' => 'G', 'F' => 'G', ..., 'D' => null);

function to_tree($array)
{
    $flat = array();
    $tree = array();

    foreach ($array as $child => $parent) {
        if (!isset($flat[$child])) {
            $flat[$child] = array();
        }
        if (!empty($parent)) {
            $flat[$parent][$child] =& $flat[$child];
        } else {
            $tree[$child] =& $flat[$child];
        }
    }

    return $tree;
}

返回一个类似于这样的分层数组：

Array(
    [D] => Array(
        [G] => Array(
            [H] => Array()
            [F] => Array()
        )
        ...
    )
)

可以使用递归函数轻松地将其打印为 HTML 列表。

- Alexander Konstantinov

+1 - 非常聪明。虽然我认为递归解决方案更合乎逻辑，但我确实更喜欢你的函数输出格式。 - Eric

@Eric 更加合乎逻辑？我不这么认为。递归中没有任何“逻辑”可言；相反，解析递归函数/调用会带来严重的认知负担。如果没有显式的堆栈分配，我每天都会选择迭代而不是递归。 - user719662

下面对该解决方案进行基准测试。 - Eric

29

将 $tree 中的扁平结构转换为层次结构的另一种更简化的方法。只需要一个临时数组就可以实现：

// add children to parents
$flat = array(); # temporary array
foreach ($tree as $name => $parent)
{
    $flat[$name]['name'] = $name; # self
    if (NULL === $parent)
    {
        # no parent, is root element, assign it to $tree
        $tree = &$flat[$name]; 
    }
    else
    {
        # has parent, add self as child    
        $flat[$parent]['children'][] = &$flat[$name];
    }
}
unset($flat);

以上就是将层次结构转换为多维数组的全部内容：

Array
(
    [children] => Array
        (
            [0] => Array
                (
                    [children] => Array
                        (
                            [0] => Array
                                (
                                    [name] => H
                                )

                            [1] => Array
                                (
                                    [name] => F
                                )

                        )

                    [name] => G
                )

            [1] => Array
                (
                    [name] => E
                    [children] => Array
                        (
                            [0] => Array
                                (
                                    [name] => A
                                )

                            [1] => Array
                                (
                                    [children] => Array
                                        (
                                            [0] => Array
                                                (
                                                    [name] => B
                                                )

                                        )

                                    [name] => C
                                )

                        )

                )

        )

    [name] => D
)

如果你想避免递归（对于大型结构可能是负担），输出就不那么琐碎了。

我一直想解决 UL/LI "困境"，以输出数组。问题在于，每个项目都不知道是否会有子项跟进或需要关闭多少之前的元素。在另一个答案中，我已经通过使用 RecursiveIteratorIterator 和查找 getDepth() 等元信息来解决了这个问题，并提供了自己编写的 Iterator：Getting nested set model into a <ul> but hiding “closed” subtrees。该答案还显示使用迭代器非常灵活。

但是，那是一个预排序列表，因此不适合您的示例。此外，我一直想为标准树结构和 HTML 的 <ul> 和 <li> 元素解决这个问题。

我提出的基本概念如下：

TreeNode - 将每个元素抽象成一个简单的 TreeNode 类型，可以提供其值（例如 Name）以及它是否具有子项。
TreeNodesIterator - 一个能够迭代一组（数组）这些 TreeNodes 的 RecursiveIterator。这很简单，因为 TreeNode 类型已经知道它是否有子项以及哪些子项。
RecursiveListIterator - 一个具有递归迭代任何类型的 RecursiveIterator 所需的所有事件的 RecursiveIteratorIterator：
- beginIteration / endIteration - 主列表的开始和结束。
- beginElement / endElement - 每个元素的开始和结束。
- beginChildren / endChildren - 每个子列表的开始和结束。
此 RecursiveListIterator 仅以函数调用的形式提供这些事件。作为 <ul><li> 列表的典型特征，子列表在其父 <li> 元素内打开和关闭。因此，endElement 事件在相应的 endChildren 事件之后触发。这可以更改或配置为扩大类的使用范围。然后，将事件分配为函数调用到装饰器对象中，以保持事物分开。
ListDecorator - 一个“装饰器”类，只是 RecursiveListIterator 事件的接收器。

我从主要的输出逻辑开始。考虑到现在是分层的 $tree 数组，最终代码如下：

$root = new TreeNode($tree);
$it = new TreeNodesIterator(array($root));
$rit = new RecursiveListIterator($it);
$decor = new ListDecorator($rit);
$rit->addDecorator($decor);

foreach($rit as $item)
{
    $inset = $decor->inset(1);
    printf("%s%s\n", $inset, $item->getName());
}

首先，让我们来看一下ListDecorator，它简单地包装了<ul>和<li>元素，并决定列表结构的输出：

class ListDecorator
{
    private $iterator;
    public function __construct(RecursiveListIterator $iterator)
    {
        $this->iterator = $iterator;
    }
    public function inset($add = 0)
    {
        return str_repeat('  ', $this->iterator->getDepth()*2+$add);
    }

构造函数接受其正在处理的列表迭代器。 "inset"只是一个用于输出缩进的辅助函数。其余部分只是每个事件的输出函数：

构造函数接受其正在处理的列表迭代器。 inset 只是一个用于输出缩进的辅助函数。其余部分只是每个事件的输出函数：

    public function beginElement()
    {
        printf("%s<li>\n", $this->inset());
    }
    public function endElement()
    {
        printf("%s</li>\n", $this->inset());
    }
    public function beginChildren()
    {
        printf("%s<ul>\n", $this->inset(-1));
    }
    public function endChildren()
    {
        printf("%s</ul>\n", $this->inset(-1));
    }
    public function beginIteration()
    {
        printf("%s<ul>\n", $this->inset());
    }
    public function endIteration()
    {
        printf("%s</ul>\n", $this->inset());
    }
}

考虑到这些输出函数，这是主要的输出包装/循环，我会逐步地介绍它：

$root = new TreeNode($tree);

创建根TreeNode，它将用于开始迭代：

$it = new TreeNodesIterator(array($root));

这个 TreeNodesIterator 是一个 RecursiveIterator，它可以使得单个 $root 节点进行递归迭代。它作为数组传递是因为该类需要一些东西进行迭代，并允许重用具有一组子节点的数组，这些子节点也是 TreeNode 元素的数组。

$rit = new RecursiveListIterator($it);

这个 RecursiveListIterator 是一个提供了上述事件的 RecursiveIteratorIterator。要使用它，只需要提供一个 ListDecorator（即上面提到的类），并使用 addDecorator 进行赋值：

$decor = new ListDecorator($rit);
$rit->addDecorator($decor);

然后一切都设置好了，只需使用foreach循环遍历它并输出每个节点:

foreach($rit as $item)
{
    $inset = $decor->inset(1);
    printf("%s%s\n", $inset, $item->getName());
}

正如这个示例所显示的那样，整个输出逻辑被封装在ListDecorator类和这个单独的foreach中。整个递归遍历已经完全封装到了SPL递归迭代器中，它们提供了一个堆栈过程，也就是说，在内部没有递归函数调用。

基于事件的ListDecorator允许您特定地修改输出，并为相同的数据结构提供多种类型的列表。甚至可以更改输入，因为数组数据已经封装到了TreeNode中。

完整代码示例：

<?php
namespace My;

$tree = array('H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null);

// add children to parents
$flat = array(); # temporary array
foreach ($tree as $name => $parent)
{
    $flat[$name]['name'] = $name; # self
    if (NULL === $parent)
    {
        # no parent, is root element, assign it to $tree
        $tree = &$flat[$name];
    }
    else
    {
        # has parent, add self as child    
        $flat[$parent]['children'][] = &$flat[$name];
    }
}
unset($flat);

class TreeNode
{
    protected $data;
    public function __construct(array $element)
    {
        if (!isset($element['name']))
            throw new InvalidArgumentException('Element has no name.');

        if (isset($element['children']) && !is_array($element['children']))
            throw new InvalidArgumentException('Element has invalid children.');

        $this->data = $element;
    }
    public function getName()
    {
         return $this->data['name'];
    }
    public function hasChildren()
    {
        return isset($this->data['children']) && count($this->data['children']);
    }
    /**
     * @return array of child TreeNode elements 
     */
    public function getChildren()
    {        
        $children = $this->hasChildren() ? $this->data['children'] : array();
        $class = get_called_class();
        foreach($children as &$element)
        {
            $element = new $class($element);
        }
        unset($element);        
        return $children;
    }
}

class TreeNodesIterator implements \RecursiveIterator
{
    private $nodes;
    public function __construct(array $nodes)
    {
        $this->nodes = new \ArrayIterator($nodes);
    }
    public function  getInnerIterator()
    {
        return $this->nodes;
    }
    public function getChildren()
    {
        return new TreeNodesIterator($this->nodes->current()->getChildren());
    }
    public function hasChildren()
    {
        return $this->nodes->current()->hasChildren();
    }
    public function rewind()
    {
        $this->nodes->rewind();
    }
    public function valid()
    {
        return $this->nodes->valid();
    }   
    public function current()
    {
        return $this->nodes->current();
    }
    public function key()
    {
        return $this->nodes->key();
    }
    public function next()
    {
        return $this->nodes->next();
    }
}

class RecursiveListIterator extends \RecursiveIteratorIterator
{
    private $elements;
    /**
     * @var ListDecorator
     */
    private $decorator;
    public function addDecorator(ListDecorator $decorator)
    {
        $this->decorator = $decorator;
    }
    public function __construct($iterator, $mode = \RecursiveIteratorIterator::SELF_FIRST, $flags = 0)
    {
        parent::__construct($iterator, $mode, $flags);
    }
    private function event($name)
    {
        // event debug code: printf("--- %'.-20s --- (Depth: %d, Element: %d)\n", $name, $this->getDepth(), @$this->elements[$this->getDepth()]);
        $callback = array($this->decorator, $name);
        is_callable($callback) && call_user_func($callback);
    }
    public function beginElement()
    {
        $this->event('beginElement');
    }
    public function beginChildren()
    {
        $this->event('beginChildren');
    }
    public function endChildren()
    {
        $this->testEndElement();
        $this->event('endChildren');
    }
    private function testEndElement($depthOffset = 0)
    {
        $depth = $this->getDepth() + $depthOffset;      
        isset($this->elements[$depth]) || $this->elements[$depth] = 0;
        $this->elements[$depth] && $this->event('endElement');

    }
    public function nextElement()
    {
        $this->testEndElement();
        $this->event('{nextElement}');
        $this->event('beginElement');       
        $this->elements[$this->getDepth()] = 1;
    } 
    public function beginIteration()
    {
        $this->event('beginIteration');
    }
    public function endIteration()
    {
        $this->testEndElement();
        $this->event('endIteration');       
    }
}

class ListDecorator
{
    private $iterator;
    public function __construct(RecursiveListIterator $iterator)
    {
        $this->iterator = $iterator;
    }
    public function inset($add = 0)
    {
        return str_repeat('  ', $this->iterator->getDepth()*2+$add);
    }
    public function beginElement()
    {
        printf("%s<li>\n", $this->inset(1));
    }
    public function endElement()
    {
        printf("%s</li>\n", $this->inset(1));
    }
    public function beginChildren()
    {
        printf("%s<ul>\n", $this->inset());
    }
    public function endChildren()
    {
        printf("%s</ul>\n", $this->inset());
    }
    public function beginIteration()
    {
        printf("%s<ul>\n", $this->inset());
    }
    public function endIteration()
    {
        printf("%s</ul>\n", $this->inset());
    }
}


$root = new TreeNode($tree);
$it = new TreeNodesIterator(array($root));
$rit = new RecursiveListIterator($it);
$decor = new ListDecorator($rit);
$rit->addDecorator($decor);

foreach($rit as $item)
{
    $inset = $decor->inset(2);
    printf("%s%s\n", $inset, $item->getName());
}

输出:

<ul>
  <li>
    D
    <ul>
      <li>
        G
        <ul>
          <li>
            H
          </li>
          <li>
            F
          </li>
        </ul>
      </li>
      <li>
        E
        <ul>
          </li>
          <li>
            A
          </li>
          <li>
            C
            <ul>
              <li>
                B
              </li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

演示 (PHP 5.2 变体)

一个可能的变体是迭代器，它遍历任何 RecursiveIterator 并提供可以发生的所有事件的迭代。然后 foreach 循环内的 switch / case 将处理这些事件。

相关内容：

- hakre

3

尽管这个解决方案被称为“设计得很好”，但它究竟比之前的例子更简化了哪些内容呢？它似乎只是对同样问题的过度设计。 - Andre

@Andre：根据我所记的封装等级。在另一个相关答案中，我有一个完全非封装的代码片段，它更小，因此根据不同的观点可能会“更简化”。 - hakre

@hakre 我该如何修改“ListDecorator”类以将从树数组中获取的LI添加到'id'？ - Yatix

1

@Gangesh：最简单的方法是使用节点访问器。^^开个玩笑，直接的方法是扩展装饰器并编辑beginElement()，获取内部迭代器（例如，参见inset()方法）并处理id属性。 - hakre

@hakre 谢谢。我会尝试的。 - Yatix

12

虽然 Alexander-Konstantinov 的解决方案一开始可能不太容易阅读，但其天才性和性能指数级的提升使其应该被评为最佳答案。

感谢，老兄。我为了比较本篇文章中介绍的两种解决方案而以你的名字命名了一个基准测试。

我有一个包含6层节点和250k个元素的平面树需要转换，正在寻找更好的方法来避免递归迭代。

递归 vs 引用：

// Generate a 6 level flat tree
$root = null;
$lvl1 = 13;
$lvl2 = 11;
$lvl3 = 7;
$lvl4 = 5;
$lvl5 = 3;
$lvl6 = 1;    
$flatTree = [];
for ($i = 1; $i <= 450000; $i++) {
    if ($i % 3 == 0)  { $lvl5 = $i; $flatTree[$lvl6] = $lvl5; continue; }
    if ($i % 5 == 0)  { $lvl4 = $i; $flatTree[$lvl5] = $lvl4; continue; }
    if ($i % 7 == 0)  { $lvl3 = $i; $flatTree[$lvl3] = $lvl2; continue; }
    if ($i % 11 == 0) { $lvl2 = $i; $flatTree[$lvl2] = $lvl1; continue; }
    if ($i % 13 == 0) { $lvl1 = $i; $flatTree[$lvl1] = $root; continue; }
    $lvl6 = $i;
}

echo 'Array count: ', count($flatTree), PHP_EOL;

// Reference function
function treeByReference($flatTree)
{
    $flat = [];
    $tree = [];

    foreach ($flatTree as $child => $parent) {
        if (!isset($flat[$child])) {
            $flat[$child] = [];
        }
        if (!empty($parent)) {
            $flat[$parent][$child] =& $flat[$child];
        } else {
            $tree[$child] =& $flat[$child];
        }
    }

    return $tree;
}

// Recursion function
function treeByRecursion($flatTree, $root = null)
{
    $return = [];
    foreach($flatTree as $child => $parent) {
        if ($parent == $root) {
            unset($flatTree[$child]);
            $return[$child] = treeByRecursion($flatTree, $child);
        }
    }
    return $return ?: [];
}

// Benchmark reference
$t1 = microtime(true);
$tree = treeByReference($flatTree);
echo 'Reference: ', (microtime(true) - $t1), PHP_EOL;

// Benchmark recursion
$t2 = microtime(true);
$tree = treeByRecursion($flatTree);
echo 'Recursion: ', (microtime(true) - $t2), PHP_EOL;

成果证明一切：

Array count: 255493
Reference: 0.3259289264679 (less than 0.4s)
Recursion: 6604.9865279198 (almost 2h)

- ntt

9

首先，我会将键值对的普通数组转换为层次化数组。

function convertToHeiarchical(array $input) {
    $parents = array();
    $root = array();
    $children = array();
    foreach ($input as $item) {
        $parents[$item['id']] = &$item;
        if ($item['parent_id']) {
            if (!isset($children[$item['parent_id']])) {
                $children[$item['parent_id']] = array();
            }
            $children[$item['parent_id']][] = &$item;
        } else {
            $root = $item['id'];
        }
    }
    foreach ($parents as $id => &$item) {
        if (isset($children[$id])) {
            $item['children'] = $children[$id];
        } else {
            $item['children'] = array();
        }
    }
    return $parents[$root];
}

那可以将带有parent_id和id的平面数组转换为分层结构：

$item = array(
    'id' => 'A',
    'blah' => 'blah',
    'children' => array(
        array(
            'id' => 'B',
            'blah' => 'blah',
            'children' => array(
                array(
                    'id' => 'C',
                    'blah' => 'blah',
                    'children' => array(),
                ),
             ),
            'id' => 'D',
            'blah' => 'blah',
            'children' => array(
                array(
                    'id' => 'E',
                    'blah' => 'blah',
                    'children' => array(),
                ),
            ),
        ),
    ),
);

然后，只需创建一个渲染函数：

function renderItem($item) {
    $out = "Your OUtput For Each Item Here";
    $out .= "<ul>";
    foreach ($item['children'] as $child) {
        $out .= "<li>".renderItem($child)."</li>";
    }
    $out .= "</ul>";
    return $out;
}

- ircmaxell

2

好的，要解析为无序列表和列表项，可以使用以下代码：

$array = array (
    'H' => 'G'
    'F' => 'G'
    'G' => 'D'
    'E' => 'D'
    'A' => 'E'
    'B' => 'C'
    'C' => 'E'
    'D' => 'NULL'
);


recurse_uls ($array, 'NULL');

function recurse_uls ($array, $parent)
{
    echo '<ul>';
    foreach ($array as $c => $p)  {
        if ($p != $parent) continue;
        echo '<li>'.$c.'</li>';
        recurse_uls ($array, $c);
    }
    echo '</ul>';
}

但我希望看到一种不需要你经常遍历数组的解决方案...

- arnorhs

2

以下是我想到的内容：

$arr = array(
            'H' => 'G',
            'F' => 'G',
            'G' => 'D',
            'E' => 'D',
            'A' => 'E',
            'B' => 'C',
            'C' => 'E',
            'D' => null );

    $nested = parentChild($arr);
    print_r($nested);

    function parentChild(&$arr, $parent = false) {
      if( !$parent) { //initial call
         $rootKey = array_search( null, $arr);
         return array($rootKey => parentChild($arr, $rootKey));
      }else { // recursing through
        $keys = array_keys($arr, $parent);
        $piece = array();
        if($keys) { // found children, so handle them
          if( !is_array($keys) ) { // only one child
            $piece = parentChild($arr, $keys);
           }else{ // multiple children
             foreach( $keys as $key ){
               $piece[$key] = parentChild($arr, $key);
             }
           }
        }else {
           return $parent; //return the main tag (no kids)
        }
        return $piece; // return the array built via recursion
      }
    }

输出：

Array
(
    [D] => Array
        (
            [G] => Array
                (
                    [H] => H
                    [F] => F
                )

            [E] => Array
                (
                    [A] => A
                    [C] => Array
                        (
                            [B] => B
                        )    
                )    
        )    
)

- Dan Heberden

2

父子关系嵌套数组
从数据库中获取所有记录并创建嵌套数组。

$data = SampleTable::find()->all();
$tree = buildTree($data);
print_r($tree);

public function buildTree(array $elements, $parentId = 0) {
    $branch = array();
    foreach ($elements as $element) {
        if ($element['iParentId'] == $parentId) {
            $children =buildTree($elements, $element['iCategoriesId']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[] = $element;
        }
    }
    return $branch;
}

在JSON格式中打印类别和子类别数据

public static function buildTree(array $elements, $parentId = 0){
    $branch = array();
    foreach($elements as $element){
        if($element['iParentId']==$parentId){
            $children =buildTree($elements, $element['iCategoriesId']);
            if ($children) {
                $element['children'] = $children;

            }
                $branch[] = array(
                    'iCategoriesId' => $element->iCategoriesId,
                    'iParentId'=>$element->iParentId,
                    'vCategoriesName'=>$element->vCategoriesName,
                    'children'=>$element->children,
            );
        }
    }
    return[
        $branch
    ];
}

- Akshay Mistry

0

$tree = array(
    'H' => 'G',
    'F' => 'G',
    'G' => 'D',
    'E' => 'D',
    'A' => 'E',
    'B' => 'C',
    'C' => 'E',
    'D' => null,
    'Z' => null,
    'MM' =>'Z',
    'KK' =>'Z',
    'MMM' =>'MM',
    // 'MM'=>'DDD'
);

$aa=$this->parseTree($tree);

public function get_tress($tree,$key)
{

    $x=array();
    foreach ($tree as $keys => $value) {
        if($value==$key){
        $x[]=($keys);
        }
    }
    echo "<li>";
    foreach ($x as $ke => $val) {
    echo "<ul>";
        echo($val);
        $this->get_tress($tree,$val);
    echo "</ul>";
    }
    echo "</li>";


}
function parseTree($tree, $root = null) {

    foreach ($tree as $key => $value) {
        if($value==$root){

            echo "<ul>";
            echo($key);
            $this->get_tress($tree,$key);
            echo "</ul>";
        }
    }

- Bharat

0

虽然这是一个老问题，但我也不得不做这个，使用递归的示例让我头疼。在我的数据库中，我们有一个locations表，它有一个loca_id PK（子）和自引用的loca_parent_id（父）。

目的是在HTML中表示此结构。简单的查询当然可以按固定顺序返回数据，但我发现这样的数据展示方式不够自然。我真正想要的是使用LEVEL进行Oracle树遍历处理以帮助显示。

我决定使用“路径”的想法来唯一标识每个条目。例如：

通过路径对数组进行排序应该更容易处理，以便进行有意义的显示。

我意识到使用关联数组和排序是作弊的，因为它隐藏了操作的递归复杂性，但对我来说，这看起来更简单：

<table>
<?php
    
    $sql = "
    
    SELECT l.*,
           pl.loca_name parent_loca_name,
           '' loca_path
    FROM locations l
    LEFT JOIN locations pl ON l.loca_parent_id = pl.loca_id
    ORDER BY l.loca_parent_id, l.loca_id
    
    ";
    
    function print_row ( $rowdata )
    {
    ?>
                      <tr>
                          <td>
                              <?=$rowdata['loca_id']?>
                          </td>
                          <td>
                              <?=$rowdata['loca_path']?>
                          </td>
                          <td>
                              <?=$rowdata['loca_type']?>
                          </td>
                          <td>
                              <?=$rowdata['loca_status']?>
                          </td>
                      </tr>
    <?php
    
    }
    
    $stmt  = $dbh->prepare($sql);
    $stmt->execute();
    $result = $stmt->get_result();
    $data = $result->fetch_all(MYSQLI_ASSOC);
    
    $printed = array();
    
    // To get tree hierarchy usually means recursion of data.
    // Here we will try to use an associate array and set a
    // 'path' value to represent the hierarchy tree in one
    // pass. Sorting this array by the path value should give
    // a nice tree order and reference.
// The array key will be the unique id (loca_id) for each row.
// The value for each key will the complete row from the database.
// The row contains a element 'loca_path' - we will write the path
// for each row here. A child's path will be parent_path/child_name.
// For any child we encounter with a parent we look up the parents path
// using the loca_parent_id as the key.
// Caveat, although tested quickly, just make sure that all parents are
// returned first by the query.
    
    foreach ($data as $row)
    {
    
       if ( $row['loca_parent_id'] == '' ) // Root Parent
       {
          $row['loca_path'] = $row['loca_name'] . '/';
          $printed[$row['loca_id']] = $row;
       }
       else // Child/Sub-Parent
       {
          $row['loca_path'] = $printed[$row['loca_parent_id']]['loca_path'] . $row['loca_name'] . '/';
          $printed[$row['loca_id']] = $row;
       }
    }
    
    // Array with paths built, now sort then print
    
    array_multisort(array_column($printed, 'loca_path'), SORT_ASC, $printed);
    
    foreach ( $printed as $prow )
    {
       print_row ( $prow );
    }
    ?>
    </table>

- TenG

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tatu Ulmanen · Accepted Answer

这需要一个非常基本的递归函数将子/父对解析为树形结构，并使用另一个递归函数打印它。虽然只需要一个函数，但以下是两个函数以增强清晰度（可以在本答案底部找到合并函数）。

首先初始化子/父对数组：

$tree = array(
    'H' => 'G',
    'F' => 'G',
    'G' => 'D',
    'E' => 'D',
    'A' => 'E',
    'B' => 'C',
    'C' => 'E',
    'D' => null
);

然后是将该数组解析为分层树形结构的函数：

function parseTree($tree, $root = null) {
    $return = array();
    # Traverse the tree and search for direct children of the root
    foreach($tree as $child => $parent) {
        # A direct child is found
        if($parent == $root) {
            # Remove item from tree (we don't need to traverse this again)
            unset($tree[$child]);
            # Append the child into result array and parse its children
            $return[] = array(
                'name' => $child,
                'children' => parseTree($tree, $child)
            );
        }
    }
    return empty($return) ? null : $return;    
}

还有一个遍历该树并打印出无序列表的函数:

function printTree($tree) {
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        foreach($tree as $node) {
            echo '<li>'.$node['name'];
            printTree($node['children']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

实际用途：

$result = parseTree($tree);
printTree($result);

这是$result的内容:

Array(
    [0] => Array(
        [name] => D
        [children] => Array(
            [0] => Array(
                [name] => G
                [children] => Array(
                    [0] => Array(
                        [name] => H
                        [children] => NULL
                    )
                    [1] => Array(
                        [name] => F
                        [children] => NULL
                    )
                )
            )
            [1] => Array(
                [name] => E
                [children] => Array(
                    [0] => Array(
                        [name] => A
                        [children] => NULL
                    )
                    [1] => Array(
                        [name] => C
                        [children] => Array(
                            [0] => Array(
                                [name] => B
                                [children] => NULL
                            )
                        )
                    )
                )
            )
        )
    )
)

如果您想要更高的效率，可以将这些函数合并为一个，减少迭代次数：

function parseAndPrintTree($root, $tree) {
    $return = array();
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        foreach($tree as $child => $parent) {
            if($parent == $root) {                    
                unset($tree[$child]);
                echo '<li>'.$child;
                parseAndPrintTree($child, $tree);
                echo '</li>';
            }
        }
        echo '</ul>';
    }
}

你只会在这样小的数据集上节省8次迭代，但在更大的数据集上可能会有所不同。