数据结构与算法实战：查找算法核心原理与代码实现

7.2.2 题：顺序检索优化策略

题目要求： 线性表中各结点的检索概率不等时，可用如下策略提高顺序检索的效率：若找到指定的结点，则将该结点和其前驱结点 (若存在) 交换，使得经常被检索的结点尽量位于表的前端。试设计在顺序结构和链式结构的线性表上实现上述策略的顺序检索算法。

思路解析： 检索时可先从表头开始向后顺序扫描，若找到指定的结点，则将该结点和其前趋结点 (若存在) 交换。对于链表方式实现的基本思想与上述思想相似，但要注意用链表实现时，在交换两个结点之前需要保存指向前一结点的指针。

核心代码实现：

int SeqSrch(RcdType R[], ElemType k) {
    // 顺序查找线性表，找到后和其前面的元素交换
    int i = 0;
    while ((R[i].key != k) && (i < n)) i++;
    
    if (i < n && i > 0) {
        // 若找到，则交换
        ElemType temp = R[i];
        R[i] = R[i - 1];
        R[i - 1] = temp;
        return --i; // 交换成功，返回交换后的位置
    } else {
        return -1; // 交换失败
    }
}

7.2.3 题：矩阵查找

思路解析： 从矩阵 A 的右上角 (最右列) 开始比较，若当前元素小于目标值，则向下寻找下一个更大的元素；若当前元素大于目标值，则从右往左依次比较，若目标值存在，则只可能在该行中。这种方法利用了矩阵行列有序的特性，效率很高。

核心代码实现：

bool findkey(int A[][N], int n, int k) {
    int i = 0, j = n - 1;
    while (i < n && j >= 0) {
        // 离开边界时查找结束
        if (A[i][j] == k) return true; // 查找成功
        else if (A[i][j] > k) j--;     // 向左移动，在该行内寻找目标值
        else i++;                      // 向下移动，查找下一个更大的元素
    }
    return false; // 查找失败
}

注意： 比较次数不超过 2n 次，时间复杂度为 O(n)，空间复杂度为 O(1)。

树形查找算法

7.3.1 题：判断二叉排序树

题目要求： 试编写一个算法，判断给定的二叉树是否是二叉排序树。

思路解析： 对二叉排序树来说，其中序遍历序列为一个递增有序序列。因此，对给定的二叉树进行中序遍历，若始终能保持前一个值比后一个值小，则说明该二叉树是一棵二叉排序树。这里使用全局变量 predt 来记录前驱节点的值。

核心代码实现：

KeyType predt = -32767; // predt 为全局变量，保存当前结点中序前驱的值，初值为 -∞

int JudgeBST(BiTree bt) {
    int b1, b2;
    if (bt == NULL) return 1; // 空树
    else {
        b1 = JudgeBST(bt->lchild); // 判断左子树是否是二叉排序树
        if (b1 == 0 || predt >= bt->data) return 0; // 若左子树返回值为 0 或前驱大于或等于当前结点，则不是
        predt = bt->data; // 保存当前结点的关键字
        b2 = JudgeBST(bt->rchild); // 判断右子树
        return b2; // 返回右子树的结果
    }
}

7.3.2 题：求指定结点的层次

题目要求： 设计一个算法，求出指定结点在给定二叉排序树中的层次。

思路解析： 设二叉树采用二叉链表存储结构。在二叉排序树中，查找一次就下降一层。因此，查找该结点所用的次数就是该结点在二叉排序树中的层次。采用二叉排序树非递归查找算法，用 n 保存查找层次，每查找一次，n 就加 1，直到找到相应的结点。

核心代码实现：

int level(BiTree bt, BSTNode *p) {
    int n = 0; // 统计查找次数
    BiTree t = bt;
    if (bt != NULL) n++;
    while (t->data != p->data) {
        if (p->data < t->data) // 在左子树中查找
            t = t->lchild;
        else                   // 在右子树中查找
            t = t->rchild;
        n++; // 层次加 1
    }
    return n;
}

7.3.3 题：判断平衡二叉树

题目要求： 用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法。

