事业单位考试计算机基础知识：二叉树的基本特性(2)

事业单位招聘网

1443141551326121.png

    　例题
    已知A[1……N]是一棵顺序存储的完全二叉树，如何求出A和A[j]的最近的共同祖先?
    解：根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号为i/2，故A和A[j]的最近的共同祖先可如下求出：
    while(i/2!j/2)
    if(i>j)i=i/2;
    else j=j/2;
    退出while后，若i/2=0，则最近共同祖先为根结点，否则共同祖先为i/2。