二叉树以顺序储存的方式存放，检测该二叉树是否为二叉搜索树_已知非空二叉树t的结点值均为正整数,采用顺序存储 判断是否为二叉搜索树

1. 二叉搜索树也称为二叉排序树，就是任意结点值大于左子树的全部结点值，且小于右子树的全部结点值
2. 若以顺序存储的方式存放，下标之间是有关系的，
   
3. 因为是要检测是否为二叉排序树，所以要查看所有的子树的根是否大于左子树的所有结点的值以及小于右子树所有结点的值，可以想到从叶子结点开始向上检测。

typedef struct TTT{
	int SqBiTNode[MAXSIZE];
	int num;
}SqBiTree;
bool isBST(SqBiTree bt) 
{
	// 因为是顺序存储的，也就是在数组中进行存储，下标之间有关系，
	// 分别进行左右子树的维护，从最后一层开始，二叉搜索树为左边的树比右边的树小（二叉排序树），
	// 每一个结点都有左右子树，所以要分别维护当前结点整个子树的最大最小值
	// 1) 当 当前结点为父结点的左孩子时，父节点要大于 以当前结点的整棵树的最大值
	// 2) 当 当前结点为父结点的右孩子时，父结点要小于 以当前结点的整棵树的最小值
	// 所以要维护以每个结点的整棵树的最大最小值 
	int *pmin,*pmax;
	pmin =  (int*)malloc(sizeof(int)*(bt.num));
	pmax =  (int*)malloc(sizeof(int)*(bt.num));
	
	// 初始化的最大最小等于自身 
	for(int i=0;i<bt.num;i++){
		pmin[i] = pmax[i] = bt.SqBiTNode[i];
	}
	// 从叶子结点往上遍历 
	for(int i=bt.num-1;i>0;i--){
		// 该结点不为空 
		if(bt.SqBiTNode[i] != -1){
			int m = (i-1)/2;          // 获取父结点的下标 
			if(i&1 && bt.SqBiTNode[m]>pmax[i]){  // 若当前结点为左孩子，且父结点比左孩子大，父结点的最大值还等于自身，最小值要维护成左子树的最小值 
				pmin[m] = pmin[i];
			}else if (!(i&1) && bt.SqBiTNode[m]<pmin[i]){  // 若当前结点为右孩子，且父结点比右孩子小，父结点的最小值还等于自身，最大值要维护成右子树的最大值 
				pmax[m] = pmax[i];
			}else {                             // 其他情况：父结点比左子树小或父结点比右子树大，结束 
				return false;
			} 
				
		}
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37