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

Question

我有一大堆的名字 - parentname对,我想转成少数heirarchical树形结构成为可能.例如,这些可能是配对:

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

需要转化为(a)层次结构树:

D
??? E
?   ??? A
?   ?   ??? B
?   ??? C   
??? G
    ??? F
    ??? H

我想要的最终结果是一组嵌套的<ul>元素,每个元素都<li>包含孩子的名字.

有在配对没有不一致(孩子是它自己的父母,父母是孩子的孩子,等等),所以一堆优化大概可以做.

在PHP中,我如何从包含child => parent对的数组转到一组嵌套<ul>s？

我有一种感觉,涉及到递归,但我还没有完全清醒地思考它.

Answer 1

这需要一个非常基本的递归函数来将子/父对解析为树结构,另一个递归函数将其打印出来.只有一个函数就足够了,但为了清楚起见,这里有两个函数(在这个答案的最后可以找到一个组合函数).

首先初始化子/父对的数组:

$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次迭代,但是在更大的集合上,它可能会有所不同.

Answer 2

还有另一个创建树的函数(不涉及递归,而是使用引用):

$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列表.

Answer 3

将平面结构$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提供的其他元信息解决了这个问题:将嵌套集模型转换为<ul>隐藏的"封闭"子树.那答案表演,以及与迭代器你是相当灵活的.

然而,这是一个预先排序的列表,因此不适合您的示例.另外,我一直想为一种标准树结构和HTML <ul>和<li>元素解决这个问题.

我提出的基本概念如下:

1. TreeNode- 将每个元素抽象为一个简单的TreeNode类型,可以提供它的价值(例如Name)以及它是否有孩子.
2. TreeNodesIterator- RecursiveIterator能够迭代这些集合(数组)的TreeNodes.这很简单,因为TreeNode类型已经知道它是否有孩子以及哪些孩子.
3. RecursiveListIterator- RecursiveIteratorIterator当它以递归方式迭代任何类型时,它具有所需的所有事件RecursiveIterator:
   • beginIteration/ endIteration- 主列表的开头和结尾.
   • beginElement/ endElement- 每个元素的开头和结尾.
   • beginChildren/ endChildren- 每个子项列表的开头和结尾.这RecursiveListIterator仅以函数调用的形式提供这些事件.子列表,因为它是典型的<ul><li>列表,在其父<li>元素内打开和关闭.因此,endElement事件在相应endChildren事件之后被触发.这可以更改或可配置以扩大此类的使用范围.事件作为函数调用分发给装饰器对象,然后将事物分开.
4. 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只是一个帮助函数,可以很好地缩进输出.其余的只是每个事件的输出函数:

    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());
}

Outpupt:

<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循环内的开关/案例可以处理事件.

有关:

• 带有RecursiveArrayIterator的嵌套列表
• RecursiveIteratorIterator类

Answer 4

好吧,首先我将键值对的直接数组转换为分层数组

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;
}

Answer 5

虽然亚历山大 - 康斯坦丁诺夫的解决方案起初可能看起来不那么容易,但就性能而言,它既是天才又是指数级的,这应该被认为是最好的答案.

谢谢你的配偶,我为你的荣誉做了一个基准,比较了这篇文章中提出的两个解决方案.

我有一个@ 250k平面树,有6个级别,我必须转换,我正在寻找一个更好的方法这样做,并避免递归迭代.

递归与参考:

// 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)