Как преобразовать этот массив MPTT в древовидную структуру в PHP?

Question

У меня есть иерархические данные в базе данных, хранящиеся в Модифицированный формат обхода дерева предзаказов . Я извлекаю данные в запросе, который выглядит примерно так: «SELECT ID, Left, Right, Имя и т. Д. ИЗ таблицы ORDER BY Left;». Я пытаюсь преобразовать эти данные из плоского массива, который БД дает мне, в древовидную структуру, которую я затем выведу в виде JSON с функцией PHP json_encode.

У меня проблемы с тем, чтобы заставить мой код древовидной структуры работать за пределами первого уровня. Вот минимальный тестовый пример:

<code><pre><?php

function projectListToTree($projects) {
    $stack = Array();
    for($x =0; $x < count($projects); $x++) {
        $project = $projects[$x];
        $project['Children'] = Array();

        while(count($stack) > 0 && $stack[count($stack) - 1]['Right'] < $project['Right']) {
            array_pop($stack);
        }

        if(count($stack) > 0) {
            $stack[count($stack) - 1]['Children'][] = $project; 
            echo "Adding " . $project['Name'] . " to " . $stack[count($stack) - 1]['Name'] . " for a total of "
                . count($stack[count($stack) - 1]['Children']) . " kids\n";
        } else {
            echo "No parent\n"; 
        }

        echo "stack count: " . count($stack) . "\n";

        array_push($stack, $project);
    }

    echo "Left in stack: " . count($stack) . "\n";

    return $stack[0];
}

/*
This is basically what comes from the DB.
Should be:
  Parent
    First Child
    Second Child
      Grand Child
*/
$projects = Array(
    Array(
        "ID" => "2",
        "Left" => "2",
        "Right" => "9",
        "ParentID" => "1",
        "Name" => "Parent"
    ),
    Array(
        "ID" => "3",
        "Left" => "3",
        "Right" => "4",
        "ParentID" => "2",
        "Name" => "First Child"
    ),
    Array(
        "ID" => "4",
        "Left" => "5",
        "Right" => "8",
        "ParentID" => "2",
        "Name" => "Second Child"
    ),
    Array(
        "ID" => "5",
        "Left" => "6",
        "Right" => "7",
        "ParentID" => "4",
        "Name" => "Grand Child"
    )
);


$tree = projectListToTree($projects);
echo "-----\n\n\n\n";
var_dump($tree);

?>

А вот что я получаю для вывода:

No parent
stack count: 0
Adding First Child to Parent for a total of 1 kids
stack count: 1
Adding Second Child to Parent for a total of 2 kids
stack count: 1
Adding Grand Child to Second Child for a total of 1 kids
stack count: 2
Left in stack: 3
-----



array(6) {
  ["ID"]=>
  string(1) "2"
  ["Left"]=>
  string(1) "2"
  ["Right"]=>
  string(1) "9"
  ["ParentID"]=>
  string(1) "1"
  ["Name"]=>
  string(6) "Parent"
  ["Children"]=>
  array(2) {
    [0]=>
    array(6) {
      ["ID"]=>
      string(1) "3"
      ["Left"]=>
      string(1) "3"
      ["Right"]=>
      string(1) "4"
      ["ParentID"]=>
      string(1) "2"
      ["Name"]=>
      string(11) "First Child"
      ["Children"]=>
      array(0) {
      }
    }
    [1]=>
    array(6) {
      ["ID"]=>
      string(1) "4"
      ["Left"]=>
      string(1) "5"
      ["Right"]=>
      string(1) "8"
      ["ParentID"]=>
      string(1) "2"
      ["Name"]=>
      string(12) "Second Child"
      ["Children"]=>
      array(0) {
      }
    }
  }
}

Как видите, где-то "Grandchild" теряется, хотя вывод в функции projectListToTree, похоже, указывает, что он должен быть там. Кажется, что любая структура дерева, которую я бросаю в нее, опускает что-либо ниже второго уровня. Любое понимание того, что может происходить?

Спасибо!

Answer 1

Проблема в том, что присвоение массива не копирует ссылки, а создает копию массива. Это означает, что массив «Второй дочерний», который имеется в «потомках» узла «Родитель», - это не тот массив, в который вы добавляете «Внука», а его копия.

Чтобы решить эту проблему, вы должны явно использовать присвоение ссылки вместо копирования:

function projectListToTree($projects) {
    $stack = Array();
    for($x =0; $x < count($projects); $x++) {
        $project = &$projects[$x];
        $project['Children'] = array();

        while(count($stack) > 0 && $stack[count($stack) - 1]['Right'] < $project['Right']) {
                array_pop($stack);
        }

        if(count($stack) > 0) {
                $stack[count($stack) - 1]['Children'][] = &$project; 

                echo "Adding " . $project['Name'] . " to " . $stack[count($stack) - 1]['Name'] . " for a total of "
                        . count($stack[count($stack) - 1]['Children']) . " kids\n";

                echo "\n";
        } else {
                echo "No parent\n"; 
        }

        echo "stack count: " . count($stack) . "\n";

        $stack[] = &$project;
    }

    echo "Left in stack: " . count($stack) . "\n";

    return $stack[0];
}

Обратите внимание, что амперсанд был добавлен в трех местах.

Из-за этой проблемы нужно быть предельно осторожным при использовании вложенных массивов и операторов присваивания в php.

Это также означает, что использование процессора и использование памяти являются интенсивными при использовании большого количества данных во вложенных массивах. Например, в приведенном выше примере при возврате projectListToTree () полное дерево массивов копируется в локальную переменную $ tree и (поскольку сборщик мусора php отстой) дважды находится в памяти.

Answer 2

Вы вставили оператор echo, чтобы увидеть, когда вы вызываете array_pop ()? Прочитав это без тестирования, я думаю, вы вытаскиваете запись из стека и выбрасываете ее.