如何通过递归与结构体返回多组数据？AVL树遍历问题求助

你的核心问题在于：当前的check_addr函数每次递归调用时，返回的结构体结果都被直接丢弃了，最后只返回了当前栈帧中赋值的那一个addrData，所以自然只能得到一组数据。要收集递归过程中所有匹配的结果，我们需要把结果容器（比如动态数组）作为参数传入递归函数，在遍历过程中不断添加匹配项。

下面是具体的修改方案：

1. 调整函数参数，添加结果收集容器 #

我们可以传入一个动态分配的结构体数组指针，以及一个记录当前结果数量的计数器，这样每次找到符合条件的节点时，就把数据添加到数组中：

#include <stdlib.h> // 需要malloc/realloc

// 假设你已定义以下结构体
struct baseBound {
    unsigned int base;
    unsigned int bound;
};

struct Node {
    unsigned int startAddr;
    unsigned int endAddr;
    struct Node *left;
    struct Node *right;
    // AVL树的高度等字段，此处省略
};

// 修改后的递归函数：不再返回单个结构体，而是填充传入的结果数组
void check_addr(struct Node *root, int x, int y, struct baseBound** result, int* count) {
    if(NULL == root) {
        return;
    }

    // 先遍历左子树（AVL树按startAddr有序，左子树节点startAddr更小）
    check_addr(root->left, x, y, result, count);

    // 检查当前节点是否符合条件
    if(root->startAddr <= x && y <= root->endAddr) {
        // 扩容结果数组
        *result = realloc(*result, (*count + 1) * sizeof(struct baseBound));
        if(*result == NULL) {
            perror("realloc failed");
            exit(EXIT_FAILURE);
        }
        // 添加当前节点的数据
        (*result)[*count].base = root->startAddr;
        (*result)[*count].bound = root->endAddr;
        (*count)++;
    } else if (x < root->startAddr) {
        // 右子树的startAddr更大，无需继续遍历，直接返回
        return;
    }

    // 遍历右子树
    check_addr(root->right, x, y, result, count);
}

2. 修改main函数中的调用逻辑 #

在main函数中，我们需要初始化结果数组和计数器，调用函数后遍历输出所有结果：

int main() {
    struct Node *root = NULL;
    struct baseBound *addrData = NULL;
    int count = 0;

    // 插入节点的代码保持不变
    root = insert(root, 0x40, 0x238);
    root = insert(root, 0x238, 0x254);
    root = insert(root, 0x0, 0x838);
    root = insert(root, 0x200db8, 0x201018);
    root = insert(root, 0x200dc8, 0x200fb8);
    root = insert(root, 0x254, 0x298);
    root = insert(root, 0x6f4, 0x730);
    root = insert(root, 0x0, 0x0);
    root = insert(root, 0x200db8, 0x201000);

    printf("Postorder traversal of the constructed AVL tree is \n");
    postOrder(root);
    printf("\n");

    // 调用修改后的函数
    check_addr(root, 0x238, 0x254, &addrData, &count);

    // 输出所有结果
    printf("Found %d matching nodes:\n", count);
    for(int i = 0; i < count; i++) {
        printf("%x >> %x\n", addrData[i].base, addrData[i].bound);
    }

    // 释放动态分配的内存，避免泄漏
    free(addrData);
    return 0;
}

3. 关键逻辑说明 #

• 结果收集方式：通过动态数组addrData和计数器count，我们在递归过程中不断添加匹配的结构体，突破了单个返回值的限制。
• 遍历优化：利用AVL树的有序性（假设insert函数按startAddr排序构建），当当前节点startAddr大于x时，右子树节点的startAddr只会更大，直接终止该分支的遍历，减少不必要的递归开销。
• 内存管理：使用realloc扩容后必须检查分配是否成功；使用完动态数组后记得调用free释放内存，避免内存泄漏。

4. 原代码的其他问题修正 #

原递归函数中的多个独立if分支可能导致重复遍历节点（比如同时进入左、右子树的递归调用），修改后的代码采用类似中序遍历的顺序，确保每个节点只被处理一次，逻辑更清晰且高效。

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