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

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

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

  用順序存儲結構存儲n個結點的完全二叉樹編號為i的結點其雙親編號是ëi/û(i=時無雙親)其左子女是i(若i<=n否則i無左子女)右子女是i+(若i+<=n否則無右子女)

   根據完全二叉樹的性質最後一個結點(編號為n)的雙親結點的編號是ën/û這是最後一個分枝結點在它之後是第一個終端(葉子)結點故序號最小的葉子結點的下標是ën/û+

   按前序遍歷對頂點編號即根結點從1開始對前序遍歷序列的結點從小到大編號

   設樹的結點數為n分枝數為B則下面二式成立

  n=n+n+n+…+nm                 ()
  n=B+= n+n+…+mnm             ()

  由()和()得葉子結點數n=+

   élognù +

  

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


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