n个结点的完全二叉树顺序存储在一维数组a中，设计一个算法，实现对此二叉树的先序遍历。 【输入形式】一维数组a，以#结束输入，请接收后存储在一维数组a中

顺序存储完全二叉树的方式存储 【输出形式】二叉树先序遍历结果 【算法思路】 对于完全二叉树，按照从上到下、从左到右的顺序存储在数组中，可以得到以下结论：

- 对于第i个节点，它的左子节点在数组中的下标是2i，右子节点在2i+1（i从1开始计数）。
- 如果数组中最后一个节点的下标是n，那么树的高度为log2(n)，并且从第n/2个节点开始到第n个节点是所有叶子节点。

因此，可以从根节点开始遍历二叉树。假设当前节点在数组中的下标是i，那么它的左节点在下标2i处，右节点在2i+1处。先将当前节点的值输出，然后递归遍历左子树和右子树即可。

【算法实现】

void preorder(int *a, int i, int n)
{
    if (i > n) return;
    printf("%d ", a[i]);
    preorder(a, 2*i, n);
    preorder(a, 2*i+1, n);
}

主函数中调用preorder函数：

int main()
{
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(a) / sizeof(int) - 1;
    preorder(a, 1, n);
    return 0;
}

【算法分析】【时间复杂度】时间复杂度为O(n)，n为二叉树的节点数。每个节点最多遍历一次。

【空间复杂度】空间复杂度为O(h)，h为二叉树的高度，为log2(n)

【算法优化】使用非递归实现可以节省函数调用栈空间。可以用一个栈来保存需要遍历的节点，每次从栈中取出一个节点，输出其值后将其右节点和左节点压入栈中，这样下一次从栈中取出的就是左节点。遍历结束的条件是栈为空。