如何在PHP中按指定深度与子节点数规则构建用户树结构？

需求回顾 #

你需要基于以下规则，把无父子关系的用户数组构建成指定结构的树：

• 树的总深度为 MATCHES_TREE_MAX_DEPTH（示例值3，包含根节点）
• 根节点最多允许 MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT 个子节点（示例值2）
• 其他父节点最多允许 MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT 个子节点（示例值1）
• 必须按用户数组的顺序，以广度优先的方式插入节点

核心思路 #

因为是广度优先填充，我们可以用队列来管理待填充子节点的父节点：

1. 先处理根节点的子节点，填满根节点的配额后，再依次处理根节点的每个子节点的子节点，以此类推
2. 每次从队列取出一个节点，判断它是否还能添加子节点（未达配额且当前层级未到最大深度），如果可以就从用户数组取第一个用户添加进去，同时把新的子节点加入队列等待后续填充

PHP 实现代码 #

function buildUserTree($rootUser, $childUsers, $maxDepth, $rootMaxChildren, $parentMaxChildren) {
    // 转换根节点为目标结构
    $tree = [
        'userid' => $rootUser->user_id,
        'name' => $rootUser->first_name,
        'matches' => []
    ];

    // 队列元素格式：[当前节点引用, 当前层级]
    // 根节点是层级1，最大深度3的话，层级2的节点可以添加子节点（到层级3）
    $queue = [[&$tree, 1]];

    $userIndex = 0;
    $totalUsers = count($childUsers);

    while ($userIndex < $totalUsers && !empty($queue)) {
        // 取出队列头部的节点和层级
        list($currentNode, $currentLevel) = array_shift($queue);

        // 判断当前节点是否还能添加子节点：层级未到最大深度，且子节点数未达上限
        $maxChildren = $currentLevel === 1 ? $rootMaxChildren : $parentMaxChildren;
        if ($currentLevel >= $maxDepth || count($currentNode['matches']) >= $maxChildren) {
            continue;
        }

        // 取出下一个用户，转换为目标结构
        $user = $childUsers[$userIndex];
        $childNode = [
            'userid' => $user->user_id,
            'name' => $user->first_name,
            'matches' => []
        ];
        // 如果用户有其他字段（比如street），也一并添加
        foreach ($user as $key => $value) {
            if (!in_array($key, ['user_id', 'first_name'])) {
                $childNode[$key] = $value;
            }
        }

        // 添加到当前节点的matches数组
        $currentNode['matches'][] = $childNode;
        $userIndex++;

        // 将新子节点加入队列，层级+1
        $queue[] = [&$currentNode['matches'][count($currentNode['matches']) - 1], $currentLevel + 1];

        // 如果当前节点还能继续添加子节点，把它放回队列尾部，继续处理
        if (count($currentNode['matches']) < $maxChildren) {
            array_unshift($queue, [$currentNode, $currentLevel]);
        }
    }

    return $tree;
}

// 测试示例数据
$rootUser = (object)[
    'user_id' => '1',
    'first_name' => 'Dennis'
];

$childUsers = [
    (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'
    ]
];

// 配置参数
define('MATCHES_TREE_MAX_DEPTH', 3);
define('MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT', 2);
define('MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT', 1);

// 生成树
$result = buildUserTree(
    $rootUser,
    $childUsers,
    MATCHES_TREE_MAX_DEPTH,
    MATCHES_TREE_ROOT_MAX_CHILDREN_AMOUNT,
    MATCHES_TREE_PARENT_MAX_CHILDREN_AMOUNT
);

// 打印结果
print_r($result);

代码说明 #

1. 节点结构转换：把原始对象转换为你需要的数组结构，自动保留user_id、first_name之外的字段（比如street）
2. 队列管理：用队列确保广度优先的顺序——先填满根节点的2个子节点，再处理Tom的子节点，最后处理Mary的（但Mary的子节点配额是1，但此时用户数组已经空了，所以Mary的matches是空数组）
3. 配额判断：根节点用rootMaxChildren，其他节点用parentMaxChildren，同时判断当前层级是否已达最大深度，避免超出层级
4. 循环终止条件：要么所有用户都被插入，要么队列里的节点都无法再添加子节点（达到配额或层级上限）

测试结果 #

运行代码后，会输出你期望的结构：

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

内容的提问来源于stack exchange，提问作者Dennis