09年自考《數據結構》各章要點二[1]

　　第六章 樹

　　樹是n個結點的有限集合非空時必須滿足只有一個稱為根的結點其余結點形成m個不相交的子集並稱根的子樹

　　根是開始結點結點的子樹數稱度度為的結點稱葉子(終端結點)度不為的結點稱分支結點(非終端結點)除根外的分支結點稱內部結點

　　有序樹是子樹有左右之分的樹無序樹是子樹沒有左右之分的樹森林是m個互不相交的樹的集合

　　樹的四種不同表示方法

　　·樹形表示法

　　·嵌套集合表示法

　　·凹入表示法

　　·廣義表表示法

　　二叉樹的定義是n≥個結點的有限集它是空集(n=)或由一個根結點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成

　　二叉樹不是樹的特殊情形與度數為的有序樹不同

　　二叉樹的個重要性質

　　·二叉樹上第i層上的結點數目最多為^(i)(i≥)

　　·深度為k的二叉樹至多有(^k)個結點(k≥)

　　·在任意一棵二叉樹中若終端結點的個數為n度為的結點數為n則n=n+

　　·具有n個結點的完全二叉樹的深度為int(logn)+

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

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