在构建复杂的分类系统时，我们经常会遇到这样的场景：一个树状结构中包含大量类别，每个类别可能包含子类别和/或关联内容。然而，随着内容的增删，一些类别可能变得“空”——它们自身没有直接关联的内容，甚至其所有子类别也都没有任何内容。为了维护数据结构的整洁和效率，我们需要一种机制来自动识别并移除这些冗余的空类别，只保留那些最终能导向实际内容的路径。
问题定义
假设我们有一个以下结构的类别树：
[uid_of_category]
=> (array)content
=> [...associated content...] 或 empty
=> (array)sub_categories
=> [uid_of_category]
=> (array)content
=> [...associated content...] 或 empty
=> (array)sub_categories
...我们的目标是清理这个树，使得只有满足以下条件的类别才被保留：
- 该类别直接包含关联内容。
- 该类别本身没有关联内容，但其至少一个子类别（或子类别的子类别，以此类推）包含关联内容。
换句话说，任何不通向实际内容的“死胡同”路径都应该被移除。
解决方案：递归方法
处理树状结构最自然且强大的工具就是递归。我们将采用双函数递归策略来解决这个问题：一个函数负责判断一个类别及其所有后代是否“可清理”（即完全没有内容），另一个函数则负责遍历树并执行清理操作。
1. 判断类别是否可清理 (isCleanable)
这个函数的目标是确定一个给定的类别，以及其所有子类别，是否完全没有任何内容。如果一个类别自身没有内容，并且它的所有子类别（递归地）也都没有内容，那么这个类别就是“可清理”的。
/**
* 判断一个类别及其所有后代是否完全没有内容（可清理）。
*
* @param array $category 待检查的类别数组。
* @return bool 如果类别及其所有后代都没有内容，则返回 true；否则返回 false。
*/
function isCleanable(array $category): bool
{
// 如果当前类别有内容，则它不可清理。
if (!empty($category['content'])) {
return false;
}
// 遍历当前类别的所有子类别。
// 如果任何一个子类别（或其后代）不可清理（即有内容），则当前类别也不可清理。
foreach ($category['sub_categories'] as $subCategory) {
if (!isCleanable($subCategory)) {
return false; // 发现有内容的子类别，当前类别不可清理
}
}
// 如果当前类别没有内容，且所有子类别都可清理（即也都没有内容），
// 那么当前类别就是可清理的。
return true;
}函数逻辑详解：
- 基本情况： 如果$category['content']非空，说明这个类别自身有内容，它就不是一个“空”类别，因此不可清理，直接返回false。
-
递归情况： 如果当前类别没有内容，我们需要检查它的子类别。我们遍历$category['sub_categories']，并对每个子类别递归调用isCleanable。
- 如果isCleanable($subCategory)返回false（表示该子类别或其后代有内容），那么当前的父类别也就不应该被清理，因为它通向了内容，所以立即返回false。
- 最终判断： 如果循环结束，意味着当前类别没有内容，并且它的所有子类别（递归检查后）也都被判定为可清理（即都没有内容），那么当前类别就是可清理的，返回true。
2. 执行清理操作 (cleanCategories)
这个函数负责遍历整个类别树，并根据isCleanable的判断结果移除相应的类别。为了能够修改原始的类别数组，我们需要通过引用传递参数。
/**
* 递归地清理类别树，移除所有不包含内容或不通向内容的空类别。
*
* @param array $categories 待清理的类别数组（通过引用传递）。
* @return void
*/
function cleanCategories(array &$categories): void
{
foreach ($categories as $key => &$category) { // 注意这里 $category 也是通过引用传递，以便修改子类别
// 如果当前类别是可清理的（自身和所有后代都没有内容），则移除它。
if (isCleanable($category)) {
unset($categories[$key]);
} else {
// 如果当前类别不可清理（有内容或通向内容），则递归清理其子类别。
// 确保 'sub_categories' 键存在且是数组，避免错误
if (isset($category['sub_categories']) && is_array($category['sub_categories'])) {
cleanCategories($category['sub_categories']);
}
}
}
}函数逻辑详解：
- 引用传递： $categories参数必须通过引用（&）传递。这是因为我们希望在函数内部直接修改调用者传入的数组（即移除元素），而不是创建一个副本。
-
遍历与判断： 函数遍历当前级别的所有类别。对于每个类别：
- 它调用isCleanable($category)。如果返回true，说明这个类别及其所有后代都没有内容，因此可以使用unset($categories[$key])将其从当前数组中移除。
- 如果isCleanable($category)返回false（表示这个类别自身有内容，或者它的某个子类别有内容），那么这个类别需要保留。此时，我们递归地调用cleanCategories($category['sub_categories'])来处理它的子类别，确保子树中的空类别也被清理。
示例用法
假设我们有以下初始类别数据：
$categoryTree = [
'cat1' => [
'content' => [], // 空内容
'sub_categories' => [
'cat1_1' => [
'content' => [], // 空内容
'sub_categories' => []
],
'cat1_2' => [
'content' => ['item_a'], // 有内容
'sub_categories' => []
],
'cat1_3' => [
'content' => [], // 空内容
'sub_categories' => [
'cat1_3_1' => [
'content' => ['item_b'], // 有内容
'sub_categories' => []
],
'cat1_3_2' => [
'content' => [], // 空内容
'sub_categories' => []
]
]
]
]
],
'cat2' => [
'content' => [], // 空内容
'sub_categories' => [
'cat2_1' => [
'content' => [], // 空内容
'sub_categories' => []
]
]
]
];
// 执行清理操作
cleanCategories($categoryTree);
// 打印清理后的树
print_r($categoryTree);清理后的预期结果：
- cat2 会被移除，因为它自身没有内容，且其子类别cat2_1也没有内容。
- cat1_1 会被移除，因为它没有内容。
- cat1_3_2 会被移除，因为它没有内容。
- cat1_3 会被保留，因为它通向cat1_3_1（有内容）。
- cat1 会被保留，因为它通向cat1_2和cat1_3（都有内容）。
最终$categoryTree将只包含cat1、cat1_2、cat1_3、cat1_3_1，并且cat1_3下的cat1_3_2将被移除。
注意事项与优化
- 数据结构一致性： 确保您的类别数据严格遵循预期的content和sub_categories键结构。如果键名可能不存在或类型不匹配，请在代码中添加额外的检查（例如isset()和is_array()）。
- 引用传递的重要性： 再次强调，cleanCategories函数中的&$categories参数是关键。如果忘记&，函数将操作数组的副本，原始数组不会被修改。
- 效率考量： 这种双递归函数的方法在逻辑上非常清晰，但在处理极其庞大的树时，可能会有多次遍历的开销。对于大多数应用场景，其性能是足够的。更高级的优化可能涉及单次遍历的后序遍历（post-order traversal）策略，但在代码复杂性上会增加。
- 错误处理： 在生产环境中，您可能需要添加额外的错误处理，例如检查输入是否为有效的数组结构。
总结
通过递归函数isCleanable和cleanCategories的巧妙结合，我们能够高效且精确地清理复杂的树状分类结构。这种方法不仅保证了数据结构的整洁，也为后续的数据处理和展示提供了优化过的基础。理解并掌握递归在处理树形数据结构中的应用，是每一个开发者必备的技能。
