1.一棵具有n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行中序遍历。 输入： 输入完全二叉树的元素个数（以-1结束整个程序的运行）： 输入二叉树的结点数据： 输出： 中序遍历序列

对于完全二叉树的中序遍历，我们可以利用其特殊性质，即除了最后一层外，其他所有层次都是满的，并且如果最右边的节点不满，则从左到右放置。这种结构使得我们可以通过顺序遍历数组的方式来模拟二叉树的中序遍历。

以下是非递归算法的伪代码描述：

1. 初始化两个指针：`index` 表示当前访问的位置（开始于0），`prev` 表示上一个访问过的节点位置（初始值为-1）。
2. 当输入的元素不是-1时，继续遍历：
a. 如果当前元素（`tree[index]`）小于根节点，说明还没到左子树，将 `prev` 更新为当前索引，然后向左移动 `index` 到下一个元素。
b. 如果当前元素等于根节点，输出它并更新 `prev` 为当前索引，然后交换 `index` 和 `prev` 的位置，因为根节点之后就是左子树。
c. 如果当前元素大于根节点，说明已经访问完左子树，输出它作为根节点，然后直接移动 `index` 到下一位，因为不需要检查右子树。
3. 循环结束后，输入变为-1，跳出循环。

**具体Python实现（假设输入数组是 tree[]）：**

def inorder_traversal(tree, n):
    prev = -1
    while n != -1:
        if tree[prev + 1] < tree[n]:
            prev = n
            n -= 1
        else:
            print(tree[n])  # 输出当前节点
            if prev != -1:  # 跳过左子树
                n = prev
            else:
                n -= 1
    return

# 示例输入：[8, 5, 10, 1, 6, null, null, 4, 7, null, 9]
inorder_traversal(your_input_tree, len(your_input_tree))