二叉树的遍历也是面试中的经典算法题，是算法相关岗位必须掌握的内容。

但是网上能找到的资料大部分是C/C++的，本文将以Python语言展示二叉树的三种遍历方式的递归与迭代实现方法。

假设有二叉树结构如下图所示：

二叉树

从列表（带终止符的中序列表）创建二叉树

# 定义二叉树类class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Nonedef create_tree(root, lst):    global i    # i不能超出lst范围，并且遇到#意味着到了叶节点，无法继续    if i > len(lst) -1 or lst[i] == '#':        return None    else:        data = lst[i]        root = TreeNode(data)        i += 1        root.left = create_tree(root.left, lst)        i += 1        root.right = create_tree(root.right, lst)    return root

if __name__ == "__main__":    lst = ['1','2','4','#','#','5','#','#','3','#','6','#']    root = TreeNode(0)    i = 0    root = create_tree(root, lst)

1. 前序遍历

1.1 递归实现

前序遍历的顺序是根节点->左子树->右子树，递归实现的代码很简单，按顺序递归打印即可：
凭直观查看，可以知道前序遍历的结果是[1,2,4,5,3,6]

def traversal(root,itype='preorder'):    # 递归遍历主函数    res = []    if itype == 'preorder':        preorder(root,res)    elif itype == 'inorder':        inorder(root, res)    elif itype == 'postorder':        postorder(root,res)    else:        print("Wrong itype.")    print(res)def preorder(root, res):    # 前序遍历    if root is None:        return None    else:        res.append(root.val)        preorder(root.left,res)        preorder(root.right,res)if __name__ == "__main__":    lst = ['1','2','4','#','#','5','#','#','3','#','6','#']    root = TreeNode(0)    i = 0    root = create_tree(root, lst)    traversal(root,itype='preorder')

output:['1', '2', '4', '5', '3', '6']

结果符合预期。

1.2 迭代实现

迭代实现利用了栈的先进后出的性质，反顺序将节点加入，然后再输出。

def preorder_iter(root):    res, stack = [], []    if root is None:        return None    print("结点%s,入栈" % root.val)    stack.append(root)    while len(stack) > 0:        # 因为是中序遍历，所以找到一个节点便可以直接加入列表，然后再去找它的子树        node = stack.pop()        print("结点%s,出栈入表" % node.val)        res.append(node.val)        if node.right:            stack.append(node.right)            print("发现结点%s存在右结点，右结点%s入栈" % (node.val,node.right.val))        if node.left:            stack.append(node.left)            print("发现结点%s存在左结点，左结点%s入栈" % (node.val, node.left.val))    return resif __name__ == "__main__":    lst = ['1','2','4','#','#','5','#','#','3','#','6','#']    root = TreeNode(0)    i = 0    root = create_tree(root, lst)    res = preorder_iter(root)    print(res)

output:结点1,入栈结点1,出栈入表发现结点1存在右结点，右结点3入栈发现结点1存在左结点，左结点2入栈结点2,出栈入表发现结点2存在右结点，右结点5入栈发现结点2存在左结点，左结点4入栈结点4,出栈入表结点5,出栈入表结点3,出栈入表发现结点3存在右结点，右结点6入栈结点6,出栈入表['1', '2', '4', '5', '3', '6']

后面的中序和后序遍历代码类似，所以只介绍一下实现原理，不再逐步分析。

2. 中序遍历

中序遍历的顺序是：左子树-> 根节点 -> 右子树。就这个二叉树而言中序遍历的结果是：[‘4’, ‘2’, ‘5’, ‘1’, ‘3’, ‘6’]
中序遍历的递归实现没什么好讲的，和前序遍历几乎一样

2.1 递归实现

def inorder(root, res):    # 中序遍历    if root is None:        return None    else:        inorder(root.left, res)        res.append(root.val)        inorder(root.right, res)

2.2 迭代实现

迭代实现同样是用到了栈的属性，先找到最左叶子节点，并将沿途的左节点都加入栈中，然后逐步回溯，加入父节点，如果父节点有右子树的话，再添加右子树。

def inorder_iter(root):    res, stack = [], []    node = root    if root is None:        return None    while node or len(stack) > 0:        if node:            # 一直向左，添加所有的左子树值            stack.append(node)            node = node.left        else:            # 逐步回退            node = stack.pop()            res.append(node.val)            # 如果node.right == None会继续回退            # 如果node.right != None则继续寻找node.right是否含有左子树            node = node.right    return res

3. 后序遍历

后序遍历的顺序是左子树-> 右子树-> 根节点，这棵树的后序遍历结果是：[‘4’, ‘5’, ‘2’, ‘6’, ‘3’, ‘1’]

3.1 递归实现

def postorder(root, res):    # 后序遍历    if root is None:        return None    else:        postorder(root.left,res)        postorder(root.right,res)        res.append(root.val)

3.2 迭代实现

后序遍历的迭代方法是在前序遍历的基础上改的，前序遍历是根节点->左子树->右子树，而后序遍历是左子树->右子树->根节点。

所以可以修改前序遍历代码，将遍历左右子树的顺序对调，即可用栈保存一个根节点->右子树->左子树的遍历序列，然后反序输出即可。

def postorder_iter(root):    # 后序迭代遍历    res, stack1, stack2 = [], [], []    if root is None:        return None    stack1.append(root)    while len(stack1) > 0:        node = stack1.pop()        stack2.append(node)        if node.left:            stack1.append(node.left)        if node.right:            stack1.append(node.right)    # 反序输出    while len(stack2) > 0:        node = stack2.pop()        res.append(node.val)    return res