树-前中后序遍历的非递归实现

前、中、后序遍历是对树进行的基础操作,当使用递归来实现时代码非常简单。但是由于递归时会不断将当前状态保存下来,因此空间复杂度较高。下面就介绍一下用非递归的方式如何来实现这些操作。

Binary Tree Travel

二叉树的数据结构定义如下:

  • 前序遍历:非递归遍历通过栈来实现,并且有两种不同的实现方式。思路一是先将根节点压入栈,然后当栈不为空的时候,先将栈顶元素出栈并访问这个节点,然后依次将该节点的右孩子左孩子入栈。代码如下:

思路二则是使用回溯,先遍历完左子树,然后回溯遍历右子树。

  • 中序遍历:和前序遍历的实现非常类似,只不过访问节点的时机不同。
  • 后序遍历:后序遍历是这几种遍历方式中比较麻烦的一种。前面的算法的规律是,当一个节点的左子树已经访问完了后,会将当前节点从栈中直接弹出并访问这个节点,然后再遍历它的右子树。但是后序遍历时,当访问完一个节点的左子树后,先得从栈顶获得这个节点,得到它的右子树并访问右子树,当右子树访问之后,再从栈顶获得这个节点,然后去访问这个节点自身,然后将该节点出栈。可以看出,访问该节点的过程发生了两次,但是只有访问了它的右子树后才可以将这个节点从栈中弹出。因此我们需要标记该节点是否被访问过。代码如下:
  • 层序遍历:作为树的遍历方式的一种,虽然不如前面三种方式常见,但是也是非常有必要了解的。与前面三种方式不同的是,层序遍历使用了队列而不是栈这种结构。思路是:先将根节点入队,当队列不为空的时候,从队列头出队一个元素并访问它,然后将它的左右孩子依次入队。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据