第五章 樹狀結構

導論

• 樹（Tree）是一種非線性的資料結構，用於描述具有分支的結構，是一個階層性的、無向圖。
• 樹在各種領域都有廣泛的應用，包括計算機科學、數學和生物學。

5-1 樹的基本概念

• 樹由一個或多個節點組成，有一個特殊的節點稱為根節點（root）。
• 其他節點分為 n 個互斥的集合 T1、T2、T3……Tn，每個集合本身也是一棵樹，稱為根節點的子樹。
• 樹的術語包括：
  • 度（Degree）：每個節點的子樹數量。
  • 層級（Level）：樹的層級，根節點為第一層級。
  • 高度（Height）：樹中最大層級。
  • 葉節點（Terminal Nodes）：度為零的節點。
  • 父節點（Parent）：每個節點的上層節點。
  • 子節點（Children）：每個節點的下層節點。
  • 祖先（Ancestor）：從根節點到該節點路徑上的節點。
  • 子孫（Decendent）：從該節點到子樹中任一節點路徑上的節點。
  • 兄弟節點（Siblings）：具有共同父節點的節點。

5-2 二元樹

• 二元樹是一種特殊類型的樹，其每個節點最多只有兩個子樹，稱為左子樹和右子樹。
• 二元樹與其他樹之間的區別包括：
  • 二元樹可以是空的，而普通樹不能。
  • 二元樹的節點度限制為 0、1 或 2。
  • 二元樹中子樹之間存在次序關係。
• 特殊的二元樹結構包括：
  • 滿二元樹：高度為 h 的二元樹，節點數為 2h-1。
  • 完整二元樹：深度為 h 的二元樹，節點數小於 2h-1，但其節點編號符合滿二元樹的編號方式。
  • 歪斜樹：一個二元樹完全沒有左節點或右節點。
  • 嚴格二元樹：每個非葉節點都有非空的左子樹和右子樹。

5-3 二元樹的儲存方式

• 陣列表示法：
  • 使用一維陣列儲存二元樹，假設二元樹為滿二元樹。
  • 節點的索引值與父節點和子節點的索引值之間存在以下關係：
    • 左子樹索引值 = 父節點索引值 * 2
    • 右子樹索引值 = 父節點索引值 * 2 + 1
• 串列表示法：
  • 使用串列來儲存二元樹，便於增加和刪除節點。
  • 每個節點都包含其值、左子樹指標和右子樹指標。

5-4 二元樹的走訪

• 中序走訪（Inorder Traversal）：
  • 遵循 左子樹 -> 根節點 -> 右子樹 的順序走訪二元樹。
• 前序走訪（Preorder Traversal）：
  • 遵循 根節點 -> 左子樹 -> 右子樹 的順序走訪二元樹。
• 後序走訪（Postorder Traversal）：
  • 遵循 左子樹 -> 右子樹 -> 根節點 的順序走訪二元樹。

5-5 二元樹的進階研究

• 二元樹排序：
  • 利用二元樹的性質（每個節點大於左子節點且小於右子節點）進行排序。
• 二元樹搜尋：
  • 使用二元樹進行搜尋，利用根節點和目標值的關係判斷走訪子樹的方向。
• 引用二元樹：
  • 將空的節點指標再次指向樹中的其他節點，以節省空間和提高中序走訪的效率。

樹的結構 PowerPoint 簡報

引言

本篇簡報將探討樹的構造，深入剖析其基本組成部分和功能，瞭解樹木如何生長和適應環境。

樹的定義

樹是一種多年生、木質化植物，具有以下特徵：
– 有單一主幹（樹幹）
– 樹幹上分枝
– 生長在土壤中，根系發達

樹的組成部分

樹的生長

樹木通過頂芽和側芽不斷生長：
– 頂芽位於樹幹或樹枝的最頂端，向上生長
– 側芽位於樹幹或樹枝的側面，向外側生長
– 根系不斷向外延伸，吸收水分和養分

樹的適應性

樹木具有以下適應性，以應對不同的環境：
– 樹冠形狀：根據陽光照射強度和競爭程度而變化
– 樹幹高度：根據風力強度和光合作用需要而變化
– 根系深度：根據土壤水份含量和結構而變化

結論

樹的構造非常複雜且高度適應，讓樹木能夠在各種環境中茁壯成長。瞭解樹的組成部分和功能有助於我們欣賞樹木的獨特之處和對生態系統的重要貢獻。

延伸閲讀…

第六章樹和二叉樹2 | PPT

PPT – 第五章樹狀結構導論（ Tree ） …