思路解析： 设置二叉树的平衡标记 balance，以标记返回二叉树 bt 是否为平衡二叉树。采用后序遍历的递归算法：若 bt 为空，高度为 0；若仅有根结点，高度为 1；否则递归计算左右子树的高度和平衡标记。若左右子树的高度差大于 1，则不平衡；若高度差小于或等于 1，且左右子树都平衡时，才平衡。

核心代码实现：

void Judge_AVL(BiTree bt, int &balance, int &h) {
    int bl = 0, br = 0, hl = 0, hr = 0; // 左、右子树的平衡标记和高度
    if (bt == NULL) {
        h = 0; balance = 1; // 空树
    } else if (bt->lchild == NULL && bt->rchild == NULL) {
        h = 1; balance = 1; // 仅有根结点
    } else {
        Judge_AVL(bt->lchild, bl, hl); // 递归判断左子树
        Judge_AVL(bt->rchild, br, hr); // 递归判断右子树
        h = (hl > hr ? hl : hr) + 1;
        if (abs(hl - hr) < 2) // 若子树高度差的绝对值<2
            balance = bl && br; // 左、右子树都平衡时，二叉树平衡
        else
            balance = 0;
    }
}

7.3.4 题：求最小和最大关键字

题目要求： 设计一个算法，求出给定二叉排序树中最小和最大的关键字。

思路解析： 一棵二叉排序树中，最左下结点即为关键字最小的结点，最右下结点即为关键字最大的结点。本算法只要找出这两个结点即可，而不需要比较关键字。利用 BST 的性质直接沿左/右指针走到底。

核心代码实现：

KeyType MinKey(BSTNode *bt) {
    while (bt->lchild != NULL)
        bt = bt->lchild;
    return bt->data;
}

KeyType MaxKey(BSTNode *bt) {
    // 求出二叉排序树中最大关键字结点
    while (bt->rchild != NULL)
        bt = bt->rchild;
    return bt->data;
}

7.3.5 题：输出不小于 k 的关键字

题目要求： 设计一个算法，从大到小输出二叉排序树中所有值不小于 k 的关键字。

思路解析： 由二叉排序树的性质可知，右子树中所有的结点值均大于根结点值，左子树中所有的结点值均小于根结点值。为了从大到小输出，先遍历右子树，再访问根结点，后遍历左子树。这是一种逆中序遍历的变体。

核心代码实现：

void Output(BSTNode *bt, KeyType k) {
    // 本算法从大到小输出二叉排序树中所有值不小于 k 的关键字
    if (bt == NULL) return;
    if (bt->rchild != NULL) Output(bt->rchild, k); // 递归输出右子树结点
    if (bt->data >= k) printf("%d", bt->data);     // 只输出大于或等于 k 的结点值
    if (bt->lchild != NULL) Output(bt->lchild, k); // 递归输出左子树的结点
}

补充： 本题也可采用中序遍历加辅助栈的方法实现。

7.3.6 题：查找第 k 小的元素

思路解析： 所以我们可以对左右子树的搜索采用相同的规则。关键在于维护每个节点的子树大小信息（count），以便快速定位第 k 个元素的位置。

核心代码实现：

BSTNode *Search_Small(BSTNode *t, int k) {
    // 在以 t 为根的子树上寻找第 k 小的元素，返回其所在结点的指针。k 从 1 开始计算
    // 在树结点中增加一个 count 数据成员，存储以该结点为根的子树的结点个数
    if (k < 1 || k > t->count) return NULL;
    if (t->lchild == NULL) {
        if (k == 1) return t;
        else return Search_Small(t->rchild, k - 1);
    } else {
        if (t->lchild->count == k - 1) return t;
        if (t->lchild->count > k - 1) return Search_Small(t->lchild, k);
        if (t->lchild->count < k - 1) return Search_Small(t->rchild, k - (t->lchild->count + 1));
    }
}

补充： 最大查找长度取决于树的高度。由于二叉排序树是随机生成的，其高度应是 O(log₂n)，算法的时间复杂度为 O(log₂n)。