基于单链表的二叉树非递归遍历算法

王防修，周 康

(武汉工业学院数学与计算机学院，湖北武汉430023)

二叉树是一种重要的非线性数据结构，其应用［1-4］相当广泛。因此，掌握二叉树的各种特性是灵活使用二叉树的基础。在二叉树的所有特性中，二叉树的遍历是需要掌握的重点。传统遍历二叉树的方式一般采用递归遍历算法［5-9］。然而，这种递归遍历算法存在明显缺点：①算法难以反映二叉树被访问的详细过程;②在遍历过程中需要消耗大量系统栈空间;③递归算法比非递归算法需要花费更多的时间。

因此，为了克服二叉树递归遍历算法的这些缺点，相继出现了二叉树的非递归算法［10-17］。从这些论文的内容可以明显发现，所有遍历二叉树的非递归遍历算法都需要借助栈或队列来实现。如二叉树的先序遍历、中序遍历和后序遍历需要借助栈实现非递归算法，而二叉树的层次遍历需要借助队列实现非递归算法。从现有的研究成果可以看出，所有的非递归遍历二叉树的算法都采用静态栈或静态队列来存储节点地址。事实上，在未遍历一棵二叉树之前，是无法知道该二叉树到底包含多少节点的。这直接导致静态栈和静态队列应该分配多大的内存空间才比较合适的问题。如果空间分配太小，就会在遍历过程中出现栈空间或队列空间不足的情形;相反，如果栈空间或队列空间定义过大，对遍历小规模的二叉树又是一种内存空间浪费。因此，如果不能精确定义栈空间和队列空间的大小，就会大大限制二叉树的非递归算法的应用范围和解决实际问题的能力。……