当前位置：首页 > article >正文

二叉树的前序、中序、后序遍历（递归和非递归实现）

article 2025/2/22 13:44:48

二叉树，顾名思义，就是一个节点最多有两个子节点的树，要访问二叉树内的所有节点，我们一般有三种方法：前序遍历，中序遍历和后续遍历。

前序遍历：访问顺序为“根-左-右”
中序遍历：访问顺序为“左-根-右”
后序遍历：访问顺序为“左-右-根”

例如下面这颗二叉树：

前序遍历序列为：ABDGCEHIFJ

中序遍历序列为：DGBAHIECFJ

后序遍历序列为：GDBHIEJFCA

1、前序遍历代码

前序遍历的非递归需要用栈实现，实现过程如下：

根节点入栈
栈非空的时候，栈顶元素直接出栈，并将值放入结果中
然后先后访问栈顶元素的右节点和左节点，并入栈（先右后左保证左节点先出）
重复第二步，直到访问完所有元素

代码实现：

def preorder_traversal_iterative(root):
    if root is None:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.value)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

2、中序遍历代码

中序遍历不仅要用到栈，还需要用到一个指针，来记录当前访问的元素，实现过程如下：

将指针初始指向根节点，将所有左节点入栈
弹出栈顶节点，并将节点的值存入结果
访问栈顶元素的右节点

这里要注意循环结束的条件是栈为空且当前指针也指向空。如果指针指向了空，但栈内还有元素，要继续弹出，若栈内没有元素，但当前指针还指向了非空节点，也需要继续入栈。

def inorder_traversal_iterative(root):
    if not root:
        return []
    stack = []
    res = []
    current = root
    while stack or current:
        # 将所有左节点入栈
        while current:
            stack.append(current)
            current = current.left
        # 弹出栈顶元素并访问
        current = stack.pop()
        res.append(current.value)
        current = current.right
    return res

3、后序遍历代码

后序遍历需要用到辅助栈，第一个栈用于模拟遍历过程。第二个栈用于存储结果。实现过程如下：

当遍历的栈非空时，弹出栈顶元素，并将栈顶元素压入存储栈
左节点和右节点先后进入遍历栈
最后输出存储栈

def postorder_traversal_iterative(root):
    if not root:
        return []
    
    stack1 = [root]  # 用于模拟遍历
    stack2 = []  # 用于存储结果
    result = []
    
    while stack1:
        node = stack1.pop()  # 弹出栈顶节点
        stack2.append(node)  # 将节点压入第二个栈
        
        # 左子节点先入栈
        if node.left:
            stack1.append(node.left)
        # 右子节点后入栈
        if node.right:
            stack1.append(node.right)
    
    # 从第二个栈中弹出节点，即为后序遍历结果
    while stack2:
        result.append(stack2.pop().value)
    
    return result

4、递归遍历

递归法比较简单，直接按照顺序写代码就可以了

# 前序遍历
def preorder_traversal(root):
    if root is None:
        return []
    return [root.value] + preorder_traversal(root.left) + preorder_traversal(root.right)


# 中序遍历
def inorder_traversal(root):
    if root is None:
        return []
    return inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)


# 后序遍历
def postorder_traversal(root):
    if root is None:
        return []
    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.value]

5、最后进行测试

# 定义二叉树节点类
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

if __name__ == "__main__":
    # 构建二叉树
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    # 测试遍历函数
    print("前序遍历:", preorder_traversal(root))  # 输出: [1, 2, 4, 5, 3]
    print("中序遍历:", inorder_traversal(root))  # 输出: [4, 2, 5, 1, 3]
    print("后序遍历:", postorder_traversal(root))  # 输出: [4, 5, 2, 3, 1]

    # 测试非递归
    print("非递归前序遍历:", preorder_traversal_iterative(root))  # 输出: [1, 2, 4, 5, 3]
    print("非递归中序遍历:", inorder_traversal_iterative(root))  # 输出: [4, 2, 5, 1, 3]
    print("非递归后序遍历:", postorder_traversal_iterative(root))  # 输出: [4, 5, 2, 3, 1]

都看到这里了，给个小心心♥呗~

查看全文

http://www.kler.cn/a/556152.html