用非递归算法前序遍历完全二叉树

前序遍历（Preorder Traversal）是一种二叉树的遍历方式，其顺序为：根节点 -> 左子树 -> 右子树。对于完全二叉树，我们可以通过非递归的方式来实现前序遍历。

非递归算法通常使用栈（Stack）来实现。这是因为栈是一种后入先出（LIFO）的数据结构，可以用来模拟递归的堆栈退栈过程。

以下是使用Python实现完全二叉树前序遍历的非递归算法：

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

def preorder_traversal(root):
    res = []
    stack = [root]

    while stack:
        node = stack.pop()
        if node:
            res.append(node.val)
            # 由于是完全二叉树，所以左子节点只可能在根节点的左子树中存在，所以需要跳过根节点的右子树和空节点
            if node.left:
                stack.append(node.left)
            if node.right and node != root:  # 跳过根节点右子树中的空节点
                stack.append(node.right)
    return res

在这个算法中，我们首先创建一个栈并将根节点放入栈中。然后，我们进入一个循环，该循环会持续到栈为空为止。在每次循环中，我们从栈顶弹出一个节点，并将其值添加到结果列表中。然后，我们将该节点的左子节点（如果存在）放入栈中，如果该节点有右子节点且不是根节点（即不是空节点），那么也将右子节点放入栈中。这是因为完全二叉树的特性使得我们只需要遍历非空节点的左子树和对应的右子树即可。

这个算法的时间复杂度是O(n)，其中n是二叉树的节点数，因为我们最多只需要访问每个节点一次。空间复杂度也是O(n)，因为我们需要使用一个栈来存储节点。尽管看起来我们创建了一个临时列表来存储结果，但这只是一个方便我们输出的操作，不会额外占用空间。