考研笔记

板子：判断二叉排序树（2022）

BST 的中序序列是严格递增的。中序遍历时记住上一个访问的结点 pre，一旦当前值 pre 的值，就不是 BST。

代码：二叉链表

bool isBST(BiTree T, BiTNode *&pre) {        // 调用前 pre = NULL；pre：中序遍历的上一个结点
    if (T == NULL) return true;              // 空树是 BST
    if (!isBST(T->lchild, pre)) return false;               // 左子树不是 BST，直接失败
    if (pre != NULL && pre->data >= T->data) return false;  // 当前值不大于前一个：不是严格递增
    pre = T;                                 // 当前结点成为下一个结点的「上一个」
    return isBST(T->rchild, pre);
}
// 调用：BiTNode *pre = NULL;  isBST(T, pre);

pre 要写成引用 BiTNode *&pre：递归里改了它，外层要能看到。

代码：顺序存储（2022 原题）

#define MAX_SIZE 100
typedef struct {                             // 2022 原题给的结构
    int SqBiTNode[MAX_SIZE];                 // 结点值都是正整数，不存在的结点用 -1 表示
    int ElemNum;                             // 数组中元素的个数
} SqBiTree;
 
bool judgeBST(SqBiTree &bt, int k, int &pre) {   // 中序遍历下标为 k 的子树；调用前 pre = 0
    if (k >= bt.ElemNum || bt.SqBiTNode[k] == -1) return true;   // 超出数组或结点不存在：空树
    if (!judgeBST(bt, 2 * k + 1, pre)) return false;             // 左孩子的下标是 2k+1
    if (bt.SqBiTNode[k] <= pre) return false;                    // 不是严格递增
    pre = bt.SqBiTNode[k];
    return judgeBST(bt, 2 * k + 2, pre);                         // 右孩子的下标是 2k+2
}
// 调用：int pre = 0;  judgeBST(bt, 0, pre);

复杂度：两种都是时间 ，空间 。

关键边界

位置为什么
孩子下标 、数组从 0 开始存根。如果从 1 开始存，孩子是 、
pre 初值为 0原题保证结点值都是正整数，所以 0 比任何结点都小
判失败用 >= / <=要求严格递增，值相等也不是 BST
k >= bt.ElemNum 先判下标越界时就不能再读 SqBiTNode[k] 了

易错点

  • 只比较父子是不够的。例如根为 10，左孩子为 5，5 的右孩子为 15：每一对父子都满足大小关系，但 15 在 10 的左子树里。必须用中序，或者给每个结点传下上下界。
  • 顺序存储时，SqBiTree 用引用传参，避免每层递归都复制一遍整个数组。原题答案按值传也对。

链接

反向链接