[php] 일련의 부모-자식 관계를 계층 적 트리로 변환 하시겠습니까?

가능한 한 적은 수의 계층 구조 트리 구조로 바꾸고 싶은 이름-부모 이름 쌍이 많이 있습니다. 예를 들어 다음과 같은 쌍이 될 수 있습니다.

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 쌍을 포함하는 배열에서 Nested 세트로 이동할 수 <ul>있습니까?

재귀가 관련되어 있다는 느낌이 있지만 충분히 생각할 수는 없습니다.

답변

이를 위해서는 자식 / 부모 쌍을 트리 구조로 구문 분석하는 매우 기본적인 재귀 함수와이를 인쇄하기위한 또 다른 재귀 함수가 필요합니다. 하나의 기능만으로 충분하지만 명확성을 위해 두 가지가 있습니다 (이 답변의 끝에 결합 된 기능이 있습니다).

먼저 자식 / 부모 쌍의 배열을 초기화합니다.

$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 번의 반복 만 저장하지만 더 큰 세트에서는 차이를 만들 수 있습니다.

답변

트리를 만드는 또 다른 함수 (재귀가 필요하지 않고 대신 참조를 사용함) :

$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 목록으로 쉽게 인쇄 할 수 있습니다.

답변

의 플랫 구조를 $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 “딜레마”를 항상 해결하고 싶었습니다. 딜레마는 각 항목이 자식이 후속 조치를 취할 것인지 또는 닫아야하는 선행 요소의 수를 알지 못한다는 것입니다. 또 다른 대답에서 나는 이미 a를 사용하고 내가 작성한 다른 메타 정보를 RecursiveIteratorIterator찾아서 해결했습니다 . 중첩 된 세트 모델을 “닫힌”하위 트리 로 가져 오기 . 그 대답 은 반복자를 사용하면 매우 유연하다는 것을 보여줍니다.getDepth()Iterator<ul>

그러나 이것은 미리 정렬 된 목록이므로 귀하의 예에는 적합하지 않을 것입니다. 또한 나는 항상 일종의 표준 트리 구조와 HTML <ul>및 <li>요소에 대해 이것을 해결하고 싶었습니다 .

내가 생각 해낸 기본 개념은 다음과 같습니다.

TreeNode-각 요소를 TreeNode값 (예 🙂 Name과 자식이 있는지 여부를 제공 할 수 있는 간단한 유형 으로 추상화합니다 .
TreeNodesIterator– RecursiveIterator이 세트 (배열)를 반복 할 수 있습니다 TreeNodes. TreeNode유형이 이미 자식이 있는지, 어떤 자식이 있는지 알고 있기 때문에 매우 간단 합니다.
RecursiveListIterator-다음 RecursiveIteratorIterator과 같은 유형을 반복적으로 반복 할 때 필요한 모든 이벤트가 있는 A 입니다 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);

이것은 RecursiveListIteratorA는 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 루프 내의 스위치 / 케이스가 이벤트를 처리 할 수 있습니다.

답변

음, 먼저 키-값 쌍의 직선 배열을 계층 배열로 바꿉니다.

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

답변

하지만 알렉산더 – 콘스탄티노 프 의 솔루션은 처음에는 쉽게 읽을으로 보이지 않을 수도 있습니다, 그것은 천재 기하 급수적으로 더 나은 성능의 측면에서,이 있었어야 최고의 답변으로 투표를 모두입니다.

감사합니다 친구,이 게시물에 제시된 두 가지 솔루션을 비교하기 위해 벤치 마크를 만들었습니다.

나는 변환해야하는 6 개의 레벨을 가진 @ 250k 플랫 트리를 가지고 있었고 더 나은 방법을 찾고 재귀 반복을 피했습니다.

재귀 대 참조 :

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

답변

UL 및 LI로 구문 분석하려면 다음과 같습니다.

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

하지만 어레이를 자주 반복 할 필요가없는 솔루션을보고 싶습니다.

답변

내가 생각 해낸 것입니다.

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