如何在按a值排序的AVL树中查找独立b值的最小值？

因为b值和AVL树基于a的排序规则无关，必须遍历所有节点才能找到全局最小的b值。下面是两种可行的递归实现思路，完全不会出现“丢失最小值”的问题：

方法1：用指针参数实时更新最小值 #

递归函数传入一个指向int的指针，用来持续记录当前找到的最小值。初始时把指针指向一个极大值（比如INT_MAX），遍历每个节点时，若当前节点的b值更小，就更新指针指向的值。

示例代码：

#include <limits.h>

void findMinB(struct avl* root, int* min_val) {
    if (root == NULL) {
        return;
    }
    // 更新当前最小值
    if (root->b < *min_val) {
        *min_val = root->b;
    }
    // 递归遍历左右子树
    findMinB(root->left, min_val);
    findMinB(root->right, min_val);
}

// 调用方式
int min_b = INT_MAX;
findMinB(your_avl_root, &min_b);
// 此时min_b即为树中b的最小值

方法2：递归返回当前子树的最小b值 #

让递归函数返回当前子树（含当前节点）的最小b值，通过合并当前节点b值、左子树最小值、右子树最小值，最终得到全局最小值。

示例代码：

#include <limits.h>

int findMinB(struct avl* root) {
    if (root == NULL) {
        // 空树返回极大值，不影响最小值计算
        return INT_MAX;
    }
    // 递归获取左右子树的最小b值
    int left_min = findMinB(root->left);
    int right_min = findMinB(root->right);
    // 三者取最小
    int curr_min = root->b < left_min ? root->b : left_min;
    return curr_min < right_min ? curr_min : right_min;
}

// 调用方式
int min_b = findMinB(your_avl_root);
// 注意：树为空时min_b会是INT_MAX，调用前需判断树是否非空

额外提示 #

• 调用前务必判断树是否为空，避免得到错误的极大值结果。
• 两种方法都会完整遍历所有节点，不会遗漏任何可能的b值，完全不用担心最小值丢失。

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