Создать древовидную структуру в PHP с заданной глубиной, корневым и родительским количеством детей

Question

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

Построение дерева должно содержать следующие переменные, которые определяют ширину и глубину дерева:

Variable: MATCHES_TREE_MAX_DEPTH (eg: 3)
Variable: MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT (eg: 2)
Variable: MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT (eg: 1)

Это означает, что я хочу создать древовидную структуру глубиной 3 (включая корневой элемент, поэтому я хочу на 2 уровня глубже). Корневой элемент имеет 2 дочерних элемента, в то время как у любого дочернего элемента будет максимум 1 дочерний элемент.

Порядок элементов в моем массиве пользователей - это порядок, в котором я хочу вставить их в дерево (я хочу вставить их сначала в ширину, а не в глубину).

Я нашел следующую универсальную функцию в SO: PHP - Как построить список древовидной структуры? Но мне кажется, что я не могу адаптировать его к своему варианту использования, поскольку у меня нет отношений родитель-ребенок, исходящих из моей базы данных.

Этот SO-ответ возвращает мне массив, который выглядит похожим, но у меня возникли проблемы с преобразованием его в мой вариант использования: PHP генерирует дерево по заданной глубине и правилам

Пример данных выглядит так:

Пользователь root:

object(stdClass)[56]
  public 'user_id' => string '1' (length=1)
  public 'first_name' => string 'Dennis' (length=6)

Другие пользователи (дети):

array (size=3)
  0 => 
    object(stdClass)[57]
      public 'user_id' => string '2' (length=2)
      public 'first_name' => string 'Tom' (length=3)
      public 'street' => string 'Teststreet' (length=10)
  1 => 
    object(stdClass)[58]
      public 'user_id' => string '3' (length=2)
      public 'first_name' => string 'Mary' (length=1)
      public 'street' => string 'Maryland avenue' (length=15)
  2 => 
    object(stdClass)[59]
      public 'user_id' => string '4' (length=2)
      public 'first_name' => string 'Jeff' (length=4)
      public 'street' => string 'Teststreet' (length=10)

Пример дерева, которое я хочу получить с помощью заполненных примеров (принимая во внимание переменные 3 максимальной глубины, 2 дочерних элементов корня и 1 максимальных дочерних элементов любого другого элемента, кроме корневого):

Array
(
    [userid] => 1
    [name] => "Dennis"
    [matches] => Array
        (
            [0] => Array
                (
                    [userid] => 2
                    [name] => "Tom"
                    [street] => "Teststreet"
                    [matches] => Array
                        (
                            [0] => Array
                                (
                                    [userid] => 4
                                    [name] => "Jeff"
                                    [street] => "Teststreet"
                                    [matches] = Array()
                                )
                        )
                )

            [1] => Array
                (
                    [userid] => 3
                    [name] => "Mary"
                    [street] => "Maryland avenue"
                    [matches] => Array
                        (
                        )
                )
        )
)

Как мне создать эту древовидную структуру с учетом 3 переменных, определяющих глубину и дочерних элементов?

Answer 1

РЕДАКТИРОВАТЬ: я вижу, что оригинальный вопрос ищет решение, которое работает с 3 константами. Я добавил в код, чтобы можно было определять константы и циклы на их основе, но я не уверен, что понимаю, как предполагается использовать все три переменные. В частности, MATCHES_TREE_MAX_DEPTH кажется неуместным, учитывая ваши описания. Вы указали только два уровня детей и указали, что мы должны пропустить любые дополнительные пункты в вашем списке. Если вам нужен код, который определяет еще больше уровней дочерних элементов, вам необходимо уточнить, как вы хотите, чтобы ваша структура развивалась.

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

// function to convert from list objects to the array we want as output
function new_obj($obj) {
    $ret = array(
        "userid" => $obj->user_id,
        "name" => $obj->first_name
    );
    if (isset($obj->street)) {
        $ret["street"] = $obj->street;
    }
    $ret["matches"] = [];
    return $ret;
}


// INPUT DATA
$root = (object)["user_id" => "1", "first_name" => "Dennis"];
$children = [
    (object)[
        "user_id" => "2",
        "first_name" => "Tom",
        "street" => "Teststreet"
    ],
    (object)[
        "user_id" => "3",
        "first_name" => "Mary",
        "street" => "Maryland avenue"
    ],
    (object)[
        "user_id" => "4",
        "first_name" => "Jeff",
        "street" => "Teststreet"
    ],
    (object)[
        "user_id" => "5",
        "first_name" => "Arthur",
        "street" => "Teststreet"
    ]

];

$result1 = new_obj($root);

// an iterative solution, only works for one trivial set of values for the constants defined
// but also does provide some insight into a more general solution
if (isset($children[0])) {
    $result1["matches"][0] = new_obj($children[0]);
}
if (isset($children[1])) {
    $result1["matches"][1] = new_obj($children[1]);
}
if (isset($children[2])) {
    $result1["matches"][0]["matches"][0] = new_obj($children[2]);
}
if (isset($children[3])) {
    $result1["matches"][1]["matches"][0] = new_obj($children[3]);
}


print_r($result1);

Если вы хотите определить константы / переменные, чтобы указать дочерние ограничения, а затем использовать циклы, попробуйте это с теми же переменными $ root и $ children, определенными выше.

// solution must use these constants:
define("MATCHES_TREE_MAX_DEPTH", 3);
define("MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT", 2);
define("MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT", 1);

$result2 = new_obj($root);

$i = 0;
while ($child = array_shift($children)) {
    $result2["matches"][$i] = new_obj($child);
    $i++;
    if ($i >= MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT) break;
}

$i = 0;
while ($grandchild = array_shift($children)) {
    $child = $result2["matches"][$i];
    if (count($child["matches"]) >= MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT) {
        // if we reach a child that has its max number of grandchildren, it's time to quit
        break;
    }
    // otherwise, assign this child as a grandchild
    $result2["matches"][$i]["matches"] = new_obj($grandchild);

    // increment the counter and check if we cycle back to the first child of root
    $i++;
    if ($i >= count($result2["matches"])) {
        $i = 0;
    }
}
print_r($result2);