使用堆栈无需递归就能遍历二叉树，下面是一个使用堆栈中序遍历二叉树的算法。
算法思路
1)创建一个空栈S。
2）将当前节点初始化为root
3)将当前节点推入S并设置current=current->left直到current为NULL
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)
登录后复制
以上就是用Python实现堆栈中序遍历二叉树的详细步骤的详细内容，更多请关注每日运维网(www.mryunwei.com)其它相关文章！
