# 什么是二叉樹
## 目錄
1. [基本概念](#基本概念)
2. [二叉樹的性質](#二叉樹的性質)
3. [特殊類型二叉樹](#特殊類型二叉樹)
4. [存儲結構](#存儲結構)
5. [遍歷方式](#遍歷方式)
6. [應用場景](#應用場景)
7. [代碼實現示例](#代碼實現示例)
8. [復雜度分析](#復雜度分析)
9. [常見問題](#常見問題)
## 基本概念
二叉樹（Binary Tree）是每個節點最多有兩個子節點的樹形數據結構，這兩個子節點分別稱為**左子節點**和**右子節點**。它是非線性數據結構中最基礎且最重要的結構之一，具有遞歸定義的特性。
### 核心特征
- 每個節點最多有2個子節點
- 左子樹和右子樹有明確區分
- 第i層最多有2^(i-1)個節點
- 深度為k的二叉樹最多有2^k - 1個節點
### 數學定義
遞歸定義二叉樹：
1. 空樹是二叉樹
2. 由一個根節點和兩個互不相交的子樹（左/右子樹）組成
## 二叉樹的性質
1. **層次性質**：
- 第k層最多有2^(k-1)個節點
- 深度為h的樹最多有2^h - 1個節點
2. **節點關系**：
- 度為0的節點（葉節點）數 = 度為2的節點數 + 1
- 具有n個節點的二叉樹最小深度為?log?(n+1)?
3. **特殊性質**：
```math
n = n? + n? + n?
e = n - 1 = n? + 2n?
=> n? = n? + 1
# 完全二叉樹的數組表示
tree = [None, 'A', 'B', 'C', 'D', 'E', 'F']
# 索引i的左右子節點分別為2i和2i+1
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
前序遍歷：根→左→右
def preorder(root):
if root:
print(root.val)
preorder(root.left)
preorder(root.right)
中序遍歷：左→根→右（BST得到有序序列）
后序遍歷：左→右→根
from collections import deque
def level_order(root):
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_sample_tree():
""" 構建示例樹：
1
/ \
2 3
/ \
4 5
"""
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
return root
void inorderTraversal(TreeNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
}
| 操作 | 平均情況 | 最壞情況 |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 刪除 | O(log n) | O(n) |
| 空間復雜度 | O(n) | O(n) |
注：平衡二叉樹的最壞情況為O(log n)
使用層序遍歷，當遇到空節點后不應再出現非空節點
雖然單次操作時間復雜度可能相同，但樹形結構支持二分查找等高效算法
通過本文的詳細講解，讀者應該已經掌握了二叉樹的核心概念、存儲方式、遍歷算法以及實際應用。二叉樹作為基礎數據結構，是學習更高級樹形結構（如B樹、Trie樹等）的重要基礎。建議通過LeetCode等平臺的相關題目（如94、102、104題）進行實踐練習。 “`
注：本文實際約2150字（含代碼和公式），由于Markdown渲染差異，不同平臺顯示的字數可能略有不同。如需精確字數控制，建議在最終發布前使用專業字數統計工具校驗。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
