2022-年算法题-isBST

判断顺序存储的二叉树是否为二叉搜索树

算法如下：

具体C代码：

#include<stdio.h>

typedef struct{
    int SqNode[20];
    int EleNum;
}SqBiTree;

int isBST(SqBiTree T){
    int i=0,j=0,k=0;
    for(i=T.EleNum-1;i>0;i--){
//      printf("%4d%4d\n",i,T.SqNode[i]);
        if(T.SqNode[i]>0){
            k=i;
            while(k>0){
                if(k%2==0)
                    if(T.SqNode[i]<T.SqNode[k/2-1])
                        return 0;
                if(k%2==1)
                    if(T.SqNode[i]>T.SqNode[k/2])
                        return 0;
                if(k%2==0)
                    k=k/2-1;
                else
                    k=k/2;
            }
        }
    }
    return 1;
}

int main(){
    SqBiTree T={
        .SqNode = {20,10,30,5,15,25,35,2,7,12,17,22,27,32,37},
        .EleNum = 15,
    };
    if(isBST(T)==1)
        printf("\nThe T is a BST.\n");
    else
        printf("\nThe T is not a BST.\n");
    return 0;
}