二叉排序树中查找比给定值大的最小值 - C语言实现

二叉排序树中查找比给定值大的最小值 - C语言实现

本文介绍了在给定的二叉排序树中查找指定的 value 值，并返回比 value 值大的所有值中最小的值。如果 value 值是最大的，即没有比它更大的值，那么算法返回空。

算法思想

1. 从二叉排序树的根节点开始遍历。
2. 如果当前节点的值大于给定值，则记录当前节点的值作为可能的最小值，并继续遍历左子树。
3. 如果当前节点的值小于或等于给定值，则继续遍历右子树。
4. 直到遍历到叶子节点或找到比给定值大的最小值，算法结束。

C语言实现

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

// 二叉搜索树的结点定义
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 创建一个新的二叉搜索树结点
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败");
        exit(1);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入结点到二叉搜索树
struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}

// 在二叉搜索树中查找比给定值大的最小值
int findMinGreater(struct Node* root, int value) {
    int minGreater = -1; // 初始化为-1表示不存在比给定值大的值
    while (root != NULL) {
        if (root->data > value) {
            minGreater = root->data;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return minGreater;
}

int main() {
    struct Node* root = NULL;
    int n, value;
    
    // 创建二叉搜索树，接收输入的结点值
    printf("输入二叉搜索树的结点数量：");
    scanf("%d", &n);
    printf("输入二叉搜索树的结点值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
        root = insert(root, value);
    }
    
    // 查找并输出比给定值大的最小值
    printf("输入要查找的值：");
    scanf("%d", &value);
    int result = findMinGreater(root, value);
    if (result == -1) {
        printf("不存在比给定值大的值\n");
    } else {
        printf("比给定值大的最小值为：%d\n", result);
    }
    
    return 0;
}

注意： 以上代码仅包含了实现上述算法所需的基本功能，实际应用中可能需要根据具体情况进行适当扩展和优化。