數據結構考研分類復習真題 第六章 答案 (四)[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

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/22664.html