6.3 二叉树的遍历—不用栈的二叉树遍历的非递归方法
前面介绍的二叉树的遍历算法可分为两类，一类是依据二叉树结构的递归性，采用递归调用的方式来实现；另一类则是通过堆栈或队列来辅助实现。采用这两类方法对二叉树进行遍历时，递归调用和栈的使用都带来额外空间增加，递归调用的深度和栈的大小是动态变化的，都与二叉树的高度有关。因此，在最坏的情况下，即二叉树退化为单支树的情况下，递归的深度或栈需要的存储空间等于二叉树中的结点数。
还有一类二叉树的遍历算法，就是不用栈也不用递归来实现。常用的不用栈的二叉树遍历的非递归方法有以下三种：
（1）对二叉树采用三叉链表存放，即在二叉树的每个结点中增加一个双亲域parent，这样，在遍历深入到不能再深入时，可沿着走过的路径回退到任何一棵子树的根结点，并再向另一方向走。由于这一方法的实现是在每个结点的存储上又增加一个双亲域，故其存储开销就会增加。
（2）采用逆转链的方法，即在遍历深入时，每深入一层，就将其再深入的孩子结点的地址取出，并将其双亲结点的地址存入，当深入不下去需返回时，可逐级取出双亲结点的地址，沿原路返回。虽然此种方法是在二叉链表上实现的，没有增加过多的存储空间，但在执行遍历的过程中改变子女指针的值，这既是以时间换取空间，同时当有几个用户同时使用这个算法时将会发生问题。
（3）在线索二叉树上的遍历，即利用具有n 个结点的二叉树中的叶子结点和一度结点的n＋1 个空指针域，来存放线索，然后在这种具有线索的二叉树上遍历时，就可不需要栈，也不需要递归了。有关线索二叉树的详细内容，将在下一节中讨论。
还有一类二叉树的遍历算法，就是不用栈也不用递归来实现。常用的不用栈的二叉树遍历的非递归方法有以下三种：
（1）对二叉树采用三叉链表存放，即在二叉树的每个结点中增加一个双亲域parent，这样，在遍历深入到不能再深入时，可沿着走过的路径回退到任何一棵子树的根结点，并再向另一方向走。由于这一方法的实现是在每个结点的存储上又增加一个双亲域，故其存储开销就会增加。
（2）采用逆转链的方法，即在遍历深入时，每深入一层，就将其再深入的孩子结点的地址取出，并将其双亲结点的地址存入，当深入不下去需返回时，可逐级取出双亲结点的地址，沿原路返回。虽然此种方法是在二叉链表上实现的，没有增加过多的存储空间，但在执行遍历的过程中改变子女指针的值，这既是以时间换取空间，同时当有几个用户同时使用这个算法时将会发生问题。
（3）在线索二叉树上的遍历，即利用具有n 个结点的二叉树中的叶子结点和一度结点的n＋1 个空指针域，来存放线索，然后在这种具有线索的二叉树上遍历时，就可不需要栈，也不需要递归了。有关线索二叉树的详细内容，将在下一节中讨论。
