二叉树数据结构完全实现(非递归遍历)

最近为了准备考MSE研究生,也顺便复习了一下数据结构的理论知识,其中书中留了一个问题,算是习题吧,叫我们用非递归的方式遍历二叉树。我想既然算是复习,就自己再写一次吧。 二叉树ADT,是一个节点最多可有两个子节点的抽象数据类型,当结点数是N时,树的平均深度是O(根号N),平均查找时间在O(logN)。二叉树在计算机中有着非常广泛的应用,例如数据索引(二叉查找树),编译器设计(表达式树)等等。 遍历二叉树就是用不同的方式,把二叉树里面的数据逐一遍历出来,不同的遍历方式有不同的效果,例如中序遍历,遍历出来的数据一般都是已经排序的,后序遍历可以构建表达式树等。遍历的时候使用递归,当数据量很大时,可能因为应用程序自身的堆栈空间不够而导致程序的崩溃。如果自己建立堆栈的话,不仅可以保证堆栈够用,而且还减少函数调用时保存程序上下文的开销。