熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第六章 答案 (四)[4]

2013-11-15 14:59:16  來源: 數據結構 

  .最低高度二叉樹的特點是除最下層結點個數不滿外其余各層的結點數都應達到各層的最大值設n個結點的二叉樹的最低高度是h則n應滿足h<n<=h關系式解此不等式並考慮h是整數則有h=ëlognû+即任一結點個數為n 的二叉樹的高度至少為O(logn)

  n(本題等價於高度為n的滿二叉樹有多少葉子結點從根結點到各葉子結點的單枝樹是不同的二叉樹)

  由於本題求二叉樹的結點數最多是多少層共有=個結點已知有個葉子其余個結點均為分支結點它在第八層上有個葉子結點所以該二叉樹的結點數最多可達(+)=(注意本題並未明說完全二叉樹的高度但根據題意只能)

  (=

  .證明設度為 的結點數是n和n則二叉樹結點數n為n=m+n+n…………()

  由於二叉樹根結點沒有分枝所指度為的結點各有個和個分枝度為 的結點沒有分枝故二叉樹的結點數n與分枝數B有如下關系n=B+=n+*n+…………()

  由()和(得n=m即n個結點的二叉樹若葉子結點數是m則非葉子結點中有(m)個度為其余度為

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


From:http://tw.wingwit.com/Article/program/sjjg/201311/22663.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.