PreOrder(T): s = InitStack() cur = T while s.not_empty() or cur: while cur: visit(cur) s.push_back(cur) cur = cur.left cur = s.pop() cur = cur.right
// 等价写法，仅使用`if`利用外层循环 PreOrder(T): s = InitStack() cur = T while s.not_empty() or cur: if cur: visit(cur) s.push_back(cur) cur = cur.left else: cur = s.pop() cur = cur.right
基于对遍历性质的考虑
扩展性较好，可以扩展到中序、后序遍历
广度优先入栈：同层右、左节点先后入栈
1 2 3 4 5 6 7 8 9 10
PreOrder(T): s = InitStack() s.push_back(T) while s.not_empty(): cur = s.pop() if cur.right: s.push_back(cur.right) if cur.left: s.push_back(cur.left) visit(cur)
InOrder(T): s = InitStack() cur = T while s.not_empty() or cur: while cur: s.push_back(cur) cur = cur.left cur = s.pop() visit(cur) cur = cur.right
// 等价写法，仅使用`if`利用外层循环 InOrder(T): s = InitStack() cur = T while s.not_empty() or cur: if cur: s.push_back(cur) cur = cur.left else: cur = s.pop() visit(cur) cur = cur.right
后序：需要标记当前节点左、右子树是否被访问
深度优先入栈
节点先入栈后访问，栈内存未访问节点
记录最后一次访问节点，判断右子树是否被访问
（若右子树被访问，右子节点必然是上个被访问节点）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
PostOrder(T): s = InitStack() cur = T last = NULL while s.not_empty() or cur: while cur: s.push_back(cur) cur = cur.left cur = s.top() // 检查右子树是否被访问过 if cur.right == NULLor cur.right == last: visit(cur) last = s.pop() // 此时再弹出`cur` cur = NULL// 置`cur`为`NULL`，否则 // 再次访问左子树，死循环 else: cur = cur.right
# 判断节点是否存在、再填充至队列 LevelTraversal(T): q = InitQueue() cur = T while q.not_empty() or cur: if cur.left: q.push_back(cur.left) if cur.right:d q.push_back(cur.right) visit(cur) cur = q.pop_first()
# 先填充、再判断节点是否为`None` # 填充可保证、适合节点位置和满二叉树对应 LevelTraversal(T): q = InitQueue() q.push(T) # 层次遍历使用队列实现，所以无需像栈一样使用 # 两个判断条件`q.not_empty or cur` while q.not_empty(): cur = q.pop_first() # 弹出时判断节点是否有效 if cur: visit(cur) q.push_back(cur.left) q.push_back(cur.right)
严格分层遍历：记录队列长度、遍历固定长度
1 2 3 4 5 6 7 8 9 10 11 12 13
LevelTraversal(T): q = InitQueue() q.push(T) while q.not_empty(): # 记录当前开始时队列长度 # 每轮遍历该长度数目元素，严格分层遍历节点 for i=0 to len(q): cur_node = q.pop_left() visit(cur_node) if cur.left: q.push_back(cur.left) if cur.right: q.push_back(cur.right)
