Построить дерево из плоского массива в PHP

Question

Я просмотрел интернет и не совсем нашел то, что искал. У меня есть плоский массив с каждым элементом, содержащим «id» и «parent_id». Каждый элемент будет иметь ОДНОГО родителя, но может иметь несколько дочерних элементов. Если parent_id = 0, он считается элементом корневого уровня. Я пытаюсь превратить мой плоский массив в дерево. Другие образцы, которые я обнаружил, только копируют элемент в родительский, но оригинал все еще существует.

EDIT

Каждый элемент начального массива читается из отдельного файла XML. Сам файл будет иметь значение «0» для parent_id, если у него нет родителя. Ключи на самом деле являются строками.

Прошу прощения за путаницу ранее. Надеюсь, это более понятно:

/ EDIT

Мой начальный массив:

Array
(
    [_319_] => Array
        (
            [id] => 0
            [parent_id] => 0
        )

    [_320_] => Array
        (
            [id] => _320_
            [parent_id] => 0
        )

    [_321_] => Array
        (
            [id] => _321_
            [parent_id] => _320_
        )

    [_322_] => Array
        (
            [id] => _322_
            [parent_id] => _321_
        )

    [_323_] => Array
        (
            [id] => _323_
            [parent_id] => 0
        )

    [_324_] => Array
        (
            [id] => _324_
            [parent_id] => _323_
        )

    [_325_] => Array
        (
            [id] => _325_
            [parent_id] => _320_
        )
)

Получается массив после дерева:

Array
(
    [_319_] => Array
        (
            [id] => _319_
            [parent_id] => 0
        )

    [_320_] => Array
        (
            [id] => _320_
            [parent_id] => 0
            [children] => Array
                (
                    [_321_] => Array
                        (
                            [id] => _321_
                            [parent_id] => _320_
                            [children] => Array
                                (
                                    [_322_] => Array
                                        (
                                            [id] => _322_
                                            [parent_id] => _321_
                                        )
                                )
                        )
                    [_325_] => Array
                        (
                            [id] => _325_
                            [parent_id] => _320_
                        )
                )
    [_323_] => Array
        (
            [id] => _323_
            [parent_id] => 0
            [children] => Array
                (
                    [_324_] => Array
                        (
                            [id] => _324_
                            [parent_id] => _323_
                        )
                )
        )

Любая помощь / руководство с благодарностью!

Какой-то код, который у меня есть:

        function buildTree(array &$elements, $parentId = 0) {
        $branch = array();

        foreach ($elements as $element) {
            if ($element['parent_id'] == $parentId) {
                $children = $this->buildTree($elements, $element['id']);
                if ($children) {
                    $element['children'] = $children;
                }
                $branch[] = $element;
            }
        }

        return $branch;
    }

Answer 1

Ты забыл unset() там, братан.

function buildTree(array &$elements, $parentId = 0) {
    $branch = array();

    foreach ($elements as $element) {
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($elements[$element['id']]);
        }
    }
    return $branch;
}

Answer 2

Решение от ImmortalFirefly работает, однако, как указывает mrded, оно не спасает первых родителей без детей.Я отредактировал функцию, чтобы исправить эту проблему:

function buildTree(array &$elements, $parentId = 0) {

    $branch = array();

    foreach ($elements as &$element) {

        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($element);
        }
    }
    return $branch;
}

Answer 3

Это работает для меня:

$index=array();
$tree=array();
foreach ($ori as $key=>$var) {
  $var=array_shift($ori);
  if ($var['id']==0) $var['id']=$key;
  if ((string)$var['parent_id']==='0') {
    $tree[$key]=$var;
    $index[$key]=&$tree[$key];
  } else if (isset($index[$var['parent_id']])) {
    if (!isset($index[$var['parent_id']]['children'])) $index[$var['parent_id']]['children']=array();
    $index[$var['parent_id']]['children'][$key]=$var;
    $index[$key]=&$index[$var['parent_id']]['children'][$key];
  } else {
    array_push($ori,$var);
  }
}
unset($index);
print_r($tree);

Answer 4

Я могу видеть логику, за исключением этого в результате:

