3 樹與二叉樹

計算機中的樹與現實中的形態相反，是一棵倒掛的樹～

課程內容#

樹#

樹的組成：結點 + 邊
- 結點 👉 集合，邊 👉 關係
- 根結點：全集；子結點：子集
  - 根結點的所有子結點的集合並集 = 全集
  - 【思想】大問題抽象為樹，小問題抽象為子結點

結構定義#

【結點 + 邊】

一叉樹是鏈表結構，只有一個分支的樹形結構
對於三叉樹，則將鏈表的 next 指針變成 next [3] 數組即可

屬性、性質#

深度、高度
- 樹的深度和高度是一個值：最大層數
- 結點的深度和高度不一樣
  - 深度：從根結點往下數，該結點是第幾層
  - 高度：從最深的層數往上數，該結點是第幾層
度：有幾個子孩子
⭐【重要公式】結點數 = 邊數 + 1

二叉樹#

二進制可以轉換成任何進制，二叉樹同理
- 首先簡單
- 且可以表示所有的樹形結構
  - 方法：左孩子、右兄弟法，又稱十字鏈表法
  - 從上往下，從左往右，結點的孩子放在左邊，結點的相鄰兄弟放在右邊
對於 n 叉樹，n 不確定，而二叉樹是確定的
- n 叉樹可以用二叉樹來實現
- 所以，利用二叉樹可以將非確定性問題 → 計算機能解決的確定性問題
⭐【重要公式】二叉樹中，度為 0 的結點比度為 2 的結點多 1 個
- 利用另一重要公式：結點數 = 邊數 + 1
- 令 ni 表示度為 i 的結點個數
- 則：[結點數] n0 + n1 + n2 = n1 + 2 * n2 + 1 [邊數 + 1]
- 得：n0 = n2 + 1
遍歷方式：取決於什麼時候 [最先、中間、最後] 訪問根結點
- 前序遍歷：根左右
- 中序遍歷：左根右
- 後序遍歷：左右根
- 遍歷時的左、右可以分別代表左、右子樹
- 左右的相對順序一直是左在前，右在後
二叉樹分類【國際版】，參考Binary tree: Types of binary trees- 維基百科
- 完全二叉樹：除了最後一層最右邊可以缺少若干連續結點，其他地方都滿滿當當
- 滿二叉樹：度為 0 或 2 即可
- 完美二叉樹：度均為 2，所有葉結點在同一層
- PS：中國版只分完全二叉樹和滿二叉樹，滿二叉樹的定義同國際版的完美二叉樹
完全二叉樹的特點 [完美二叉樹同樣滿足]
- 編號為 i 的結點的左右孩子編號分別是 2 * i、2 * i + 1
- 可以用連續空間（數組）存儲，用於算法優化：記錄式👉計算式
  - 不再需要用結構體存儲孩子結點的地址，直接通過公式可計算其在數組中的索引
廣義表：樹的字符串化
- 有很多種表示方法，一般怎麼簡單怎麼來，見上圖紅框：方式一、方式二
對於二叉搜索樹，中序遍歷是順序的
根據兩種遍歷可得第三種遍歷結果
- 前序遍歷 / 後序遍歷可得根結點，中序遍歷可得左右孩子的位置
- 【必須】要有中序遍歷，只有它才能確定孩子的左右

代碼演示#

二叉搜索樹#

結構定義、結構操作、遍歷結果顯示

樹和結點的操作是分開實現的，獨立封裝
插入操作
- 使用 flag 獲取插入狀態
- 二叉搜索樹沒有重複值
遍歷操作
- 三種遍歷的內部實現，就調換一下訪問左右根的順序即可
- 二叉搜索樹的中序遍歷是有序的，從小到大排序
輸出：廣義表形式為前述第二種方式
❓結構體裡的結點都定義為指針形式，自己的理解是
- 結點是一個結構體，用指針存儲地址更省空間
- 結構體指針調用成員更方便：->
- 方便 free 結點

廣義表還原二叉樹#

具有完全包含關係的問題，使用棧
棧裡存儲結點地址 [Node *]：把廣義表中的字符看成結點
轉換過程
|(|,|)|其他字符【字母】|
|:----:|:----:|:----:|:----:|
|【將元素入棧】
下個 ',' 前的元素為左孩子 | 決定下個字符封裝的元素為【右孩子】| 記錄棧頂，【將元素彈棧】|①將字符【封裝】成結點指針類型，作為棧的元素
②【關係確定】如果棧不為空，則根據該字符相對於 ',' 的位置，成為棧頂元素的左孩子或右孩子 |