假设非空二叉树采用顺序存储结构，每个结点值为单个字符。设计一个算法输出编号为i的结点的所有祖先结点值。

### 回答1：
假设非空二叉树采用顺序存储结构，每个结点值为单个字符。要输出编号为i的结点的所有祖先结点值，可以按照以下步骤进行：

1. 计算结点i的父结点编号：如果i是根结点，则无父结点；否则，父结点编号为(i-1)/2。

2. 从父结点开始，依次向上遍历二叉树，输出每个祖先结点的值，直到根结点为止。

具体实现时，可以使用一个循环来实现向上遍历，每次计算当前结点的父结点编号，并将当前结点更新为父结点，直到遍历到根结点为止。输出祖先结点的值可以使用一个数组或链表来保存，也可以直接打印输出。

### 回答2：
非空二叉树采用顺序存储结构，可以将二叉树中的每一个结点按照层次顺序进行编号，编号从1开始向下逐个增加，若某个结点编号为i，则其左孩子结点的编号为2i，右孩子结点的编号为2i+1。这样，每个结点的编号对应了该结点在顺序存储结构中的位置。

根据这个编号规律，可以设计一个算法输出编号为i的结点的所有祖先结点值。具体实现步骤如下：

1. 首先通过编号i计算出该结点在数组中的索引index，即index = i-1。
2. 从该结点的父结点开始，依次输出每一个祖先结点的值。
1）若该结点的编号为奇数，则父结点编号为 (i-1)/2；
2）若该结点的编号为偶数，则父结点编号为 (i-2)/2。
3）将该父结点的编号赋值给i，重复步骤2直到i=1。

该算法的时间复杂度为 O(logn)，空间复杂度为 O(1)。因为它只需要通过结点编号计算出该结点在数组中的索引，然后逐个输出该结点的祖先结点值，不需要额外的空间存储中间结果。

### 回答3：
假设编号为i的结点所在的位置为j（从1开始），那么它的父节点位置为 j/2，左子节点位置为2j，右子节点位置为2j+1。

因此我们可以从编号为i的结点开始，通过不断地向上查找父节点，直到根节点为止，输出所有的祖先结点值。

具体实现可以借助一个栈来存储每个向上查找的结点。从i结点开始，将其入栈。然后依次将其父节点入栈，直到根节点为止。最后依次出栈，输出所有的祖先结点值。

具体代码如下：

def get_ancestors(tree, i):
    ancestors = []
    j = i
    while j > 0:
        ancestors.append(tree[j-1])
        j //= 2
    return ancestors[::-1]

其中，tree是存储树的数组，i为要查找祖先结点的节点编号。从i开始向上查找，将每个结点值加入到ancestors列表中，最后将列表反转，输出所有的祖先结点值。

该算法的时间复杂度为O(logn)，其中n为二叉树结点数，因为最多需要向上查找二叉树的深度次数即可找到根节点。而空间复杂度为O(logn)，即最多需要存储二叉树深度个结点。