二叉树前序遍历的非递归算法

二叉树的前序遍历非递归算法通常使用栈来实现。以下是使用Python实现的示例代码：

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

def preorderTraversal(root):
    if not root:
        return []
    
    stack, result = [root, ], []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # 先右后左入栈，保证左节点先被处理
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

# 示例使用
# 构建一棵二叉树:
#     1
#    / \
#   2   3
#  /
# 4
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4))
root.right = TreeNode(3)

# 执行前序遍历
print(preorderTraversal(root))  # 输出: [1, 2, 4, 3]

在这段代码中，我们定义了一个`TreeNode`类来表示二叉树的节点。`preorderTraversal`函数接收一个二叉树的根节点`root`作为输入，并返回该二叉树的前序遍历结果。我们使用一个栈`stack`来辅助实现非递归遍历，并使用一个列表`result`来保存遍历的结果。在遍历过程中，我们首先将根节点入栈，然后循环进行以下操作：

1. 弹出栈顶元素，将其值添加到结果列表中。

2. 如果该节点有右子节点，则将其右子节点入栈。

3. 如果该节点有左子节点，则将其左子节点入栈。

注意，为了保证左子节点先于右子节点被访问，我们需要先将右子节点入栈，然后再将左子节点入栈。这样，在栈中左子节点就会位于右子节点之上，从而先被处理。

最后，函数返回遍历得到的结果列表。