二叉樹是我們在數據結構中學到的第一個非線性結構，是后續學習更為復雜的樹、圖結構的基礎。本文整理了二叉樹的概念定義、基本操作、遍歷算法、偽代碼與代碼實現以及實例說明，方便大家隨時查找對應。

一、定義與基本術語

二叉樹是一種樹形結構，每個節點最多有兩個子節點，分別稱為左節點和右節點。

基本術語：

• 根節點：樹的頂部節點。
• 葉節點：沒有子節點的節點。
• 父節點：某個節點的直接上級節點。
• 子節點：某個節點的直接下級節點。
• 兄弟節點：具有相同父節點的節點。
• 深度：從根節點到某個節點的邊的數量。
• 高度：從某個節點到最遠葉節點的邊的數量。

? ? ? ? A (Depth: 0, Root)
? ? ? ?/? ??
? ? ?B (Depth: 1)
? ? / ? \
?C1? ?C2(Depth: 2)
? ?\
? ? D (Depth: 3, Right)
? ? ?\
? ? ? E (Depth: 4, Right)
? ? ?/? \
? ? F1? ?F2(Depth: 4)?

二、主要特點

1. 遞歸性質：二叉樹的許多操作可以通過遞歸實現。
2. 動態集合：二叉樹可以用來實現動態集合，支持插入、刪除和查找操作。
3. 層次結構：二叉樹具有明確的層次結構，適合表示具有層次關系的數據。

三、基本操作

1. 構建二叉樹：

① 構建節點：

struct TreeNode{int key;TreeNode* left;TreeNode* right;TreeNode(int k): key(k),left(nullptr),right(nullptr){}
};

② 插入節點：

插入操作會根據節點的值來決定插入的位置。例如，在二叉搜索樹（BST）中，插入操作遵循以下規則：

• 如果當前節點的值大于插入值，則遞歸地插入到左子樹。
• 如果當前節點的值小于插入值，則遞歸地插入到右子樹。
• 如果當前節點的值等于插入值，則可以選擇不插入或插入到左/右子樹。

TreeNode* insert(TreeNode* node, int key){if(node == nullptr){return new TreeNode(key);}if(key < node->key){node->left = insert(node->left, key);}else if(key > node->key){node->right = insert(node->right,key);}return node;
}

③ 構建樹：

從一個空樹開始，通過多次插入節點，可以逐步構建二叉樹。

TreeNode* root = nullptr;
// 如果是基于一個給定數組構建二叉樹
for(int i = 0;i<length;i++){root = insert(root,nums[i]);
}
//手動輸入構建
root = insert(root,10);
root = insert(root,4);
root = insert(root, 7);
root = insert(root, 20);
root = insert(root, 34);
root = insert(root, 16);
root = insert(root, 8);

?2. 刪除節點：

TreeNode* deleteNode(TreeNode* node, int key){if(node == nullptr) return node;if(key < node->key){node->left = deleteNode(node->left, key);} else if (key > node->key) {node->right = deleteNode(node->right, key);}else{if(node->left == nullptr){TreeNode* tmp = node->right;delete node;return tmp;}else if(node->right == nullptr){TreeNode* tmp = node->left;delete node;return tmp;}TreeNode* temp = findMin(node->right);node->key = temp->key;node->right = deleteNode(node->right, temp->key);}return node;
}TreeNode* findMin(TreeNode* node){while(node->left != nullptr){node = node->left;}return node;
}

3. 查找節點：

TreeNode* searchNode(TreeNode* node, int key){if(node == nullptr||node->key = key) return node;if(key < node->key){return searchNode(node->left,key);}if(key > node->key){return searchNode(node->right, key);}
}

四、遍歷算法

需要了解：前序遍歷、中序遍歷、后序遍歷、層序遍歷

1. 前序遍歷：

? ? ? ? A
? ? ? ?/ \
? ? ? B ? C
? ? ?/ \ ? \
? ? D ? E ? F

遍歷順序：A->B->D->E->C->F

? ? ? ? 1
? ? ? ?/ \
? ? ? 2 ? 3
? ? ?/ \ ? \
? ? 4 ? 5 ? 6
? ?/ \
? 7 ? 8

遍歷順序：1->2->4->7->8->5->3->6

前序遍歷的訪問順序：根節點-->左子樹-->右子樹

// 以int整數型為例
vector<int> result
void preorder(TreeNode* node){if(node == nullptr){return;}// 如果題目要求的是前序遍歷打印節點值，那么可以直接：// cout<<node->key<<" ";// 如果題目要求前序遍歷將節點值存儲到數組中，需要先定義一個vector數組（如↑），再進行存儲result.push_back(node_key);preorder(node->left);preorder(nofe->right);
}

?2. 中序遍歷

? ? ? ? A
? ? ? ?/ \
? ? ? B ? C
? ? ?/ \ ? \
? ? D ? E ? F

