首页猿问将一系列父子关系转换为层次树？

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

PHP

慕森卡 2019-06-28 16:46:38

将一系列父子关系转换为层次树？我有一堆名字-父母的名字对，我想变成尽可能少的传家宝树结构。例如，这些可能是配对：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中，我将如何从包含子=>父对的数组转到嵌套的一组<ul>是吗？我有一种感觉，递归涉及到，但我还没有完全清醒地考虑清楚。

查看完整描述

3 回答

慕慕森

TA贡献1856条经验获得超17个赞

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

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

$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次迭代，但是在更大的集合上，这可能会产生不同的效果。

反对回复 2019-06-28

四季花海

TA贡献1811条经验获得超5个赞

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

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

反对回复 2019-06-28

catspeake

TA贡献1111条经验获得超0个赞

另一种更简化的方法来转换$tree进入等级体系。只需要一个临时数组就可以公开它：

// add children to parents$flat = array(); # temporary arrayforeach ($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>元素。

我提出的基本概念如下：

TreeNode
-将每个元素抽象成一个简单的
TreeNode
可以提供它的值的类型(例如：
Name
)以及它是否有孩子。
TreeNodesIterator
-A
RecursiveIterator
可以迭代其中的一组(数组)
TreeNodes
..这相当简单，因为
TreeNode
类型已经知道它是否有孩子和哪个孩子。
RecursiveListIterator
-A
RecursiveIteratorIterator
当它递归地遍历任何类型的
RecursiveIterator:

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只是一个很好的输出缩进的助手函数。其余的只是每个事件的输出函数：

    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.

完整的代码示例：

<?phpnamespace 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 arrayforeach ($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>

演示(PHP5.2变体)

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

有关：

反对回复 2019-06-28

3 回答
0 关注
812 浏览

关注

添加回答

0/150

提交

取消

热搜

最近搜索清空

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

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

3 回答

添加回答