PHP分类树按名称搜索并获取父子节点的算法实现

需求 #

实现PHP分类树按名称搜索，获取对应的父子节点，返回包含ID、带路径的名称（用/分隔）及层级的结果。

数据库表结构（表名t1） #

+----+-----------+------------+-------+
| id | parent_id | name       | level |
+----+-----------+------------+-------+
|  1 |         0 | cars       |     1 |
|  2 |         1 | ford       |     2 |
|  3 |         2 | red        |     3 |
|  4 |         2 | blue       |     3 |
|  5 |         0 | Airs       |     1 |
|  6 |         5 | AirBus     |     2 |
|  7 |         5 | Boeing     |     2 |
|  8 |         6 | blue       |     3 |
|  9 |         5 | white      |     3 |
| 10 |         5 | green      |     3 |
+----+-----------+------------+-------+

搜索示例 #

示例1：搜索关键词 = cars #

array:4 [ 
  0 => array:3 [
    "id" => 1
    "name" => "Cars"
    "level" => 1
  ]
  1 => array:3 [
    "id" => 2
    "name" => "Cars/ford"
    "level" => 2
  ]
  2 => array:3 [
    "id" => 3
    "name" => "Cars/ford/red"
    "level" => 3
  ]
  3 => array:3 [
    "id" => 4
    "name" => "Cars/ford/blue"
    "level" => 3
  ]
]

示例2：搜索关键词 = ford #

array:3 [ 
  0 => array:3 [
    "id" => 2
    "name" => "Cars/ford"
    "level" => 2
  ]
  1 => array:3 [
    "id" => 3
    "name" => "Cars/ford/red"
    "level" => 3
  ]
  2 => array:3 [
    "id" => 4
    "name" => "Cars/ford/blue"
    "level" => 3
  ]
]

示例3：搜索关键词 = blue #

array:2 [ 
  0 => array:3 [
    "id" => 4
    "name" => "Cars/ford/blue"
    "level" => 3
  ]
  1 => array:3 [
    "id" => 8
    "name" => "Airs/Airbus/blue"
    "level" => 3
  ]
]

规则总结 #

• 若搜索结果为1级分类：获取该分类及其所有子级分类
• 若搜索结果为2级分类：获取该分类、其父级分类及所有子级分类
• 若搜索结果为3级分类：获取该分类及其所有上级父级分类（1级、2级）

现有限制 #

原本计划新增fullName字段存储带路径的名称，搜索时直接检索，但目前无数据库修改权限，需通过算法实现。

原始分类数组 #

array (
  0 => 
  array (
    'id' => 2,
    'name' => 'ford',
    'parent_id' => 1,
    'level' => 2,
  ),
  1 => 
  array (
    'id' => 3,
    'name' => 'red',
    'parent_id' => 2,
    'level' => 3,
  ),
  2 => 
  array (
    'id' => 4,
    'name' => 'blue',
    'parent_id' => 2,
    'level' => 3,
  ),
  3 => 
  array (
    'id' => 5,
    'name' => 'Airs',
    'parent_id' => 0,
    'level' => 1,
  ),
  4 => 
  array (
    'id' => 6,
    'name' => 'Airbus',
    'parent_id' => 5,
    'level' => 2,
  ),
  5 => 
  array (
    'id' => 7,
    'name' => 'Boeing',
    'parent_id' => 5,
    'level' => 2,
  ),
  6 => 
  array (
    'id' => 8,
    'name' => 'blue',
    'parent_id' => 6,
    'level' => 3,
  ),
  7 => 
  array (
    'id' => 9,
    'name' => 'white',
    'parent_id' => 5,
    'level' => 3,
  ),
  8 => 
  array (
    'id' => 10,
    'name' => 'green',
    'parent_id' => 5,
    'level' => 3,
  ),
  9 => 
  array (
    'id' => 1,
    'name' => 'Cars',
    'parent_id' => 0,
    'level' => 1,
  ),
)

算法实现代码 #

<?php

