37.2° Blog

1、一颗二叉树按顺序存储，求编号为i和j的两个结点的最近公共祖先结点的值。

分析：任一结点i的双亲结点的编号为i/2

算法思想：

• 若i>j，则结点i所在的层次大于等于结点j所在层次。结点i的双亲结点为i/2，若i/2=j，则结点j为最近公共祖先结点；若i/2!=j，则令i=i/2，采用递归的方式继续查找。
• 若j>i，则结点j所在的层次大于等于结点i所在层次。结点j的双亲结点为j/2，若j/2=i，则结点i为最近公共最先结点；若j/2 != i，则令j=j/2，采用递归的方式继续查找

// 二叉树中查找i和j的最近公共结点 
ElemType commoAncestor(Tree T, int i, int j) 
{
    if(T[i] != NULL && T[j] != NULL) 
    { 
        while(i != j) 
        { 
              if(i > j) 
                    i = i /2; 
              else 
                       j = j /2 
        } 
        return T[i]; 
     }
}