如何在Trie中删除空父节点？无法移除无子节点的节点

问题说明 #

在Trie树中删除节点时，能正确识别并移除值为3的标记节点，但无法移除没有子节点的空父节点，最终残留空节点结构，期望删除后整个树变为空数组。

现有代码 #

function removeWord($word){
    global $tree;
    $ch=false;
    
    while(strlen($word)>0){
        $p="";
        $parent=&$tree;
        $i=0;
        
        foreach(str_split($word) as $char){
            $i++;
            $p.=$char;
            $parent=&$parent[$char];
            
            if(!$ch && $parent[0]==3 && $p==$word){
                unset($parent[0]);
                $ch=true;
            }
            if($ch && $p==$word){
                if(empty($parent)){
                    unset($parent);
                }
                else{
                    $word="";
                    break;
                }
                $word=substr($word, 0, -1);
            }
        }
    }
}

测试数据 #

示例数据 #

$tree=array("a"=>array("a"=>array()));
$word='aa';

源数据（删除前） #

Array
(
    [a] => Array
        (
            [a] => Array
                (
                    [0] => 3
                )

        )

)

错误输出（删除后） #

Array
(
    [a] => Array
        (
            [a] => Array
                (
                )

        )

)

期望输出 #

Array ( )

问题根源 #

1. 引用操作无效：unset($parent)仅销毁当前变量引用，并未修改上层父节点中对应的子节点条目，空节点依然留在父节点的数组中。
2. 循环逻辑无法回溯：当前循环尝试通过缩短单词长度回溯，但未正确定位到上层父节点并删除空的子节点条目，导致空节点残留。

解决方案：递归实现删除 #

递归天然适合Trie树的层级回溯，删除单词末尾节点后，逐层向上检查父节点是否为空，为空则继续删除：

function removeWordRecursive(&$node, $word, $index = 0) {
    if ($index === strlen($word)) {
        // 到达单词末尾，移除标记3
        if (isset($node[0]) && $node[0] == 3) {
            unset($node[0]);
            // 检查当前节点是否为空，为空则返回true告知上层删除
            return empty($node);
        }
        return false;
    }

    $char = $word[$index];
    if (!isset($node[$char])) {
        return false;
    }

    // 递归处理子节点
    $shouldDeleteChild = removeWordRecursive($node[$char], $word, $index + 1);

    if ($shouldDeleteChild) {
        // 子节点为空，移除当前节点中的该子条目
        unset($node[$char]);
        // 返回当前节点是否为空，供上层判断
        return empty($node);
    }

    return false;
}

// 使用方式
removeWordRecursive($tree, 'aa');

代码说明 #

• 递归遍历到单词末尾，先删除标记3，判断当前节点是否为空，返回布尔值告知上层是否需要删除该节点。
• 上层节点收到子节点需要删除的信号后，移除对应的子条目，再检查自身是否为空，继续向上传递删除信号。
• 通过引用传递&$node，直接修改原Trie树的结构，确保空节点被彻底移除。

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