用python实现树的遍历

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

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)

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

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=' ')

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