第 41 题
（本题满分 13 分）假定二叉搜索树使用二叉链表存储，存储结构如下：typedef struct BSTNode{int data;struct BSTNode *left,*right;} BSTNode;typedef BSTNode BTNode;给一棵二叉搜索树 T 和整数 K，查找树中关键字与 K 之差的绝对值最小的所有结点，并输出该绝对值与结点中的关键字。
（1）给出算法的基本思想。（4 分）
（2）使用 C/C++ 描述算法思想。（8 分）
[tag_link]
【答案】
(1)算法设计思想：由于二叉搜索树的中序遍历序列为递增序列，本算法采用中序递归遍历二叉树，并记录当前找到的最小绝对值差值 min。遍历过程中，每访问一个结点时计算目标值与当前结点值之差的绝对值：
- 若该值小于
min，则更新min； - 若该值大于或等于
min，说明后续结点的差值会更大，此时可停止查找（可通过标志变量flag控制递归终止）。最后输出所有差值为min的结点。注意：题目要求输出与目标值差的绝对值最小的所有结点，可能不止一个结点。例如下图中：结点 5、15 与目标值 10 的差的绝对值均为 5，此时应全部输出。满足条件的结点最多只可能有两个。
10
/ \
5 15
(2) 算法实现：
// 当前的绝对值差值最小值
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]);
}
}