24
Mar
March 24, 2011 分类: ASM/C/C++     作者: hoverlees     留言: 5

最近为了准备考MSE研究生,也顺便复习了一下数据结构的理论知识,其中书中留了一个问题,算是习题吧,叫我们用非递归的方式遍历二叉树。我想既然算是复习,就自己再写一次吧。

二叉树ADT,是一个节点最多可有两个子节点的抽象数据类型,当结点数是N时,树的平均深度是O(根号N),平均查找时间在O(logN)。二叉树在计算机中有着非常广泛的应用,例如数据索引(二叉查找树),编译器设计(表达式树)等等。

遍历二叉树就是用不同的方式,把二叉树里面的数据逐一遍历出来,不同的遍历方式有不同的效果,例如中序遍历,遍历出来的数据一般都是已经排序的,后序遍历可以构建表达式树等。遍历的时候使用递归,当数据量很大时,可能因为应用程序自身的堆栈空间不够而导致程序的崩溃。如果自己建立堆栈的话,不仅可以保证堆栈够用,而且还减少函数调用时保存程序上下文的开销。


查看详细内容 »

快速链接
推荐标签
最新图片
较新文章
随机推荐
友情链接