《树与二元树》PPT课件

《《树与二元树》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章樹與二元樹（TreesandBinaryTrees）7-1樹的基本觀念7-2二元樹的基礎7-3二元樹的表示法7-4二元樹的走訪7-5二元搜尋樹7-6引線二元樹7-7樹的二元樹表示法7-8二元樹的應用-運算式處理7-1樹的基本觀念-說明「樹」（Trees）是一種模擬現實生活中樹幹和樹枝的資料結構，屬於一種階層架構的非線性資料結構，例如：家族族譜，如下圖所示：7-1樹的基本觀念-架構1樹的樹根稱為「根節點」（Root），在根節點之下是樹的樹枝，擁有0到n個「子節點」（Children），即樹的「分支」（Branch），節點A是樹的根節點，B、C

2、、D….和H是節點A的子節點，即樹枝，如下圖所示：7-1樹的基本觀念-架構2在樹枝下還可以擁有下一層樹枝，I和J是B的子節點，K、L和M是E的子節點，節點B是I和J的「父節點」（Parent），節點E是K、L和M的父節點，節點I和J擁有共同父節點，稱為「兄弟節點」（Siblings），K、L和M是兄弟節點，B、C…和H節點也是兄弟節點，如下圖所示：7-1樹的基本觀念-定義定義7.1：樹的節點個數是一或多個有限集合，且：(1)存在一個節點稱為根節點。(2)在根節點下的節點分成n>=0個沒有交集的多個子集合t1、t2…,tn，每一個子集合也是一棵樹，

3、而這些樹稱為根節點的「子樹」（Subtree）。樹在各節點之間不可以有迴圈，或不連結的左、右子樹，如下圖所示：7-1樹的基本觀念-相關術語1n元樹：樹的一個節點最多擁有n個子節點。二元樹（BinaryTrees）：樹的節點最多只有兩個子節點。根節點（Root）：沒有父節點的節點是根節點。例如：節點A。葉節點（Leaf）：節點沒有子節點的節點稱為葉節點。例如：節點I、J、C、D、K、L、M、F、G和H。祖先節點（Ancenstors）：指某節點到根節點之間所經過的所有節點，都是此節點的祖先節點。7-1樹的基本觀念-相關術語2非終端節點（Non-te

4、rminalNodes）：除了葉節點之外的其它節點稱為非終端節點。例如：節點A、B和E是非終端節點。分支度（Dregree）：指每個節點擁有的子節點數。例如：節點B的分支度是2，節點E的分支度是3。階層（Level）：如果樹根是1，其子節點是2，依序可以計算出樹的階層數。例如：上述圖例的節點A階層是1，B、C到H是階層2，I、J到M是階層3。樹高（Height）：樹高又稱為樹深（Depth），指樹的最大階層數。例如：上述圖例的樹高是3。7-2二元樹的基礎-定義樹依不同分支度可以區分成很多種，在資料結構中最廣泛使用的樹狀結構是「二元樹」（Binar

5、yTrees），二元樹是指樹中的每一個「節點」（Nodes）最多只能擁有2個子節點，即分支度小於或等於2。二元樹的定義如下所示：定義7.2：二元樹的節點個數是一個有限集合，或是沒有節點的空集合。二元樹的節點可以分成兩個沒有交集的子樹，稱為「左子樹」（LeftSubtree）和「右子樹」（RightSubtree）。7-2二元樹的基礎-圖例左子樹右子樹二元樹7-2二元樹的基礎-歪斜樹左邊這棵樹沒有右子樹，右邊這棵樹沒有左子樹，雖然擁有相同節點，但是這是兩棵不同的二元樹，因為所有節點都是向左子樹或右子樹歪斜，稱為「歪斜樹」（SkewedTree），如

6、下圖所示：7-2二元樹的基礎-完滿二元樹(說明)若二元樹的樹高是h且二元樹的節點數是2h-1，滿足此條件的樹稱為「完滿二元樹」（FullBinaryTree），如下圖所示：7-2二元樹的基礎-完滿二元樹(節點數)因為二元樹的每一個節點有2個子節點，二元樹樹高是3，也就是有3個階層（Level），各階層(以L表示階層)的節點數為2(L-1)，如下所示：第1階：2(L-1)=2(1-1)=20=1第2階：第1階節點數的2倍，1*2=2(2-1)=2第3階：第2階節點數的2倍，2*2=2(3-1)=4以此類推，可以得到每一階層的最大節點數是：2(L-1

7、)，L是階層數，整棵二元樹的節點數一共是：20+21+22=7個，即23-1，可以得到：20+21+22+….+2(h-1)=2h-1，h是樹高7-2二元樹的基礎-完整二元樹若二元樹的節點不是葉節點，一定擁有2個子節點，不過節點總數不足2h-1，其中h是樹高，而且其節點編號是對應相同高度完滿二元樹的１至2h-1的節點編號，滿足此條件稱為完整二元樹（CompleteBinaryTree），如下圖所示：7-3二元樹的表示法7-3-1二元樹陣列表示法7-3-2二元樹結構陣列表示法7-3-3二元樹鏈結表示法7-3二元樹的表示法二元樹在實作上有多種方法可以

8、建立二元樹，常用的方法有三種，如下所示：二元樹陣列表示法。二元樹結構陣列表示法。二元樹鏈結表示法。7-3-1二元樹陣列表示法-說明1完滿