T41 二叉树的中序遍历 判定是否为二叉搜索树

顺序存储:

• 数组 $A$ 长度为 $n$
• 左子树：下标 $2i+1$
• 右子树：下标 $2i+2$

// 判定是否为二叉搜索树
typedef struct {
  int SqBiTNode[MAXSIZE];
  int ElemNum;
} SqBiTree;
 
// T: 二叉树指针
// index: 当前节点下标
// prev: 上一个访问的节点值
bool inOrderCheck(SqBiTree* T, int index, int *prev) {
  if (index >= T->ElemNum || T->SqBiTNode[index] == -1) return true; // 空节点
  // 检查左子树
  if (!inOrderCheck(T, 2 * index + 1, prev)) return false;
  // 检查当前节点
  if (T->SqBiTNode[index] <= *prev) return false; // 不满足 BST 条件
  *prev = T->SqBiTNode[index];
  // 检查右子树
  if (!inOrderCheck(T, 2 * index + 2, prev)) return false;
  return true;
}
 
bool isBST(SqBiTree T) {
  if (T.ElemNum == 0) return true; // 空树是 BST
  else if (T.SqBiTNode[0] == -1) return true; // 只有根节点是 BST
  int prev = INT_MIN; // 记录上一个访问的节点值
  return inOrderCheck(&T, 0, &prev);
}