这里先对二叉树的形式做个定义：
class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None二叉树的四种遍历方式：
a / \ b c / \ d e 先序遍历：每次遍历树时先访问当前节点，再按照这种方式依次遍历左子树和右子树。上图遍历结果为：abdec中序遍历：每次遍历树时先遍历左子树，再访问当前节点，最后遍历右子树。上图遍历结果为：dbeac后序遍历：每次遍历树时先遍历左子树，再遍历右子树，最后访问当前节点。上图遍历结果为：debca层序遍历：按照从上往下，从左到右的顺序遍历。上图遍历结果为：abcde在递归写法中，通过函数调用栈保存了程序的中间数据。非递归写法则必须借助一个辅助的栈：
# -*- coding: UTF-8 -*- from collections import deque class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None class Tree: def __init__(self): self.root = None def show(self): return def construct(self, li = None): if not li: return None tl = [] for i in li: if i is None: tl.append(None) else: tl.append(TreeNode(i)) for idx in range(len(li) / 2): if idx * 2 + 1 < len(tl) and tl[idx * 2 + 1]: tl[idx].left = tl[idx * 2 + 1] if idx * 2 + 2 < len(tl) and tl[idx * 2 + 2]: tl[idx].right = tl[idx * 2 + 2] self.root = tl[0] def preOrder(self, cur): if not cur: return stack = [] stack.append(cur) while stack: cur = stack.pop() if not cur: continue print(cur.val) stack.append(cur.right) stack.append(cur.left) def inOrder(self, cur): if not cur: return stack = [] while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() print(cur.val) cur = cur.right def postOrder(self, cur): if not cur: return stack = [] stack2 = [] while stack2 or cur: while cur: stack.append(cur) stack2.append(cur) cur = cur.right cur = stack2.pop() cur = cur.left while stack: cur = stack.pop() print(cur.val) def levelOrder(self, cur): dq = deque() dq.append(cur) while dq: tmp = dq.popleft() if not tmp: continue print(tmp.val) dq.append(tmp.left) dq.append(tmp.right) l = [2, 3, 4, 5, None, 7] t = Tree() t.construct(l) print("pre order:") t.preOrder(t.root) print("in order:") t.inOrder(t.root) print("post order:") t.postOrder(t.root) print("level order:") t.levelOrder(t.root)