function searchCategoryTree($categories, $keyword) {
    // 将分类数组转为以id为键的映射，方便快速查找
    $categoryMap = [];
    foreach ($categories as $cat) {
        $categoryMap[$cat['id']] = $cat;
    }

    // 查找所有匹配关键词的分类（不区分大小写）
    $matchedCats = [];
    foreach ($categoryMap as $cat) {
        if (stripos($cat['name'], $keyword) !== false) {
            $matchedCats[] = $cat;
        }
    }

    $result = [];
    $processedIds = []; // 避免重复处理同一分类

    foreach ($matchedCats as $matchedCat) {
        $currentId = $matchedCat['id'];
        $level = $matchedCat['level'];

        if ($level == 1) {
            // 1级分类：获取自身及所有子级
            $treeNodes = getSubtreeNodes($currentId, $categoryMap);
            foreach ($treeNodes as $nodeId) {
                if (!isset($processedIds[$nodeId])) {
                    $result[] = [
                        'id' => $nodeId,
                        'name' => getFullPath($nodeId, $categoryMap),
                        'level' => $categoryMap[$nodeId]['level']
                    ];
                    $processedIds[$nodeId] = true;
                }
            }
        } elseif ($level == 2) {
            // 2级分类：获取父级、自身及所有子级
            $parentId = $matchedCat['parent_id'];
            if (!isset($processedIds[$parentId])) {
                $result[] = [
                    'id' => $parentId,
                    'name' => getFullPath($parentId, $categoryMap),
                    'level' => $categoryMap[$parentId]['level']
                ];
                $processedIds[$parentId] = true;
            }
            $treeNodes = getSubtreeNodes($currentId, $categoryMap);
            foreach ($treeNodes as $nodeId) {
                if (!isset($processedIds[$nodeId])) {
                    $result[] = [
                        'id' => $nodeId,
                        'name' => getFullPath($nodeId, $categoryMap),
                        'level' => $categoryMap[$nodeId]['level']
                    ];
                    $processedIds[$nodeId] = true;
                }
            }
        } elseif ($level == 3) {
            // 3级分类：获取自身及所有父级
            $pathIds = getPathIds($currentId, $categoryMap);
            foreach ($pathIds as $nodeId) {
                if (!isset($processedIds[$nodeId])) {
                    $result[] = [
                        'id' => $nodeId,
                        'name' => getFullPath($nodeId, $categoryMap),
                        'level' => $categoryMap[$nodeId]['level']
                    ];
                    $processedIds[$nodeId] = true;
                }
            }
        }
    }

    // 按层级排序，同一层级按id排序
    usort($result, function($a, $b) {
        if ($a['level'] == $b['level']) {
            return $a['id'] - $b['id'];
        }
        return $a['level'] - $b['level'];
    });

    return $result;
}

// 获取指定节点的所有子级节点ID（包括自身）
function getSubtreeNodes($rootId, $categoryMap) {
    $nodes = [$rootId];
    foreach ($categoryMap as $cat) {
        if ($cat['parent_id'] == $rootId) {
            $nodes = array_merge($nodes, getSubtreeNodes($cat['id'], $categoryMap));
        }
    }
    return $nodes;
}

// 获取指定节点的完整路径ID（从根到自身）
function getPathIds($nodeId, $categoryMap) {
    $path = [$nodeId];
    $parentId = $categoryMap[$nodeId]['parent_id'];
    while ($parentId != 0 && isset($categoryMap[$parentId])) {
        array_unshift($path, $parentId);
        $parentId = $categoryMap[$parentId]['parent_id'];
    }
    return $path;
}

// 获取指定节点的带路径名称
function getFullPath($nodeId, $categoryMap) {
    $pathIds = getPathIds($nodeId, $categoryMap);
    $names = [];
    foreach ($pathIds as $id) {
        $names[] = $categoryMap[$id]['name'];
    }
    return implode('/', $names);
}

// 测试示例
$categories = array (
  0 => 
  array (
    'id' => 2,
    'name' => 'ford',
    'parent_id' => 1,
    'level' => 2,
  ),
  1 => 
  array (
    'id' => 3,
    'name' => 'red',
    'parent_id' => 2,
    'level' => 3,
  ),
  2 => 
  array (
    'id' => 4,
    'name' => 'blue',
    'parent_id' => 2,
    'level' => 3,
  ),
  3 => 
  array (
    'id' => 5,
    'name' => 'Airs',
    'parent_id' => 0,
    'level' => 1,
  ),
  4 => 
  array (
    'id' => 6,
    'name' => 'Airbus',
    'parent_id' => 5,
    'level' => 2,
  ),
  5 => 
  array (
    'id' => 7,
    'name' => 'Boeing',
    'parent_id' => 5,
    'level' => 2,
  ),
  6 => 
  array (
    'id' => 8,
    'name' => 'blue',
    'parent_id' => 6,
    'level' => 3,
  ),
  7 => 
  array (
    'id' => 9,
    'name' => 'white',
    'parent_id' => 5,
    'level' => 3,
  ),
  8 => 
  array (
    'id' => 10,
    'name' => 'green',
    'parent_id' => 5,
    'level' => 3,
  ),
  9 => 
  array (
    'id' => 1,
    'name' => 'Cars',
    'parent_id' => 0,
    'level' => 1,
  ),
);

// 测试搜索
echo "搜索'cars'结果：\n";
print_r(searchCategoryTree($categories, 'cars'));

echo "\n搜索'ford'结果：\n";
print_r(searchCategoryTree($categories, 'ford'));

echo "\n搜索'blue'结果：\n";
print_r(searchCategoryTree($categories, 'blue'));
?>

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