樹與二叉樹

概述

樹是一種層次結構的數據模型，節點之間存在父子關係；二叉樹是每個節點最多有兩個子節點的樹。

基本術語

• 結點：樹中的基本元素。
• 度：結點擁有的子樹數量。
• 葉子結點：度為 0 的結點。
• 深度/高度：從根到某結點的層數（或從結點到葉子的層數）。

二叉樹的性質

• 第 $i$ 層最多有 $2^{i-1}$ 個結點。
• 高度為 $h$ 的二叉樹，結點總數最多為 $2^h-1$。
• 對於完全二叉樹，可用數組順序存儲並快速定位父子結點。

遍歷方式

• 前序遍歷：根 → 左 → 右。
• 中序遍歷：左 → 根 → 右。
• 後序遍歷：左 → 右 → 根。
• 層序遍歷：按層從上到下，從左到右。

典型應用

• 表達式樹與語法分析。
• 堆與優先隊列。
• 二叉搜索樹與平衡樹。