如何高效检索二叉搜索树中存储的目标字符串的所有前缀

这问题我之前做字符串前缀匹配场景时也碰到过，挨个查每个前缀的naive方法确实太浪费了——要是目标字符串很长，来回遍历BST好几次完全没必要。咱们可以利用BST的字典序特性（你提到的strcmp比较规则），一次遍历就把所有符合条件的前缀捞出来，思路和实现我给你捋清楚：

核心思路 #

BST的左子树节点都小于当前节点，右子树都大于当前节点（按strcmp的字典序）。基于这个特性，我们可以在遍历过程中动态剪枝，避免遍历无关的子树，同时收集所有是目标字符串前缀的节点：

1. 遍历到某个节点时，先判断它的字符串是不是目标的前缀：
   • 如果是，直接加入结果列表，并且要继续遍历左右子树——左子树可能有更短的前缀（比如"a"在"ab"的左子树），右子树可能有更长的前缀（比如"abc"在"ab"的右子树）。
   • 如果不是，就根据strcmp的结果剪枝：
     • 若当前节点字符串比目标大（strcmp返回正数）：右子树的所有节点肯定都比目标大，不可能是目标的前缀，直接跳过右子树，只遍历左子树。
     • 若当前节点字符串比目标小（strcmp返回负数）：虽然当前不是前缀，但左右子树都可能存在符合条件的前缀（比如目标是"abcd"，当前节点是"aa"，左子树可能有"a"，右子树可能有"ab"），所以都要遍历。

C语言实现示例 #

首先定义BST节点结构，然后写核心的遍历收集逻辑：

1. 节点结构与辅助函数

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// BST节点定义
typedef struct Node {
    char* str;
    struct Node* left;
    struct Node* right;
} Node;

// 判断prefix是否是target的前缀
int is_prefix(const char* prefix, const char* target) {
    size_t prefix_len = strlen(prefix);
    size_t target_len = strlen(target);
    if (prefix_len > target_len) return 0;
    // 比较prefix长度的字符即可
    return strncmp(prefix, target, prefix_len) == 0;
}

2. 递归版收集函数

递归写起来比较直观，适合理解逻辑：

// 递归遍历收集前缀
void collect_prefixes(Node* node, const char* target, char*** result, int* count, int* capacity) {
    if (!node) return;

    // 当前节点是前缀，加入结果
    if (is_prefix(node->str, target)) {
        // 动态扩容结果数组
        if (*count >= *capacity) {
            *capacity *= 2;
            *result = realloc(*result, *capacity * sizeof(char*));
        }
        (*result)[*count] = strdup(node->str); // 复制字符串避免引用问题
        (*count)++;
        // 左右子树都可能有符合条件的前缀，继续遍历
        collect_prefixes(node->left, target, result, count, capacity);
        collect_prefixes(node->right, target, result, count, capacity);
    } else {
        int cmp = strcmp(node->str, target);
        if (cmp > 0) {
            // 当前节点比目标大，右子树没必要遍历
            collect_prefixes(node->left, target, result, count, capacity);
        } else {
            // 当前节点比目标小，左右子树都可能有符合条件的
            collect_prefixes(node->left, target, result, count, capacity);
            collect_prefixes(node->right, target, result, count, capacity);
        }
    }
}

// 对外接口函数
char** find_all_prefixes(Node* root, const char* target, int* out_count) {
    if (!root || !target) {
        *out_count = 0;
        return NULL;
    }

    int capacity = 4;
    int count = 0;
    char** result = malloc(capacity * sizeof(char*));
    if (!result) {
        *out_count = 0;
        return NULL;
    }

    collect_prefixes(root, target, &result, &count, &capacity);

    // 调整数组到实际大小
    result = realloc(result, count * sizeof(char*));
    *out_count = count;
    return result;
}

3. 迭代版（避免递归栈溢出）

如果BST节点很多，递归可能栈溢出，用栈模拟递归更稳妥：

char** find_all_prefixes_iterative(Node* root, const char* target, int* out_count) {
    if (!root || !target) {
        *out_count = 0;
        return NULL;
    }

    int capacity = 4;
    int count = 0;
    char** result = malloc(capacity * sizeof(char*));
    Node** stack = malloc(capacity * sizeof(Node*));
    if (!result || !stack) {
        free(result);
        free(stack);
        *out_count = 0;
        return NULL;
    }

    int stack_top = 0;
    stack[stack_top++] = root;

    while (stack_top > 0) {
        Node* current = stack[--stack_top];

        if (is_prefix(current->str, target)) {
            // 加入结果并扩容
            if (count >= capacity) {
                capacity *= 2;
                result = realloc(result, capacity * sizeof(char*));
                stack = realloc(stack, capacity * sizeof(Node*));
            }
            result[count++] = strdup(current->str);
            // 先压右子树，再压左子树，保证左子树先遍历（和递归顺序一致）
            if (current->right) stack[stack_top++] = current->right;
            if (current->left) stack[stack_top++] = current->left;
        } else {
            int cmp = strcmp(current->str, target);
            if (cmp > 0) {
                // 只遍历左子树
                if (current->left) stack[stack_top++] = current->left;
            } else {
                // 左右都遍历
                if (current->right) stack[stack_top++] = current->right;
                if (current->left) stack[stack_top++] = current->left;
            }
        }
    }

    free(stack);
    result = realloc(result, count * sizeof(char*));
    *out_count = count;
    return result;
}

额外优化：结果排序 #

如果需要结果按前缀长度排序（比如从短到长），可以用qsort整理：

// 按字符串长度升序排序的比较函数
int compare_by_length(const void* a, const void* b) {
    const char* str1 = *(const char**)a;
    const char* str2 = *(const char**)b;
    return strlen(str1) - strlen(str2);
}

// 使用示例
int main() {
    // 假设已经构建好BST，包含"a", "ab", "abc"
    Node* root = ...;
    int count;
    char** prefixes = find_all_prefixes(root, "abcd", &count);
    
    // 排序
    qsort(prefixes, count, sizeof(char*), compare_by_length);
    
    // 输出结果
    for (int i = 0; i < count; i++) {
        printf("%s\n", prefixes[i]);
        free(prefixes[i]); // 记得释放内存
    }
    free(prefixes);
    return 0;
}

效率对比 #

• naive方法：目标字符串长度为n时，要遍历BST n次，时间复杂度O(n*h)，h是BST高度。
• 这个方法：只遍历一次BST，时间复杂度O(h + k)，k是结果的数量。当n很大时，比如目标是1000字符的字符串，这个方法的效率提升非常明显，尤其是平衡BST（h≈logN，N是节点总数）的场景。

备注：内容来源于stack exchange，提问作者glugau