Ben ebeveyn-çocuk ilişkilerinde bir dizi nasıl bir hiyerarşik ağaç çevirebilirim?

6 Cevap php

Ben mümkün olduğunca az hiyerarşik ağaç yapılara dönüşmesi isterim ki, isim-ParentName çiftleri bir grup var. Yani, örneğin, bu eşleşmeleri olabilir:

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

Hangi (a) hiyerarşik ağacı (ler) 'e transforme edilmesi gerekmektedir:

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

İstediğim sonuç her <li> çocuğun adını içeren <ul> elemanlarının, iç içe geçmiş bir dizi.

Çiftlerinde hiçbir tutarsızlık yani optimizasyonlar bir demet muhtemelen yapılabilir, (çocuk ebeveyn vb, çocuğun çocuk olduğunu, bu kendi ebeveyn) vardır.

Nasıl, PHP, ben Yuvalanmış'ı <ul> s bir dizi, bir dizi içeren bir çocuk => ebeveyn çifti gitmek istiyorsunuz?

Ben özyineleme dahil olduğu bir duygu var, ama bunu düşünmek için yeterli oldukça uyanık değilim.

6 Cevap

Bu bir ağaç yapısı ve bunu yazdırmak için başka bir özyinelemeli işlev için çocuk / ana çiftleri ayrıştırmak için çok temel bir özyinelemeli işlev gerektirir. Sadece tek bir işlev yeterli ama burada açıklık için iki (kombine bir fonksiyonu bu cevabın sonunda bulunabilir) bulunuyor olacaktır.

Ilk çocuk / ebeveyn çiftlerinin dizisini başlatmak:

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

Sonra bir hiyerarşik ağaç yapısı içine dizi ayrıştırır fonksiyonu:

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

Ve Sırasız listesini yazdırmak için bu ağaç traversler bir işlev:

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

Ve gerçek kullanım:

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

Burada içerikleri bu $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
                            )
                        )
                    )
                )
            )
        )
    )
)

Eğer biraz daha fazla verimlilik istiyorsanız, birine bu fonksiyonlarını birleştiren ve yapılan iterasyon sayısını azaltabilir:

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

Sadece bu kadar küçük bir veri kümesi üzerinde 8 tekrarlamalar tasarruf edeceğiz ama daha büyük kümeler üzerinde bir fark yaratabilir.

Bir Ağacı yapmak için başka bir Fonksiyon (dahil hiçbir özyineleme yerine, referanslar kullanır):

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

Bu gibi bir hiyerarşik dizi döndürür:

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

Kolayca özyinelemeli işlevini kullanarak bir HTML liste olarak basılabilir hangi.

Başka, bir hiyerarşi içine $tree olarak düz bir yapıya dönüştürmek için daha basitleştirilmiş bir yoldur. Sadece tek bir geçici dizi maruz için gereklidir:

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

Bu çok boyutlu bir diziye hiyerarşi almak için hepsi:

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
)

Eğer Özyinelemeyi (büyük yapıları ile bir yük olabilir) kaçınmak istiyorsanız çıkışı daha az önemsiz değildir.

Ben her zaman bir dizi çıktısı için UL / LI "ikilemi" çözmek istiyordu. Ikilem her bir öğesi çocuklara takip ya da kaç önceki elemanlar kapalı olması gerekir olup olmadığını bilmiyor olmasıdır. Başka bir cevap ben zaten RecursiveIteratorIterator kullanarak ve getDepth() ve diğer meta-bilgi arıyorsanız benim kendi yazılı Iterator sağladığı o çözdü: {[(3) }] ancak gizleme altağaçlara . That answer de iteratörler ile oldukça esnek olduğunuzu gösterir "kapalı".

Bununla birlikte bu liste önceden kriteri olarak, bu nedenle, örneğin uygun olmaz. Ayrıca ben her zaman standart ağaç yapısı çeşit ve HTML'ın <ul> ve <li> öğeleri için bu çözmek istiyordu.

