數和二叉樹---一站式入門，資料結構其實很簡單（2）

樹和二叉樹的抽象資料類型定義

二叉樹的性質

性質1:

在二叉樹的第i層上至多有2^(i-1)個結點(i≥1)。

第i層上至少有1個結點。

性質2:深度為k的二叉樹至多有)2^k)- 1個結點(k≥1)。

深度為k時至少有k個結點。

性質3:對任何一棵二叉樹T,如果其葉子數為n0, 度為2的結點數為n2,則n0= n2+ 1。

解釋：總邊數B，總結點n；度為一的結點數為n1

自下往上數，一節點對應一邊，頭結點無邊B=n-1;

自上往下數，度為2有2邊，度為1為1邊B=2n2+1n1

又n=n0+n1+n2.是以n0=n2+1

兩種特殊形态的二叉樹

滿二叉樹

一棵深度為k且有（2^k）- 1個結點的二叉樹稱為滿二叉樹。

特點:1.每一層上的結點數都是最大結點數(即每層都滿)

2.葉子節點全部在最底層

對滿叉樹結點位置進行編号編号規則:從根結點開始，自上而下，自左而右。

每一結點位置都有元素。

滿二叉樹在同樣深度的二叉樹中結點個數最多

滿二叉樹在同樣深度的二叉樹中葉子結點個數最多

完全二叉樹

滿二叉樹也是完全二叉樹

注:在滿二叉樹中，從最後一個結點開始，連續去掉任意個結點，即是一棵完全二叉樹.

特點: 1葉子隻可能分布在層次最大的兩層上。

2.對任一結點， 如果其右子樹的最大層次為i,則其左子樹的最大層次必為i或i+1。

性質4:具有n個結點的完全二叉樹的深度為Llog2n」+ 1。

注: L x」:稱作x的底，表示不大于x的最大整數

二叉樹的存儲結構

二叉樹的順序存儲

實作:按滿二叉樹的結點層次編号，依次存放二叉樹中的資料元素。

特點：

結點間關系蘊含在其存儲位置中

浪費空間，适于存滿二叉樹和完全二叉樹

二叉樹的鍊式存儲

在n個結點的二叉連結清單中，有n-1個空指針域。

分析:必有2n個鍊域。除根結點外,每個結點有且僅有一一個雙親，是以隻會有n - 1個結點的鍊域存放指針，指向非空子女結點。

空指針數目=2n- (n-1)=n+1

三叉連結清單