遍歷順序：D->B->E->A->C->F

? ? ? ? 1
? ? ? ?/ \
? ? ? 2 ? 3
? ? ?/ \ ? \
? ? 4 ? 5 ? 6
? ?/ \
? 7 ? 8

遍歷順序：7->4->8->2->5->1->3->6?

? ? ? ? 10
? ? ? ?/? ? \
? ? ? 6 ? ?14
? ? ?/? \? ? /? ? \
? ? 4 ? 8 12 ?16

遍歷順序：4->6->8->10->12->14->16

中序遍歷的訪問順序：左子樹-->根節點-->右子樹

vector<int> result;
void inorder(TreeNode* node) {if (node == nullptr) return;inorder(node->left);visit(node);inorder(node->right);
}void visit(TreeNode* node){// cout<< node->key <<" ";result.push_back(node->key);
}

3. 后序遍歷

? ? ? ? A
? ? ? ?/ \
? ? ? B ? C
? ? ?/ \? ? ?\
? ? D ? E ? F

遍歷順序：D->E->B->F->C->A

? ? ? ? 1
? ? ? ?/ \
? ? ? 2 ? 3
? ? ?/? \? ? \
? ? 4 ? 5 ? 6
? ?/ \
? 7 ? 8

遍歷順序：7->8->4->5->2->6->3->1?

后序遍歷的訪問順序：左子樹->右子樹->根節點。

void postorder(TreeNode* node){if(node==nullptr) return;postorder(node->left);postorder(node->right);visit(node);
}
//visit函數要根據題目要求來定義，示例可參考中序遍歷的定義

4. 層序遍歷

? ? ? ? A
? ? ? ?/ \
? ? ? B ? C
? ? ?/ \? ? ?\
? ? D ? E ? F

遍歷順序：A->B->C->D->E->F

? ? ? ? 1
? ? ? ?/ \
? ? ? 2 ? 3
? ? ?/? ? /? \
? ? 4 ? 5 ? 6
? ? ? ? /
? ? ? 7?

遍歷順序：1->2->3->4->5->6->7

層序遍歷的順序是：從上到下，從左到右。

層序遍歷的結果特別好寫，從上往下盯齊就沒問題，但是代碼是最長的。。

先來看看偽代碼：

LevelOrder(root)
? ? queue = new Queue()
? ? queue.enqueue(root)
? ? while not queue.isEmpty()
? ? ? ? node = queue.dequeue()
? ? ? ? visit(node)
? ? ? ? if node.left != null
? ? ? ? ? ? queue.enqueue(node.left)
? ? ? ? if node.right != null
? ? ? ? ? ? queue.enqueue(node.right)

void levelorder(TreeNode* root){if(root == nullptr) return;queue<TreeNode* > q; // 創建一個隊列，用于存儲待訪問的節點q.push(root); // 把現在的根節點存進去while(!q.empty()){TreeNode* node = q.front(); // 取出隊列的第一個節點q.pop(); // 將該節點從隊列中移除visit(node);if (node->left != nullptr) q.push(node->left);if (node->right != nullptr) q.push(node->right); // 這里加入隊列的順序是先左再右，隊列又是FIFO結構，遍歷得到的順序也就滿足了先左再右}
}

五、適用場景舉例

1. 表達式樹：用于表示和計算算術表達式。
2. 二叉搜索樹（BST）：用于實現動態集合，支持高效的插入、刪除和查找操作。
3. 哈夫曼樹：用于數據壓縮。
4. 堆：用于實現優先隊列。
5. 線索二叉樹：用于高效地遍歷二叉樹。

六、Leetcode 二叉樹 練習題匯總

1.?初級題目

題號	題目名稱	知識點
94	二叉樹的中序遍歷	中序遍歷，遞歸與迭代
144	二叉樹的前序遍歷	前序遍歷，遞歸與迭代
145	二叉樹的后序遍歷	后序遍歷，遞歸與迭代
102	二叉樹的層序遍歷	層序遍歷，隊列的應用
226	翻轉二叉樹	遞歸，樹的翻轉
617	合并二叉樹	遞歸，樹的合并
589	N叉樹的前序遍歷	N叉樹，前序遍歷
897	遞增順序搜索樹	二叉搜索樹，中序遍歷的應用

2. 中級題目?

題號	題目名稱	知識點
98	驗證二叉搜索樹	二叉搜索樹的性質，遞歸
113	路徑總和 II	深度優先搜索，路徑求和
257	二叉樹的所有路徑	深度優先搜索，路徑記錄
114	二叉樹展開為鏈表	遞歸，樹的展開
116	填充每個節點的下一個右側節點指針	層序遍歷，隊列的應用
104	二叉樹的最大深度	深度優先搜索或層序遍歷
543	二叉樹的直徑	深度優先搜索，樹的直徑
236	二叉樹的最近公共祖先	遞歸，最近公共祖先

?希望對你有幫助！