题目1：

已知一棵二叉树按顺序方式存储在数组a[1...n]中，设计一个算法，求编号分别是i和j的两个结点的最近公共祖先结点的值。

分析：如果要找i和j的一起的祖先结点，可以一直往下找分支结点，直到i和j相等

代码：

int ancester(int a[], int i, int j) {
    int p = i, q = j;
    while (p != q) {
        if (p > q) {
            p = p / 2;//向上找i的祖先
        }
        else {
            q = q / 2;//向下找j的祖先
        }
        return a[p];
    }
}

题目2：

已知一棵含有n个结点的二叉树，按顺序方式存储，设计用先序遍历二叉树中结点的递归和非递归算法

递归的方法：

#define MaxSize 50
void PreOrder1(char a[], int i) {
    if (i < MaxSize) {
        printf("%c", a[i]);//访问根结点
        PreOrder1(a, 2 * i);//遍历左子树
        PreOrder1(a, 2 * i + 1);//遍历右子树
    }
}

非递归的方法：

void PreOrder2(char a[]) {
    int St[MaxSize], top = -1, i = 1;
    top++;
    St[top] = i;
    while (top > -1) {
        i = St[top];
        top--;
        printf("%c", a[i]);
        if (2 * i + 1 < MaxSize) {//右孩子进栈
            top++;
            St[top] = 2 * i + 1;
        }
        if (2 * i < MaxSize) {//左孩子进栈
            top++;
            St[top] = 2 * i;
        }
    }
}