Array
(
    [0] => Array
        (
            [id] => 0
            [parent_id] => 0
        )

    [1] => Array
        (
            [id] => 1
            [parent_id] => 0
        )

ИМХО, parent_id = o, разве [1] не должен быть здесь дочерним элементом [0]?

В любом случае, ссылки на спасение:

$tree = array();
foreach($inputarray as $item){
     if(!isset($tree[$item['id']])) $tree[$item['id']] = array();
     $tree[$item['id']] = array_merge($tree[$item['id']],$item);
     if(!isset($tree[$item['parent_id']])) $tree[$item['parent_id']] = array();
     if(!isset($tree[$item['parent_id']]['children'])) $tree[$item['parent_id']]['children'] = array();
     $tree[$item['parent_id']]['children'][] = &$tree[$item['id']];
}
$result = $tree[0]['children'];
unset($tree);
print_r($result);

Поскольку вы использовали 0 как «магическое» число как root и существующий идентификатор, теперь у нас есть рекурсия в ветви id = 0.Добавление if($item['parent_id']!=$item['id']) до $tree[$item['parent_id']]['children'][] = &$tree[$item['id']]; может предотвратить это, но это не красиво.

Answer 5

Хотя это старый вопрос, я опубликую свой ответ здесь:

/* assuming top level pid = 0 */
$rows = array (
    array ( 'id' => 1, 'pid' => 0 ),
    /* ... */
);

/* make id become array key */
$rows = array_column ( $rows, null, 'id' ); 

foreach ( $rows as $key => $val ) {
    if ( $val ['pid'] ) {
        if ( isset ( $rows [$val ['pid']] )) {
            $rows [$val ['pid']]['children'][] = &$rows [$key];
        }
    }
}

foreach ( $rows as $key => $val ) {
    if ( $val ['pid'] ) unset ( $rows [$key] );
}

array_column - это PHP 5.5, но вы можете легко создать свой собственный.

Answer 6

Можно создать исходный массив немного иначе, вы можете использовать эту функцию (parent_id, id, title):

$q = mysql_query("SELECT id, parent_id, name FROM categories");
while ($r = mysql_fetch_row($q)) {
  $names[$r[0]] = $r[2];
  $children[$r[0]][] = $r[1];
 }

function render_select($root=0, $level=-1) {
  global $names, $children;
  if ($root != 0)
    echo '<option>' . strrep(' ', $level) . $names[$root] . '</option>';
  foreach ($children[$root] as $child)
    render_select($child, $level+1);
}

echo '<select>';
render_select();
echo '</select>';

1. Более эффективная иерархическая система

Answer 7

Код SteveEdson работает нормально, за исключением случая, когда родительский элемент не существует в исходной структуре данных.Вот мое исправление для этого (однако он удаляет «parent_id» из элементов, что может или не может быть приемлемым):

function buildTree(array &$elements, $parentId = 0)
{
    $branch = array();
    foreach ($elements as &$element) {
        if ($element["parent_id"] != null && $elements[$element["parent_id"]] == null)
            unset($element["parent_id"]);        
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($element);
        }
    }
    return $branch;
}

Answer 8

Вы хотите посмотреть на хранение и загрузку иерархических данных в MySQL, так как это должно решить несколько проблем.Я предполагаю, что первый массив представляет данные, взятые непосредственно из базы данных?

Похоже, вы пытаетесь использовать модель смежности для организации ваших данных в иерархическую структуру.Есть и другие способы достижения этого с помощью вложения.Если вы не берете эти данные из базы данных, это может быть не так полезно.

Эта ссылка должна вам помочь: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

Answer 9

Я придумал решение, похожее на @ eugen-rieck, и хотел поделиться им. Я назвал $branches мой массив индексов.

$tree = [];
$branches = [];

while (!empty($input)) {
    $beforeCount = count($input);

    foreach ($input as $id => $item) {
        $pid = $item['parent_id'];

        if (isset($branches[$pid])) {
            $branches[$pid]['children'][$id] = $item;
            $branches[$id] = &$branches[$pid]['children'][$id];
            unset($input[$id]);
        }
    }

    if ($beforeCount === count($input)) {
        $firstItem = array_shift($input);
        $id = $firstItem['id'];
        $tree[$id] = $firstItem;
        $branches[$id] = &$tree[$id];
    }
}

Answer 10

Чистый, короткий и без балласта.Массив массивов в дерево:

class Mother {
    private $root;
    public function treeInit($array)
    {
        $this->root = new Child();
        foreach($array as $value){
            $this->root->treeClimb(array_reverse($value));
        }
        return $this->root;
    }
}

class Child {
    private $children = [];
    public function treeClimb($arr)
    {
        if(count($arr) > 0) {
            $childTmp = array_pop($arr);
            if(!key_exists($childTmp,$this->children))
            {
                $this->children[$childTmp] = new Child();
            }
        $this->children[$childTmp]->treeClimb($arr);
        }
    }
}

$array = array(array('obst','banae','krumm','gelb'),
                    array('obst','beere','him'),
                    array('obst','beere','brom'),
                    array('obst','banae','gerade'),
                    array('veg','carot','gerade'));

$obj = new Mother();
var_dump($obj->treeInit($array));