数据结构与算法：查找算法核心原理及实战题目解析

核心代码

int SeqSrch(RcdType R[], ElemType k, int n) {
    int i = 0;
    while ((R[i].key != k) && (i < n)) i++;
    
    if (i < n && i > 0) {
        RcdType temp = R[i];
        R[i] = R[i - 1];
        R[i - 1] = temp;
        return i - 1;
    } else {
        return -1;
    }
}

注意：链表方式实现基本思想相似，但需注意保存指向前一结点的指针，避免断链。

矩阵中的查找

针对行递增、列递增的二维矩阵，可以从右上角开始比较。若当前元素小于目标值，向下寻找更大元素；若大于目标值，向左缩小范围。该策略时间复杂度为 O(n)。

核心代码

bool findKey(int A[][100], 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;
}

树形查找算法实战

二叉排序树判定

二叉排序树的中序遍历序列应为递增有序。利用这一性质，可以在中序遍历过程中维护前驱节点的值，若发现当前值不大于前驱值，则判定不是二叉排序树。

核心代码

KeyType predt = -32767; // 全局变量，保存中序前驱值

int JudgeBST(BiTree bt) {
    if (bt == NULL) return 1;
    int b1 = JudgeBST(bt->lchild);
    if (b1 == 0 || predt >= bt->data) return 0;
    predt = bt->data;
    int b2 = JudgeBST(bt->rchild);
    return b2;
}

查找指定节点的层次

在二叉排序树中，查找路径即对应节点层次。采用非递归查找，每下降一层计数加 1，直到找到目标或为空。

核心代码

int level(BiTree bt, BSTNode *p) {
    int n = 0;
    BiTree t = bt;
    if (bt != NULL) n++;
    while (t != NULL && t->data != p->data) {
        if (p->data < t->data) t = t->lchild;
        else t = t->rchild;
        if (t != NULL) n++;
    }
    return n;
}

平衡二叉树检测

判断平衡二叉树需同时满足左右子树高度差不超过 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) balance = bl && br;
        else balance = 0;
    }
}

极值查找与特定输出

二叉排序树的最小结点在左子树尽头，最大在右子树尽头。基于此特性可快速定位极值。

核心代码

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;
}

若要按从大到小输出所有不小于 k 的关键字，可利用反向中序遍历（右 - 根 - 左）的特性。

核心代码

void Output(BSTNode *bt, KeyType k) {
    if (bt == NULL) return;
    if (bt->rchild != NULL) Output(bt->rchild, k);
    if (bt->data >= k) printf("%d", bt->data);
    if (bt->lchild != NULL) Output(bt->lchild, k);
}

查找第 k 小元素

在扩展了子树节点计数的二叉排序树中，可通过比较左子树节点数与 k 的关系，决定向左、向右还是停留在当前节点。

核心代码

BSTNode *Search_Small(BSTNode *t, int k) {
    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)。