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

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

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

   該結論不成立對於任一a€A可在B中找到最近祖先fa在f的左子樹上對於從f到根結點路徑上所有b€B有可能f在b的右子樹上因而a也就在b的右子樹上這時a>b因此a<b不成立同理可以證明b<c不成立而對於任何a∈Ac∈C均有a<c

   n個結點的m次樹共有n*m個指針除根結點外其余n個結點均有指針所指故空指針數為n*m(n)=n*(m)+證畢

   證明 設度為 及葉子結點數分別為nn和n則二叉樹結點數n為n=n+n+n   ()

  再看二叉樹的分支數除根結點外其余結點都有一個分支進入設B為分支總數則n=B+度為的結點各有個和個分支度為 的結點沒有分支故n=n+n+   ()

  由()和(得n= n+

   參見題

   設完全二叉樹中葉子結點數為n則根據完全二叉樹的性質度為的結點數是n而完全二叉樹中度為的結點數至多為所以具有n個葉子結點的完全二叉樹結點數是n+(n)+=n或n(有或無度為的結點)由於具有n(或n)個結點的完全二叉樹的深度是ëlog(n)û+( ëlog(n)û+即élognù+故n個葉結點的非滿的完全二叉樹的高度是élognù+(最下層結點數>=

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


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