分别写出二叉树的先序遍历，中序遍历和后序遍历的非递归算法。（给出完整的代码）

二叉树的遍历算法主要有三种：先序遍历、中序遍历和后序遍历。以下是使用栈实现的非递归版本：

1. 先序遍历（根-左-右）：

def preorder_traversal(root):
    if root is None:
        return []
    
    stack = [root]
    result = []

    while stack:
        node = stack.pop()
        result.append(node.val)  # 将节点值添加到结果列表

        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

    return result

# 或者用Python列表推导式简化：
# def preorder_traversal(root): return [node.val for node in preorder_iterative(root)]

# 迭代器函数：
def preorder_iterative(root):
    stack, current = [], root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        yield current.val
        current = current.right

2. 中序遍历（左-根-右）：

def inorder_traversal(root):
    if root is None:
        return []

    stack = []
    result = []
    current = root

    while True:
        while current:
            stack.append(current)
            current = current.left
        if not stack:
            break
        current = stack.pop()
        result.append(current.val)  # 添加节点值
        current = current.right

    return result

# 或者用迭代器表达式简化：
# def inorder_traversal(root): return [node.val for node in inorder_iterative(root)]

# 迭代器函数：
def inorder_iterative(root):
    stack, current = [], root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        yield current.val
        current = current.right

3. 后序遍历（左-右-根）：

def postorder_traversal(root):
    if root is None:
        return []

    stack = [root]
    result = []
    current = None

    while stack:
        node = stack.pop()
        result.append(node.val)  # 将节点值放入结果
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)

        current = node  # 更新当前访问的节点

    # 将最后一个访问的节点值放在最前面，因为后序遍历是先左后右最后根
    result.reverse()

    return result

# 或者用列表推导式简化：
# def postorder_traversal(root): return [node.val for node in postorder_iterative(root)]

# 迭代器函数：
def postorder_iterative(root):
    stack, output = [root], []
    current = None

    while stack:
        node = stack.pop()
        if node is not None:
            output.append(node.val)
            stack.extend([node.right, node.left])
        else:
            current = stack[-1]

    return output[::-1]  # 反转输出顺序