用python实现树的遍历

在Python中实现树的遍历可以通过递归或迭代的方法来完成。树的遍历主要有三种方式：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）和后序遍历（Post-order Traversal）。此外，还有层序遍历（Level-order Traversal），通常使用队列来实现。

以下是一个简单的二叉树节点类和各种遍历方法的实现：

定义二叉树节点类

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

前序遍历（Pre-order Traversal）

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

递归实现

def pre_order_traversal(root):
    if root:
        print(root.value, end=' ')
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

迭代实现

def pre_order_traversal_iterative(root):
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.value, end=' ')
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

中序遍历（In-order Traversal）

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

递归实现

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.value, end=' ')
        in_order_traversal(root.right)

迭代实现

def in_order_traversal_iterative(root):
    stack = []
    current = root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        print(current.value, end=' ')
        current = current.right

后序遍历（Post-order Traversal）

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

递归实现

def post_order_traversal(root):
    if root:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.value, end=' ')

迭代实现

def post_order_traversal_iterative(root):
    if not root:
        return
    stack1 = [root]
    stack2 = []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    while stack2:
        node = stack2.pop()
        print(node.value, end=' ')

层序遍历（Level-order Traversal）

层序遍历的顺序是按层级顺序从上到下，从左到右。

迭代实现

from collections import deque

def level_order_traversal(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

示例

以下是一个示例，展示如何创建一个二叉树并进行各种遍历：

if __name__ == "__main__":
    # 创建一个示例二叉树
    #       1
    #      / \
    #     2   3
    #    / \   \
    #   4   5   6
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)

    print("Pre-order Traversal (Recursive):")
    pre_order_traversal(root)
    print("\nPre-order Traversal (Iterative):")
    pre_order_traversal_iterative(root)

    print("\nIn-order Traversal (Recursive):")
    in_order_traversal(root)
    print("\nIn-order Traversal (Iterative):")
    in_order_traversal_iterative(root)

    print("\nPost-order Traversal (Recursive):")
    post_order_traversal(root)
    print("\nPost-order Traversal (Iterative):")
    post_order_traversal_iterative(root)

    print("\nLevel-order Traversal:")
    level_order_traversal(root)

运行上述代码将输出：

Pre-order Traversal (Recursive):
1 2 4 5 3 6 
Pre-order Traversal (Iterative):
1 2 4 5 3 6 
In-order Traversal (Recursive):
4 2 5 1 3 6 
In-order Traversal (Iterative):
4 2 5 1 3 6 
Post-order Traversal (Recursive):
4 5 2 6 3 1 
Post-order Traversal (Iterative):
4 5 2 6 3 1 
Level-order Traversal:
1 2 3 4 5 6

这些方法展示了如何在Python中实现树的各种遍历方式。