Ben geldi temel kavram aşağıdaki:

  1. TreeNode - Abstracts each element into a simple TreeNode o değer sağlayabilir yazın (örn: Name) ve çocukları olup olmadığını.
  2. TreeNodesIterator - A RecursiveIterator O bu TreeNodes kümesi (array) üzerinde yineleme yapabiliyor. O çocuğu var ve hangilerinin ise TreeNode zaten yazın bildiği gibi bu oldukça basittir.
  3. RecursiveListIterator - A RecursiveIteratorIterator that has all the events needed when it recursively iterate over any kind of RecursiveIterator:
    • beginIteration / endIteration - başlayın ve ana listenin sonunda.
    • beginElement / endElement - başlayın ve her elemanın sonu.
    • beginChildren / endChildren - Begin and end of each children list. This RecursiveListIterator only provides these events in a form of function calls. children lists, as it is typical for <ul><li> lists, are opened and closed inside it's parent <li> element. Therefore the endElement event is fired after the according endChildren event. This could be changed or made configurable to broaden the use this class. The events are distributed as function calls to a decorator object then, to keep things apart.
  4. ListDecorator - A "decorator" class that is just a receiver of the events of RecursiveListIterator.

Ben ana çıkış mantığı ile başlar. Şimdi hiyerarşik $tree dizi Taken, son kodu aşağıdaki gibi görünür:

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

Önce ListDecorator sadece <ul> ve <li> elemanları ve liste yapısı çıkış nasıl karar vermektir sarar içine bakalım:

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

Yapıcı bu üzerinde çalışıyor liste yineleyici alır. inset çıkışının güzel girinti için sadece bir yardımcı fonksiyonudur. Gerisi, her olay için sadece çıkış işlevleri şunlardır:

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

Akılda bu çıkış fonksiyonları ile, bu yine ana çıkış wrap-up / döngü, ben adım adım geçmesi:

$root = new TreeNode($tree);

: Kök TreeNode üzerine yineleme başlatmak için kullanılacak oluşturun

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

Bu TreeNodesIterator a RecursiveIterator tek $root düğüm üzerinde yinelemeli yineleme kılmasıdır. Bu sınıf üzerinde yineleme için bir şey gerekiyor ve aynı zamanda TreeNode elemanlarının bir dizi olan çocukların bir dizi ile yeniden kullanımını sağlar çünkü bir dizi olarak geçirilir.

$rit = new RecursiveListIterator($it);

Bu RecursiveListIterator a RecursiveIteratorIterator bahsedilen etkinlik sağlamasıdır. O faydalanmak için, sadece bir ListDecorator (yukarıda sınıfı) sağlanan ve tahsis gerekiyor addDecorator:

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

Sonra her şey bir set-up için sadece foreach her düğüm üzerinde ve çıkış:

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

Bu örnekte gösterildiği gibi, bütün çıkış lojik ListDecorator sınıfı ve bu tek foreach içinde kapsüllenir. Bütün özyinelemeli geçişi tamamen o içten Yinelemesiz fonksiyon çağrıları yapılır anlamına gelir, bir yığılmış prosedür sağlanan SPL özyinelemeli Yineleyicilerin kapsüllü olmuştur.

Tabanlı olay ListDecorator size özel çıktı değiştirmek için ve aynı veri yapısı için listeleri birden fazla tip sağlamak için sağlar. Dizi veri TreeNode içine kapsüllü olduğu gibi bu girişi değiştirmek bile mümkün.

Tam kod örneği:

<?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>

Demo (PHP 5.2 variant)

Olası bir varyantı herhangi bir RecursiveIterator üzerinde dolaşır ve oluşabilecek tüm olayların üzerinde bir yineleme sağlar bir yineleyici olacaktır. Foreach döngüsü içinde bir switch / case sonra olaylar ile anlaşma olabilir.

İlgili:

Eh, ilk olarak ben bir hiyerarşik diziye anahtar-değer çiftleri düz dizi açacak

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

Bu hiyerarşik birine parent_id ve kimliği ile düz bir dizi dönüştürebilirsiniz olacak:

$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(),
                ),
            ),
        ),
    ),
);

Daha sonra, sadece bir oluşturma işlevi oluşturun:

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

Burada ben ile geldi ne:

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

çıkışlar:

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

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

Peki, ULS ve lis içine ayrıştırmak için, bu gibi bir şey olurdu:

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

Ama sık sık dizi yineleme yapmak gerektirmeyen bir çözüm görmek isteriz ...

etiketler