二叉树的建立就是依靠递归的原理,所以遍历它访问其路径自然可以首选考虑
但非递归的话就要考虑如何储存返回之前的数据——栈?(递归的底层是靠栈实现的)

中序遍历非递归算法

二叉树中序遍历的非递归算法的关键:在中序遍历过某结点的整个左子树后,如何找的该结点的根以及右子树。

基本思想

  1. 建立一个栈
  2. 根结点进栈,遍历左子树
  3. 根结点出栈,输出根结点,遍历右子树