简述如何实现二叉树非递归先中后序遍历 ？

非递归实现二叉树的先序、中序和后序遍历，我们通常使用栈这种数据结构来辅助实现。下面分别介绍如何实现这三种遍历方式：

1. 先序遍历 (根左右)

   • 创建一个空栈，并将根节点入栈。
   • 进入循环，直到栈为空：
     • 弹出栈顶元素并访问。
     • 如果该节点有右子节点，将其右子节点入栈。
     • 如果该节点有左子节点，将其左子节点入栈。

2. 中序遍历 (左根右)

   • 创建一个空栈，并将根节点入栈。
   • 进入循环，直到栈为空：
     • 弹出栈顶元素并访问。
     • 如果该节点有右子节点，将其右子节点入栈。
     • 如果该节点有左子节点，将其左子节点入栈，并将当前节点再次入栈（为了保证左子树先遍历完）。

3. 后序遍历 (左右根)

   • 后序遍历的非递归实现相对复杂，因为需要在遍历到根节点之前先遍历其左右子节点。这通常需要使用两个栈或者一个栈和一个临时变量。
   • 使用两个栈的方法：
     • 创建一个空栈s1，并将根节点入栈s1。
     • 创建一个空栈s2。
     • 进入循环，直到s1为空：
       • 弹出s1栈顶元素，并将其入栈s2。
       • 如果该节点有左子节点，将其左子节点入栈s1。
       • 如果该节点有右子节点，将其右子节点入栈s1。
     • 当s1为空时，s2中的元素顺序即为后序遍历的结果，依次弹出并访问。
   • 使用一个栈和一个临时变量的方法：
     • 创建一个空栈，并将根节点入栈。
     • 创建一个临时变量，用于记录当前访问的节点。
     • 进入循环，直到栈为空：
       • 弹出栈顶元素，并判断其是否是其父节点的右子节点：
         • 如果是，则访问该节点。
         • 如果不是，则将该节点再次入栈，并更新临时变量为当前节点的父节点。
       • 如果该节点有左子节点，将其左子节点入栈。
       • 如果该节点有右子节点，将其右子节点入栈。

以上是非递归实现二叉树先序、中序和后序遍历的基本思路。在编写代码时，需要根据具体的编程语言和数据结构进行调整。