题目

已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct {                    // MAX_SIZE 为已定义常量
    Elemtype SqBiTNode[MAX_SIZE];   // 保存二叉树结点值的数组
    int      ElemNum;               // 实际占用的数组元素个数
} SqBiTree;

T 中不存在的结点在数组 SqBiTNode 中用 -1 表示。例如，对于两棵非空二叉树 T₁ 和 T₂：

二叉树 T₁（满足 BST 定义）：

二叉树 T₂（不满足 BST 定义）：

T₁ 和 T₂ 对应的顺序存储如下（位置从下标 0 起，1-indexed 的层序位置规则：父 i 的左孩子在 2i+1、右孩子在 2i+2）：

数组	内容（依次）	ElemNum
T₁.SqBiTNode	[40, 25, 60, -1, 30, -1, 80, -1, -1, 27]	10
T₂.SqBiTNode	[40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35]	11

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是则返回 true，否则返回 false。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

解析

(1) 设计思想

答案：对顺序存储的二叉树做中序遍历，维护"上一个访问的值" prev。中序序列必须严格递增（即每次访问的当前值 > prev）；任何一处 cur ≤ prev 就直接判定不是 BST。

两个关键点：

• BST 中序遍历严格递增——这是 BST 的等价定义之一。注意必须严格 >，因为题中说"结点值均为正整数"且 BST 通常默认无重复。
• 顺序存储下父子关系：下标 的左孩子在 ，右孩子在 ；越界（）或值为 表示该子树为空，直接返回当作合法。

流程：

1. 初始化 prev = -∞；
2. 从下标 0（根）开始递归中序：先递归左子树（）→ 检查并更新 prev → 再递归右子树（）；
3. 任一步发现 cur ≤ prev 立即返回 false；走完所有结点未触发返回 true。

(2) 代码实现

typedef struct {
    int SqBiTNode[MAX_SIZE];
    int ElemNum;
} SqBiTree;

static int prev_val;        // 上一次中序访问到的值，全局便于递归
static int g_ok;            // 当前判定结果

static void inorderCheck(SqBiTree T, int i) {
    if (i >= T.ElemNum || T.SqBiTNode[i] == -1 || !g_ok) return;
    inorderCheck(T, 2*i + 1);                      // 左子树
    if (T.SqBiTNode[i] <= prev_val) {              // 当前必须严格大于 prev
        g_ok = 0;
        return;
    }
    prev_val = T.SqBiTNode[i];                     // 更新 prev
    inorderCheck(T, 2*i + 2);                      // 右子树
}

int isBST(SqBiTree T) {
    prev_val = INT_MIN;                            // 第一个被访问的结点没有"上一个"，用 -∞
    g_ok = 1;
    inorderCheck(T, 0);
    return g_ok;
}

关键点说明：

• prev 必须是引用语义（这里用 static）：递归中"上一个值"贯穿整次遍历，不能传值副本——否则左子树更新的 prev 进不了右子树。考场里若不想用 static 全局，可以改成传指针 int *prev。
• -1 与越界都是空子树：进入递归先判这两条退出条件，避免对不存在的结点取值或继续递归。
• 触发不合法后立刻短路：检查 !g_ok 提前 return，避免后续递归还在更新 prev、扫描无意义。
• 复杂度：时间 O(n)，每个数组位置最多访问一次（n 是 ElemNum）；空间 O(h)，递归栈深度等于树高，最坏 O(n)。

编者注（生僻术语）：题目说"二叉树 T 中不存在的结点用 -1 表示"——这是顺序存储二叉树的标准约定。本题考点是顺序存储下的中序遍历：链式结构遍历谁都会，但顺序结构下要现场推导父子下标公式（2i+1 / 2i+2），这是真正的得分点。