使用堆栈无需递归就能遍历二叉树，下面是一个使用堆栈中序遍历二叉树的算法。
算法思路
1)创建一个空栈S。
2）将当前节点初始化为root
3)将当前节点推入S并设置current=current->left直到current为NULL
立即学习“Python免费学习笔记（深入）”；
4)如果current为NULL且堆栈不为空，则
a)从堆栈中弹出顶部项目。
b)输出弹出的项目，设置current=popped_item->right
c)转到步骤3)。
5)如果current为NULL并且stack为空，那么算法结束。
算法实现步骤
1
/\
2 3
/\
4 5
步骤1创建一个空堆栈：S=NULL
步骤2将current设置为root的地址：current->1
步骤3推送当前节点并设置current=current->left
直到当前为NULL
当前->1
推1：堆栈S->1
当前->2
推2：堆栈>2,1
当前->4
推4：堆栈S>4、2、1
当前=NULL
步骤4从S弹出
a)弹出4：堆栈S->2,1
b)打印“4”
c)current=NULL/*right of 4*/并转到步骤3
由于current is NULL step 3没有做任何事情。
步骤4再次弹出。
a)弹出2：堆栈S->1
b)打印“2”
c)current->;5/*right of 2*/并转到步骤3
第3步将5推入堆栈并使当前为NULL
堆栈S->5,1
当前=NULL
步骤4从S弹出
a)弹出5：堆栈S->1
b)打印“5”
c)current=NULL/*right of 5*/并转到步骤3
由于current is NULL step 3没有做任何事情
步骤4再次弹出。
a)弹出1：堆栈S->NULL
b)打印“1”
c)当前->3/*1的右边*/
第3步将3推入堆栈并使当前为NULL
堆栈S->3
当前=NULL
步骤4从S弹出
a)弹出3：堆栈S->NULL
b)打印“3”
c)current=NULL/*3的右边*/
由于堆栈S为空且当前为NULL，因此遍历已完成。
Python实现堆栈中序遍历二叉树
class Node: def __init__(self,data): self.data=data self.left=None self.right=None def inOrder(root): current=root stack=[] while True: if current is not None: stack.append(current) current=current.left elif(stack): current=stack.pop() print(current.data,end="") current=current.right else: break print() root=Node(1) root.left=Node(2) root.right=Node(3) root.left.left=Node(4) root.left.right=Node(5) inOrder(root)
