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

第6章樹(基礎知識)習題練習答案

2013-11-15 15:41:36  來源: 數據結構 
假設在樹中結點x是結點y的雙親時用(xy)來表示樹邊已知一棵樹邊的集合為{(im)(in)(ei)(be)(bd)(ab)(gj)(gk)(cg)(cf)(hl)(ch)(ac)}用樹形表示法出此樹並回答下列問題
 ()哪個是根結點? ()哪些是葉結點? ()哪個是g的雙親? ()哪些是g的祖先? 
 ()哪些是g的孩子? ()哪些是e的子孫? ()哪些是e的兄弟?哪些是f的兄弟? 
 ()結點b和n的層次各是多少? ()樹的深度是多少? ()以結點c為根的子樹的深度是多少? () 樹的度數是多少?

 a是根結點
 dmnfjkl是葉結點
 c是g的雙親
 ca是g的祖先
 jk是g的孩子
 imn是e的子孫
 d是e的兄弟gh是f的兄弟
 b的層次是n的層次是
 樹的深度是
 以c為根的子樹深度是
 樹的度數是

一棵度為的有序樹與一棵二叉樹有何區別?


  
一棵度為二的有序樹與一棵二叉樹的區別在於:有序樹的結點次序是相對於另一結點而言的如果有序樹中的子樹只有一個孩子時這個孩子結點就無須區分其左右次序而二叉樹無論其孩子數是否為均需確定其左右次序也就是說二叉樹的結點次序不是相對於另一結點而言而是確定的

試分別畫出具有個結點的樹和個結點的二叉樹的所有不同形態


  
三個結點的樹如下只有兩種形態

      ○      ○ 
    / \      | 
    ○ ○     ○ 
              |  
                           ○ 

三個結點的二叉樹如下所示有五種形態

     ()        ()      ()       ()        ()

     ○         ○        ○        ○         ○ 
    /  \        /        /           \          \ 
   ○  ○      ○       ○           ○          ○ 
              /          \          /             \ 
             ○          ○        ○              ○   

已知一棵度為m的樹中有n個度為的結點n個度為的結點nm個度為m的結點問該樹中有多少片葉子?

    設該樹中的葉子數為n該樹中的總結點數為n個則有
         n=n+n+n+…+nm ()
又有除根結點外樹中其他結點都有雙親結點且是唯一的(由樹中的分支表示)所以有雙親的結點數為
         n=*n+*n+*n+…+m*nm ()
  聯立()()方程組可得
  葉子數為n=+*n+*n+*n++(m)*nm

一個深度為h的滿k叉樹有如下性質第h層上的結點都是葉子結點其余各層上每個結點都有k棵非空子樹如果按層次順序(同層自左至右)從開始對全部結點編號

  ()各層的結點數目是多少?
 ()編號為i的結點的雙親結點(若存在)的編號是多少?
 ()編號為i的結點的第j個孩子結點(若存在)的編號是多少?
 ()編號為i的結點的有右兄弟的條件是什麼? 其右兄弟的編號是多少?


 () 層號為h的結點數目為kh
 () 編號為i的結點的雙親結點的編號是|_ (i)/k _|+(不大於(i)/k的最大整數也就是(i)與k整除的結果以下/表示整除
 () 編號為i的結點的第j個孩子結點編號是k*(i)++j;
 () 編號為i的結點有右兄弟的條件是(i)能被k整除 
   右兄弟的編號是i+

高度為h的完全二叉樹至少有多少個結點?至多有多少個結點?


  
高度為h的完全二叉樹至少有h個結點至多有h個結點(也就是滿二叉樹)

在具有n個結點的k叉樹(k>=)的k叉鏈表表示中有多少個空指針?


  n個結點的K叉樹共有n*k個指針域已使用的指針域為n所以空指針的個數為n(k)+

假設二叉樹包含的結點數據為

 ()畫出兩棵高度最大的二叉樹
 ()畫出兩棵完全二叉樹要求每個雙親結點的值大於其孩子結點的值


 ()高度最大的兩棵二叉樹如圖

     ○     ○
     /       \
    ○       ○
    /         \
   ○         ○
   /           \
  ○           ○
  /             \
 ○             ○
 

 ()兩棵完全二叉樹如下


     ○       ○ 
     / \       / \ 
    ○     ○ 
    / \       / \ 
   ○     ○ 

試找出分別滿足下面條件的所有二叉樹

 ()前序序列和中序序列相同 ()中序序列和後序序列相同
 ()前序序列和後序序列相同 ()前序中序後序序列均相同


 () 前序序列和中序序列相同的二叉樹是空二叉樹或沒有左子樹的二叉樹(右單支樹)
 () 中序序列和後序序列相同的二叉樹是空二叉樹或沒有右子樹的二叉樹(左單支樹)
 () 前序序列和後序序列相同的二叉樹是空二叉樹或只有根的二叉樹
 () 前序中序後序序列均相同的二叉樹空樹或只有根結點的二叉樹

試采用順序存儲方法和鏈接存儲方法分別畫也所示各二叉樹的存儲結構





  ()順序存儲方法

     二叉樹(a):
下標                  
    __________________________________________________________________
 bt |  | | |∮|∮| |∮|∮|∮|∮| |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮| |
    __________________________________________________________________

     二叉樹(b):
下標                    
    __________________________________________________________________________________
  bt|  | |∮| |∮|∮| |∮|∮|∮|∮|∮|∮| |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮| |
    __________________________________________________________________________________

     二叉樹(c):
下標                    
    ______________________________________________________________________
From:http://tw.wingwit.com/Article/program/sjjg/201311/23803.html

    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.