文章

341

粉丝

0

获赞

3

访问

32.0k

头像
2026年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2026年4月28日 00:58
阅读数 29

由于二叉搜索树的中序遍历序列为递增序列,本算法采用中序递归遍历二叉树,并记录当前找到的最小绝对值差值 min
遍历过程中,每访问一个结点时计算目标值与当前结点值之差的绝对值:

  • 若该值小于 min,则更新 min
  • 若该值大于或等于 min,说明后续结点的差值会更大,此时可停止查找(可通过标志变量 flag 控制递归终止)。
// 当前的绝对值差值最小值
int min = INT_MAX;
// 最小绝对值差值是否已经找到
int flag = 0;
// 存储待输出的结点关键字
int min_data[2];
int min_idx = 0;

void searchMinDiff(BTNode *root, int K) {
    if (!root) return;
    if (flag) return;
    searchMinDiff(root->left, K);
    // 中序遍历
    int diff = abs(K - root->data);
    if (diff < min) {
        min = diff;
        min_data[0] = root->data;
        min_idx = 1;
    } else if (diff == min) {
        min_data[min_idx++] = root->data;
    } else {
        flag = 1;
    }
    searchMinDiff(root->right, K);
}

void solve(BTNode *root, int K) {
    searchMinDiff(root, K);
    printf("min diff: %d\n", min);
    for (int i = 0; i < min_idx; i++) {
        printf("min element: %d\n", min_data[i]);
    }
}

 


好的,作为一名改卷老...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发