关于判断二叉查找树算法的问题:
清华大学出版社出版的由王春森主编的软考指定教材《系统设计师(高级程序员)教程》一书的P442页是一个判断一颗二叉树是不是二叉查找树的函数,我对此函数的运行结果有一些疑问,想请教一下各位高手,希望大家能够赐教,我这里先谢谢大家了。问题如下:
ins isSearchtree(NODE *t, int *minp, int *maxp)
{
int lmin,lmax,rmin,rmax;
if(t==NULL) return 1;
lmin=lmax=t->val;
if(t->lchild){
if(isSearchtree(t->lchild,&lmin,&lmax)==0) return 0;
if(t->val<=lmax)return 0;
}
rmin=rmax=t->val;
if(t->rchild){
if(isSearchtree(t->rchild,&rmin,&rmax)==0) return 0;
if(t->val>=rmin)return 0;
}
*minp=lmin;
*maxp=rmax;
return 1;
}
假定我们对如下二叉树(1,2,3,4,5,6,7)进行判定:
4
/\
2 6
/\ /\
1 3 5 7我推导的过程是这样的:
刚进入函数时:
lmin=lmax=4,然后递归调用的结果是:
lmin=lmax=2 再次递归调用的结果为:
lmin=lmax=1,由于1的孩子为空进入下一个赋值
rmin=rmax=1由于1的孩子为空进入下一个赋值
*minp=lmin=1; *maxp=rmax=1;将结果返回到上一层调用
**** 而此时的if(t->val<=lmax)return 0;判断由于lmax=2=t-val而结束整个判断,这是我的第一个疑问
****疑问二假定上边的判断不结束整个程序,那么由(*minp=lmin=1; *maxp=rmax=1;将结果返回到上一层调用)带回的minp 和maxp两个参数最终是什么值,它在整个程序中的作用是什么?
****疑问三lmin=lmax=t->val;和rmin=rmax=t->val;在程序中的作用能否只用一组lmin和rmin来代替,我没有看出来这样的最小和最大的值是在什么时时候被修改成不一样的(因为我没有在程序中发现对这样的参数有单独赋值的语句,所以我认为这样的值没有什么区别,比如按照我上边的推导下边将出现rmin=lmax=2的赋值,二者的值还是一样)。
清华大学出版社出版的由王春森主编的软考指定教材《系统设计师(高级程序员)教程》一书的P442页是一个判断一颗二叉树是不是二叉查找树的函数,我对此函数的运行结果有一些疑问,想请教一下各位高手,希望大家能够赐教,我这里先谢谢大家了。问题如下:
ins isSearchtree(NODE *t, int *minp, int *maxp)
{
int lmin,lmax,rmin,rmax;
if(t==NULL) return 1;
lmin=lmax=t->val;
if(t->lchild){
if(isSearchtree(t->lchild,&lmin,&lmax)==0) return 0;
if(t->val<=lmax)return 0;
}
rmin=rmax=t->val;
if(t->rchild){
if(isSearchtree(t->rchild,&rmin,&rmax)==0) return 0;
if(t->val>=rmin)return 0;
}
*minp=lmin;
*maxp=rmax;
return 1;
}
假定我们对如下二叉树(1,2,3,4,5,6,7)进行判定:
4
/\
2 6
/\ /\
1 3 5 7我推导的过程是这样的:
刚进入函数时:
lmin=lmax=4,然后递归调用的结果是:
lmin=lmax=2 再次递归调用的结果为:
lmin=lmax=1,由于1的孩子为空进入下一个赋值
rmin=rmax=1由于1的孩子为空进入下一个赋值
*minp=lmin=1; *maxp=rmax=1;将结果返回到上一层调用
**** 而此时的if(t->val<=lmax)return 0;判断由于lmax=2=t-val而结束整个判断,这是我的第一个疑问
****疑问二假定上边的判断不结束整个程序,那么由(*minp=lmin=1; *maxp=rmax=1;将结果返回到上一层调用)带回的minp 和maxp两个参数最终是什么值,它在整个程序中的作用是什么?
****疑问三lmin=lmax=t->val;和rmin=rmax=t->val;在程序中的作用能否只用一组lmin和rmin来代替,我没有看出来这样的最小和最大的值是在什么时时候被修改成不一样的(因为我没有在程序中发现对这样的参数有单独赋值的语句,所以我认为这样的值没有什么区别,比如按照我上边的推导下边将出现rmin=lmax=2的赋值,二者的值还是一样)。
解决方案 »
- 窗口销毁问题
- SOCKET编程中遇到的问题(聊天程序)
- 响应村长号召坚决鄙视鸟人
- 请问:一个多线程内存访问的问题?
- 在线等CTimeSpan类的对象怎么打印出来?CTimeSpan time.format怎么写?
- QQ中文件传输的一个问题
- 为什么显示空白呢?CListCtrl中的项添加图标,谢谢好心人的赐教了!谢谢!
- 如何让线程终止,不用while等循环检测,各位高手给点建议。
- 一个奇怪的问题,请大家看一下,但我没有分送,因为我还是个新手,没分可送!
- c新手实现象棋的规则
- 請教高手, 一個文件打開後, 可不可以有一個讀的位置, 有一個寫的位置, 使它變成一個隊列?
- for update的触发器语句应该如何写!!???
要下班了,看完第一个疑问:
****而此时的if(t->val<=lmax)return 0;判断由于lmax=2=t-val而结束整个判断,这是我的第一个疑问*****
这个时候的lmax=1(而不是2,因为*maxp=rmax),t->val=2,所以不会结束整个判断,而是进行右子树的判断。
我觉得最好的办法就是写出程序来实地的调试一把,一定能搞定!