文章
74
粉丝
0
获赞
0
访问
8.6k
(1)算法思想:根据二叉搜索树的定义,只需要确认节点的右孩子比自己小,左孩子比自己大。在进行遍历的时候需要设置一个上下界防止出现右子树的节点比根节点大还要大。
(2)代码:
//辅助递归函数
bool isSearchTree(sqBiTree T,int idx,int sup,int inf){
//当前节点不存在时,下标越界值为-1
if(idx >= T.Elemnum || T.SqBiTNode[idx] == -1){
return true;
}
int val = T,SqBiTNode[idx];//当前节点的值
if(val < inf || val > sup){
return false;
}
//递归检查左子树(下表idx*2+1):更新上界为val-1
//递归检查右子树(下标idx*2+2):更新下界为val+1
return isSearchTree(T,2*idx+1,inf,val - 1) && isSearchTree(T,2*idx+2,val+1,sup);
}
//主函数
bool isBST(SqBiTree T){
if(T.ElemNum==0){
return true;
}
return isSearchTree(T,0,INT_MIN,INT_MAX);
}
评分及理由
(1)得分及理由(满分4分)
学生给出的算法思想基本正确:
扣分点:
得分:3分(基本思想正确但表述不够精确)
(2)得分及理由(满分9分)
学生代码存在以下问题:
登录后发布评论
暂无评论,来抢沙发