深度优先遍历和广度优先遍历二叉树的实现方法

二叉树是一种非常重要的数据结构，在计算机科学中得到广泛的应用。二叉树是一种树形结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。在这篇文章中，我们将探讨二叉树的广度优先遍历和深度优先遍历。

广度优先遍历

广度优先遍历是指按照层级顺序逐层遍历二叉树。从二叉树的根节点开始，逐层遍历每个节点。对于每一层，我们先遍历左子节点，再遍历右子节点。这种遍历方式通常使用队列来实现。

以下是一个二叉树的示例：

广度优先遍历的顺序为：1, 2, 3, 4, 5, 6。遍历过程如下：

将根节点1入队。
从队列中取出1并输出。
将1的左子节点2和右子节点3入队。
从队列中取出2并输出。
将2的左子节点4和右子节点5入队。
从队列中取出3并输出。
将3的右子节点6入队。
从队列中取出4并输出。
从队列中取出5并输出。
从队列中取出6并输出。

深度优先遍历

深度优先遍历是指以深度优先的方式遍历二叉树。从根节点开始，先遍历左子节点，然后遍历右子节点，直到遍历到叶子节点为止。然后返回上一级节点，继续遍历其右子节点。

以下是同一个二叉树的深度优先遍历示例：

深度优先遍历的顺序为：1, 2, 4, 5, 3, 6。遍历过程如下：

访问根节点1。
遍历左子节点2，访问节点2。
遍历左子节点4，访问节点4。
返回上一级节点2，遍历右子节点5，访问节点5。
返回上一级节点1，遍历右子节点3，访问节点3。
遍历右子节点6，访问节点6。

深度优先遍历有三种不同的方式：先序遍历、中序遍历和后序遍历。先序遍历指先遍历访问根节点，然后遍历左子树，最后遍历右子树；中序遍历指先遍历左子树，然后访问根节点，最后遍历右子树；后序遍历指先遍历左子树，然后遍历右子树，最后访问根节点。
下面我们分别来看一下这三种深度优先遍历的实现。

先序遍历

先序遍历的遍历顺序是：根节点 -> 左子树 -> 右子树。

以下是先序遍历的递归实现：

def pre_order_traversal(root):
    if root:
        print(root.val)
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

以下是先序遍历的迭代实现：

def pre_order_traversal(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            print(node.val)
            stack.append(node.right)
            stack.append(node.left)

中序遍历

中序遍历的遍历顺序是：左子树 -> 根节点 -> 右子树。

以下是中序遍历的递归实现：

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.val)
        in_order_traversal(root.right)

以下是中序遍历的迭代实现：

def in_order_traversal(root):
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        print(node.val)
        node = node.right

后序遍历

后序遍历的遍历顺序是：左子树 -> 右子树 -> 根节点。

以下是后序遍历的递归实现：

def post_order_traversal(root):
    if root:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.val)

以下是后序遍历的迭代实现：

def post_order_traversal(root):
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                print(node.val)
            else:
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))