C++数据结构学习:二叉树(3)
2008-03-08 21:37:18 来源:WEB开发网核心提示:递归遍历与非递归遍历前面写过一些关于递归的文章,因为那时还没有写到树,C++数据结构学习:二叉树(3),因此也举不出更有说服力的例子,只是阐述了“递归是一种思想”,有必要研究如何能使树的高度降低,这就是下面将要讲到的平衡树的来由,正像网友评价的,“一篇入门的文章”
递归遍历与非递归遍历
前面写过一些关于递归的文章,因为那时还没有写到树,因此也举不出更有说服力的例子,只是阐述了“递归是一种思想”,正像网友评价的,“一篇入门的文章”。但只要能能让你建立“递归是一种思想”这个观念,我的努力就没有白费。 现在,讲完了二叉搜索树,终于有了能说明问题的例子了。按照前面提供的代码,应该能调试通过下面的程序。
#include
usingnamespacestd;
#include
#include
#include"BSTree.h"
#include"Timer.h"
#definerandom(num)(rand()%(num))
#definerandomize()srand((unsigned)time(NULL))
#defineNODENUM200000//nodenumber
intdata[NODENUM];
voidzero(int&t){t=0;}
intmain()
{
BSTreea;Timert;randomize();inti;
for(i=0;i
for(i=0;i
t.start();for(i=0;i
cout<<"Inserttime:"<
t.start();for(a.first();a.get()!=NULL;a.next())a.get()->data=0;
cout<<"Non-Stacktime:"<
t.start();a.LevelOrder(zero);cout<<"LevlOrdertime:"<
t.start();a.PReOrder(zero);cout<<"PreOrdertime:"<
t.start();a.InOrder(zero);cout<<"InOrdertime:"<
t.start();a.PostOrder(zero);cout<<"PostOrdertime:"<
return0;
}
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或 以下是timer.h的内容
#ifndefTimer_H
#defineTimer_H
#include
classTimer
{
public:
Timer(){QueryPerformanceFrequency(&Frequency);}
inlinevoidstart(){QueryPerformanceCounter(&timerB);}
inlinedoubleGetTime()
{
QueryPerformanceCounter(&timerE);
return(double)(timerE.QuadPart-timerB.QuadPart)/(double)Frequency.QuadPart*1000.0;
}
private:
LARGE_INTEGERtimerB,timerE,Frequency;
};
#endif
上面的程序中,层次遍历用到的是队列,这应该可以代表用栈消解递归的情况,在我的机器C500上运行的结果是:
Inserttime:868.818Nodenumber:200000
Non-Stacktime:130.811
LevlOrdertime:148.438
PreOrdertime:125.47
InOrdertime:129.125
PostOrdertime:130.914
以上是VC6的release版的结果,时间单位是ms,不说明会有人认为是死机了,^_^。可以看出,递归遍历实际上并不慢,相反,更快一些,而debug版的结果是这样的:
Inserttime:1355.69Nodenumber:200000
Non-Stacktime:207.086
LevlOrdertime:766.023
PreOrdertime:183.287
InOrdertime:179.835
PostOrdertime:190.674
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或 递归遍历的速度是最快的
这恐怕是上面结果得出的最直接的结论。 不知从哪听来的观点“递归的速度慢,为了提高速度,应该用栈消解递归”,证据就是斐波那契数列的计算,遗憾的是斐波那契数列的非递归算法是循环迭代,不是栈消解;假如他真的拿栈来模拟,他就会发现,其实用栈的更慢。
我们来看看为什么。递归的实现是将参数压栈,然后call自身,最后按层返回,一系列的动作是在堆栈上操作的,用的是push、pop、call、ret之类的指令。而用ADT栈来模拟递归调用,实现的还是上述指令的功能,不同的是那些指令对照的ADT实现可就不只是一条指令了。谁都明白模拟的执行效率肯定比真实的差,怎么会在这个问题上就犯糊涂了呢?
当然,你非要在visit函数中加入类似这样的istreamfile1(“input.txt”),然后在用栈模拟的把这个放在循环的外面,最后你说,栈模拟的比递归的快,我也无话可说——曾经就见过一个人,http://www.csdn.net/Develop/Read_Article.asp?Id=18342将数据库连接放在visit函数里面,然后说递归的速度慢。
假如一个递归过程用非递归的方法实现后,速度提高了,那只是因为递归做了一些无用功。比如用循环消解的尾递归,是多了无用的压栈和出栈才使速度受损的;斐波那契数列计算的递归改循环迭代所带来的速度大幅提升,是因为改掉了重复计算的毛病。假使一个递归过程必须要用栈才能消解,那么,完全模拟后的结果根本就不会对速度有任何提升,只会减慢;假如你改完后速度提升了,那只证实你的递归函数写的有问题,例如多了许多重复操作——打开关闭文件、连接断开数据库,而这些完全可以放到递归外面。递归方法本身是简洁高效的,只是使用的人不注重使用方法。
这么看来,研究递归的栈消解似乎是无用的,其实不然,用栈模拟递归还是有点意义的,只是并不大,下面将给出示例来说明。
栈模拟递归的好处是节省了堆栈
将上面的程序//nodenumber那行的数值改为15000——不改没反应了别找我,将//randomswap那行注释掉,运行debug版,耐心的等30秒,就会抛异常了,最后的输出结果是这样的:
Inserttime:27555.5Nodenumber:15000
Non-Stacktime:16.858
LevlOrdertime:251.036
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或
这只能说明堆栈溢出了。你可以看到层次遍历还能工作(由此类推,栈模拟的也能工作),但是递归的不能工作了。这是因为和总的内存空间比起来,堆栈空间是很少的,假如递归的层次过深,堆栈就溢出了。所以,假如你预先感到递归的层次可能过深,你就要考虑用栈来消解了。
然而,假如你必须用递归,而递归的层次深到连堆栈都溢出了,那肯定是你的算法有问题,或者是那个程序根本不适合在PC上运行——运行起来就象死机了,这样的程序谁敢用?所以说用栈模拟递归是有意义的,但是不大,因为很少用到。
对于树结构来说,假如没有双亲指针,那么遍历时的递归是必须的,与其搞什么栈消解不如添加一个双亲指针,这实际上也是用堆空间换取堆栈空间的一个方法,只是比ADT栈来得直接、高效罢了。
综上,递归的栈消解,实际上只能节省堆栈空间,不仅不会提高速度,相反却会降低——天下哪有白吃的午餐,既省了堆栈空间还能提高速度。那些“栈消解递归能提高速度”的谣传只是对“消除尾递归能提高速度”的不负责任的引申,然而一群人以讹传讹,真就像是那么回事了,这就叫三人成虎。等我这时候再回过头看教科书,竟然没看见一本书上写着“栈消解递归能提高速度”。真的,以前一直被误导了,还不知道是被谁误导的——书上根本就没有写。
另外的结论
对比上面两组结果,可以看到插入15000个节点比200000个节点消耗的时间还多,其原因就是插入数据的顺序不同,从而导致了find的效率不同。随机的顺序大致能保证树的左右子树分布均匀,而有序的序列将使树退化成单支的链表,从而使得O(logN)的时间复杂度变成了O(N)。同时,这也是为什么200000个节点的树递归遍历还能工作,而递归遍历15000个节点的树堆栈就溢出了——递归的每一层对应的节点太少了。
为了提高find的效率,同时也是使树的递归遍历方法的使用更为宽泛,有必要研究如何能使树的高度降低,这就是下面将要讲到的平衡树的来由。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或
前面写过一些关于递归的文章,因为那时还没有写到树,因此也举不出更有说服力的例子,只是阐述了“递归是一种思想”,正像网友评价的,“一篇入门的文章”。但只要能能让你建立“递归是一种思想”这个观念,我的努力就没有白费。 现在,讲完了二叉搜索树,终于有了能说明问题的例子了。按照前面提供的代码,应该能调试通过下面的程序。
#include
usingnamespacestd;
#include
#include
#include"BSTree.h"
#include"Timer.h"
#definerandom(num)(rand()%(num))
#definerandomize()srand((unsigned)time(NULL))
#defineNODENUM200000//nodenumber
intdata[NODENUM];
voidzero(int&t){t=0;}
intmain()
{
BSTree
for(i=0;i
for(i=0;i
t.start();for(i=0;i
cout<<"Inserttime:"<
t.start();for(a.first();a.get()!=NULL;a.next())a.get()->data=0;
cout<<"Non-Stacktime:"<
t.start();a.LevelOrder(zero);cout<<"LevlOrdertime:"<
t.start();a.PReOrder(zero);cout<<"PreOrdertime:"<
t.start();a.InOrder(zero);cout<<"InOrdertime:"<
t.start();a.PostOrder(zero);cout<<"PostOrdertime:"<
return0;
}
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或 以下是timer.h的内容
#ifndefTimer_H
#defineTimer_H
#include
classTimer
{
public:
Timer(){QueryPerformanceFrequency(&Frequency);}
inlinevoidstart(){QueryPerformanceCounter(&timerB);}
inlinedoubleGetTime()
{
QueryPerformanceCounter(&timerE);
return(double)(timerE.QuadPart-timerB.QuadPart)/(double)Frequency.QuadPart*1000.0;
}
private:
LARGE_INTEGERtimerB,timerE,Frequency;
};
#endif
上面的程序中,层次遍历用到的是队列,这应该可以代表用栈消解递归的情况,在我的机器C500上运行的结果是:
Inserttime:868.818Nodenumber:200000
Non-Stacktime:130.811
LevlOrdertime:148.438
PreOrdertime:125.47
InOrdertime:129.125
PostOrdertime:130.914
以上是VC6的release版的结果,时间单位是ms,不说明会有人认为是死机了,^_^。可以看出,递归遍历实际上并不慢,相反,更快一些,而debug版的结果是这样的:
Inserttime:1355.69Nodenumber:200000
Non-Stacktime:207.086
LevlOrdertime:766.023
PreOrdertime:183.287
InOrdertime:179.835
PostOrdertime:190.674
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或 递归遍历的速度是最快的
这恐怕是上面结果得出的最直接的结论。 不知从哪听来的观点“递归的速度慢,为了提高速度,应该用栈消解递归”,证据就是斐波那契数列的计算,遗憾的是斐波那契数列的非递归算法是循环迭代,不是栈消解;假如他真的拿栈来模拟,他就会发现,其实用栈的更慢。
我们来看看为什么。递归的实现是将参数压栈,然后call自身,最后按层返回,一系列的动作是在堆栈上操作的,用的是push、pop、call、ret之类的指令。而用ADT栈来模拟递归调用,实现的还是上述指令的功能,不同的是那些指令对照的ADT实现可就不只是一条指令了。谁都明白模拟的执行效率肯定比真实的差,怎么会在这个问题上就犯糊涂了呢?
当然,你非要在visit函数中加入类似这样的istreamfile1(“input.txt”),然后在用栈模拟的把这个放在循环的外面,最后你说,栈模拟的比递归的快,我也无话可说——曾经就见过一个人,http://www.csdn.net/Develop/Read_Article.asp?Id=18342将数据库连接放在visit函数里面,然后说递归的速度慢。
假如一个递归过程用非递归的方法实现后,速度提高了,那只是因为递归做了一些无用功。比如用循环消解的尾递归,是多了无用的压栈和出栈才使速度受损的;斐波那契数列计算的递归改循环迭代所带来的速度大幅提升,是因为改掉了重复计算的毛病。假使一个递归过程必须要用栈才能消解,那么,完全模拟后的结果根本就不会对速度有任何提升,只会减慢;假如你改完后速度提升了,那只证实你的递归函数写的有问题,例如多了许多重复操作——打开关闭文件、连接断开数据库,而这些完全可以放到递归外面。递归方法本身是简洁高效的,只是使用的人不注重使用方法。
这么看来,研究递归的栈消解似乎是无用的,其实不然,用栈模拟递归还是有点意义的,只是并不大,下面将给出示例来说明。
栈模拟递归的好处是节省了堆栈
将上面的程序//nodenumber那行的数值改为15000——不改没反应了别找我,将//randomswap那行注释掉,运行debug版,耐心的等30秒,就会抛异常了,最后的输出结果是这样的:
Inserttime:27555.5Nodenumber:15000
Non-Stacktime:16.858
LevlOrdertime:251.036
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或
这只能说明堆栈溢出了。你可以看到层次遍历还能工作(由此类推,栈模拟的也能工作),但是递归的不能工作了。这是因为和总的内存空间比起来,堆栈空间是很少的,假如递归的层次过深,堆栈就溢出了。所以,假如你预先感到递归的层次可能过深,你就要考虑用栈来消解了。
然而,假如你必须用递归,而递归的层次深到连堆栈都溢出了,那肯定是你的算法有问题,或者是那个程序根本不适合在PC上运行——运行起来就象死机了,这样的程序谁敢用?所以说用栈模拟递归是有意义的,但是不大,因为很少用到。
对于树结构来说,假如没有双亲指针,那么遍历时的递归是必须的,与其搞什么栈消解不如添加一个双亲指针,这实际上也是用堆空间换取堆栈空间的一个方法,只是比ADT栈来得直接、高效罢了。
综上,递归的栈消解,实际上只能节省堆栈空间,不仅不会提高速度,相反却会降低——天下哪有白吃的午餐,既省了堆栈空间还能提高速度。那些“栈消解递归能提高速度”的谣传只是对“消除尾递归能提高速度”的不负责任的引申,然而一群人以讹传讹,真就像是那么回事了,这就叫三人成虎。等我这时候再回过头看教科书,竟然没看见一本书上写着“栈消解递归能提高速度”。真的,以前一直被误导了,还不知道是被谁误导的——书上根本就没有写。
另外的结论
对比上面两组结果,可以看到插入15000个节点比200000个节点消耗的时间还多,其原因就是插入数据的顺序不同,从而导致了find的效率不同。随机的顺序大致能保证树的左右子树分布均匀,而有序的序列将使树退化成单支的链表,从而使得O(logN)的时间复杂度变成了O(N)。同时,这也是为什么200000个节点的树递归遍历还能工作,而递归遍历15000个节点的树堆栈就溢出了——递归的每一层对应的节点太少了。
为了提高find的效率,同时也是使树的递归遍历方法的使用更为宽泛,有必要研究如何能使树的高度降低,这就是下面将要讲到的平衡树的来由。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或
更多精彩
赞助商链接