数据结构查找算法实战：顺序、折半及树形查找题解

初始调用时，low 为 1，high 为 ST.length。递归终止条件需仔细处理边界。

矩阵查找技巧

针对行递增、列递增的二维矩阵，可以从右上角开始比较。若当前元素小于目标值，向下寻找；若大于目标值，向左寻找。此方法比较次数不超过 2n 次。

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

树形查找算法

二叉排序树（BST）是树形查找的基础，其中序遍历序列应为递增有序。

判断二叉排序树

利用中序遍历的特性，只需记录前驱节点的值，确保当前节点值始终大于前驱即可。

KeyType predt = -32767;

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;
        predt = bt->data;
        b2 = JudgeBST(bt->rchild);
        return b2;
    }
}

查找结点层次

在 BST 中，查找路径的长度即为结点的层次。非递归查找过程中计数即可。

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

最小与最大关键字

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

特定范围输出

若要按从大到小输出不小于 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 小元素

若每个结点维护了子树大小 count，可快速定位第 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));
    }
}

最大查找长度取决于树的高度，随机生成的 BST 高度约为 O(log2 n)。