问答题
当一棵有n(0<=100)个结点的二叉树按顺序存储方式存储在bf[1..n]中时,试写一个算法,求出二叉树中结点值分别为x和y的两个结点的最近的公共祖先结点的值。【同济大学2003四(10分)】【武汉大学2000五】
【正确答案】正确答案:二叉树顺序存储,是按完全二叉树的格式存储,利用完全二叉树双亲结点与子女结点编号间的关系进行求解。设结点值为x和y的两个结点的下标分别是i和j,求下标为i和j的双亲,双亲的双亲,等等,直至找到最近的公共祖先。 while(i!=j) //直到i=j时,就是原来两个结点的最近的公共祖先 if(i>j)i=i/2 ; //下标为x的结点的双亲结点的下标 else j=j/2; //下标为Y的结点的双亲结点的下标
【答案解析】