二叉树先序遍历非递归

### 二叉树先序遍历非递归实现

对于二叉树的先序遍历，当采用非递归方式时，通常会利用栈这一辅助数据结构来保存尚未处理过的节点。具体来说，在进入左子树之前应先访问根节点并将其压入栈内，随后继续向左深入直到遇到最左边叶子节点为止；接着回溯至上一层次尝试转向右侧分支重复上述过程直至整个树被完全遍历。

下面给出Python语言下的非递归先序遍历代码实例：

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


def preorder_traversal(root):
    if not root:
        return []

    stack, output = [root], []
    
    while stack:
        node = stack.pop()
        if node is not None:
            output.append(node.value)

            # 注意这里的顺序：因为栈是后进先出，
            # 所以应该先把右边的孩子放入栈中,
            # 这样可以保证下一次循环的时候先进入的是左边孩子.
            if node.right:
                stack.append(node.right)
                
            if node.left:
                stack.append(node.left)

    return output

此段程序定义了一个`TreeNode`类用于构建二叉树节点，并实现了名为`preorder_traversal`函数来进行非递归形式的先序遍历操作[^3]。