数据结构
2026-41
已知二叉搜索树采用二叉链表存储，类型定义如下：
typedef struct BSTNode //二叉搜索树结点
{ int data; //保存结点的关键字值
struct BSTNode * left, * right; //指向左孩子、右孩子的指针
} BinTNode;
typedef BinTNode * BTree; //二叉搜索树对于给定的非空二叉搜索树 T（root 为指向 T 的根结点的指针）和整数 k，请设计尽可能高效的查找算法：
void searchX( BTree root, int k )
查找 T 中其关键字值与 k 之差的绝对值最小的所有结点，输出差值的绝对值和结点中的关键字值。要求：
（1）给出算法的基本设计思想。（4 分）
（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（9 分）
小程序中我的-账号中心-隐私与账号可绑定网页端账号
答案
（1）算法的基本设计思想
按照在二叉搜索树中查找目标 k 的方法，从根开始沿着某条向下的路径进行查找。若当前结点中的关键字值与 k 相等，则结果只包含一个结点，差值的绝对值为 0，不相等时，结果最多包含两个结点，差值的绝对值大于 0。
对于不相等的情况，若当前结点中的关键字值大于 k，则结果只可能是当前结点或/及左子树中的结点，此时沿 left 指针继续查找。若当前结点中的关键字值小于 k，则结果只可能是当前结点或/及右子树中的结点，此时沿 right 指针继续查找。直到遇到空指针时为止。
（2）算法实现
void searchX( BTree root, int k )
{ BTree p = root, pmin1, pmin2;
int min = MAX; //MAX 为能表示的整型最大值
if ( p == NULL ) return; //若为空树，则返回
while( p != NULL )
{ if ( p->data == k ) //结果只包含一个结点
{ min = 0;
printf ( "差值绝对值 = %d 结点 = %d\n", min, p->data );
return;
}
else if ( abs( p->data-k ) < min ) //出现差值绝对值更小的结点
{ min = abs( p->data-k );
pmin1 = pmin2 = p;
}
else if ( abs( p->data-k ) == min ) //出现另一个差值绝对值为 min 的结点
pmin2 = p;
if ( p->data > k )
p = p->left; //若当前结点的 data>k，则结果还可能在左子树中
else
p = p->right; //若当前结点的 data<k，则结果还可能在右子树中
}
if ( pmin1->data != pmin2->data )
printf ( "差值绝对值 = %d 结点 1 = %d 结点 2 = %d\n",
min, pmin1->data, pmin2->data );
else
printf ( "差值绝对值 = %d 结点 = %d\n", min, pmin1->data );
return;
}该年份真题解析暂未更新