数据结构考研分类复习真题 第六章 答案 (四)[5]

．根据顺序存储的完全二叉树的性质编号为i的结点的双亲的编号是ëi/û故A[i]和A[j]的最近公共祖先可如下求出

while(i/!=j/)

if(i>j) i=i/; else j=j/;

退出while后若i/=则最近公共祖先为根结点否则最近公共祖先是i/

．N个结点的K叉树最大高度N（只有一个叶结点的任意k叉树）设最小高度为H第i(<=i<=H)层的结点数Ki则N=+k+k+…+ kH由此得H=ëlogK(N(K)+)û

结点个数在到的满二叉树且结点数是素数的数是其叶子数是

．设分枝结点和叶子结点数分别是为nk和n因此有n=n+nk ()

另外从树的分枝数B与结点的关系有 n=B+=K*nk + ()

由（）和（）有 n=nnk=(n(K)+)/K

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []