数据结构
2022-41
已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：
typedef struct {
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
} SqBiTTree;T 中不存在的结点在数组 SqBiTNode 中用 -1 表示。例如，对于下图所示的两棵非空二叉树 T1 和 T2，
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回 true，否则，返回 false。要求：
- 给出算法的基本设计思想。
- 根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
答案
（1）建立两个与顺序存储数组等长的辅助数组 pmin 和 pmax，分别记录以各结点为根的子树中的最小值和最大值。先用结点值初始化两个数组，再从最后一个结点向根逆序扫描：左子树的最大值必须小于双亲值，右子树的最小值必须大于双亲值；满足时把相应的最小值或最大值向双亲传播，否则立即返回 false。
（2）
bool judgeBST(SqBiTree bt) {
int k, m, *pmin, *pmax;
pmin = (int *)malloc(sizeof(int) * (bt.ElemNum));
pmax = (int *)malloc(sizeof(int) * (bt.ElemNum));
for (k = 0; k < bt.ElemNum; k++) { // 辅助数组初始化
pmin[k] = pmax[k] = bt.SqBiTNode[k];
}
for (k = bt.ElemNum - 1; k > 0; k--) { // 从最后一个叶结点向根遍历
if (bt.SqBiTNode[k] != -1) {
m = (k - 1) / 2; // 双亲
if (k % 2 == 1 && bt.SqBiTNode[m] > pmax[k]) { // 左孩子
pmin[m] = pmin[k];
} else if (k % 2 == 0 && bt.SqBiTNode[m] < pmin[k]) { // 右孩子
pmax[m] = pmax[k];
} else return false;
}
}
return true;
}时间复杂度为 O(n)，辅助空间复杂度为 O(n)。