二叉树遍历算法详解：前序、中序、后序与层序遍历

创作时间:

作者:

@小白创作中心

二叉树遍历算法详解：前序、中序、后序与层序遍历

引用

CSDN

https://blog.csdn.net/qq_41768644/article/details/141652061

二叉树遍历是数据结构与算法中的基础且重要的一环，掌握二叉树的前序、中序、后序和层序遍历方法，不仅能帮助理解二叉树的结构特性，也是解决许多算法问题的关键。本文将通过实例代码和详细解析，带你全面掌握二叉树的各种遍历方式。

一、二叉树创建

首先，我们定义一个二叉树节点类TreeNode，并创建一个示例二叉树：

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def createTree():
    treeRoot = TreeNode('F')
    NodeB = TreeNode('B')
    NodeG = TreeNode('G')
    treeRoot.left = NodeB
    treeRoot.right = NodeG
    NodeA = TreeNode('A')
    NodeD = TreeNode('D')
    NodeB.left = NodeA
    NodeB.right = NodeD
    NodeC = TreeNode('C')
    NodeE = TreeNode('E')
    NodeD.left = TreeNode('C')
    NodeD.right = TreeNode('E')
    NodeI = TreeNode('I')
    NodeH = TreeNode('H')
    NodeG.right = NodeI
    NodeI.left = NodeH
    return treeRoot

二、遍历算法详解

1. DLR 前序遍历（根，左，右）

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。递归实现如下：

def preOrder(treeRoot):
    print(treeRoot.data, end="  ")
    if treeRoot.left is not None:
        preOrder(treeRoot.left)
    if treeRoot.right is not None:
        preOrder(treeRoot.right)

2. LDR 中序遍历（左、根、右）

中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树。递归实现如下：

def inOrder(treeRoot):
    if treeRoot.left is not None:
        inOrder(treeRoot.left)
    print(treeRoot.data, end="  ")
    if treeRoot.right is not None:
        inOrder(treeRoot.right)

3. LRD 后序遍历（左，右，根）

后序遍历首先遍历左子树，然后遍历右子树，最后访问根节点。递归实现如下：

def postOrder(treeRoot):
    if treeRoot.left is not None:
        postOrder(treeRoot.left)
    if treeRoot.right is not None:
        postOrder(treeRoot.right)
    print(treeRoot.data, end="  ")

4. 层序遍历

层序遍历从根节点开始，逐层从左到右访问节点，使用队列实现：

def levelOrder(treeRoot):
    q = []
    q.append(treeRoot)
    while len(q) != 0:
        node = q.pop(0)
        print(node.data, end="  ")
        if node.left is not None:
            q.append(node.left)
        if node.right is not None:
            q.append(node.right)

三、执行结果

if __name__ == '__main__':
    treeRoot = createTree()
    preOrder(treeRoot)
    print("\n############################")
    inOrder(treeRoot)
    print("\n############################")
    postOrder(treeRoot)
    print("\n############################")
    levelOrder(treeRoot)

输出结果：

F  B  A  D  C  E  G  I  H
############################
A  B  C  D  E  F  G  H  I
############################
A  C  E  D  B  H  I  G  F
############################
F  B  G  A  D  I  C  E  H