[二叉树 binary tree] は、非線形データ構造であり、祖先と子孫の派生関係を表し、"分割" の分割論理を表しています。
二分木の基本単位はノードであり、各ノードには、値、[左の子ノード] の参照、[右の子ノード] の参照があります。
class TreeNode {
int val;
TreeNode? left;
TreeNode? right;
TreeNode(int x) => val = x;
}
二分木では、葉ノード以外のすべてのノードには子ノードと空でないサブツリー（子ノードとその下のノードからなるツリー）が含まれています。
二分木の一般的な用語#
- [ルートノード] root node: 最上位のノードで、親ノードがありません。
- [葉ノード] leaf node: 子ノードを持たないノードです。
- [エッジ] edge: 2 つのノードを接続する線分、つまりノードの参照（ポインタ）です。
- ノードの [レベル] level: 上から下に向かって増加し、ルートノードのレベルは 1 です。
- ノードの [次数] degree: ノードの子ノードの数です。二分木では、次数の範囲は 0、1、2 です。
- 二分木の [高さ] height: ルートノードから最も遠い葉ノードまでのエッジの数です。
- ノードの [深さ] depth: ルートノードからそのノードまでのエッジの数です。
- ノードの [高さ] height: 最も遠い葉ノードからそのノードまでのエッジの数です。
💡 注意：通常、「高さ」と「深さ」は「エッジの数を歩く」と定義されます。
一般的な二分木のタイプ#
1. [完全二分木 perfect binary tree]#
最下層以外のすべてのレベルのノードが完全に埋まっています。
2. [完全二分木 complete binary tree]#
最下層のノードのみが埋まっておらず、最下層のノードは左側に詰められています。
3. [完全二分木 full binary tree]#
葉ノード以外のすべてのノードには 2 つの子ノードがあります。
4. [平衡二分木 balanced binary tree]#
任意のノードの左部分木と右部分木の高さの差の絶対値が 1 を超えないです。
二分木の走査#
[レベル順走査 level-order traversal]#
[レベル順走査 level-order traversal] は、上から下に向かって二分木を階層ごとに走査し、各階層で左から右の順序でノードを訪れます。
** レベル順走査は本質的には [幅優先探索 breadth-first traversal]** であり、階層ごとに外側に「一周一周広げる」階層ごとの走査方法を表しています。
幅優先探索は通常、キューを使用して実装されます。
/* レベル順走査 */
List<int> LevelOrder(TreeNode root) {
// キューを初期化し、ルートノードを追加
Queue<TreeNode> queue = new();
queue.Enqueue(root);
// 走査シーケンスを保存するためのリストを初期化
List<int> list = new();
while (queue.Count != 0) {
TreeNode node = queue.Dequeue(); // キューからノードを取り出す
list.Add(node.val); // ノードの値を保存
if (node.left != null)
queue.Enqueue(node.left); // 左の子ノードをキューに追加
if (node.right != null)
queue.Enqueue(node.right); // 右の子ノードをキューに追加
}
return list;
}
前順、中順、後順走査#
** 前順、中順、後順走査はすべて [深さ優先探索 depth-first traversal]** に属しており、"先に進んでからバックトラックする" という走査方法を表しています。
深さ優先探索は、二分木全体の外周を「歩く」ようなもので、各ノードで前順走査、中順走査、後順走査の 3 つの位置に遭遇します。
深さ優先探索は通常、再帰に基づいて実装されます。
/* **前順**走査 */
void PreOrder(TreeNode? root) {
if (root == null) return;
// 訪問優先度：**ルート**ノード -> **左**部分木 -> **右**部分木
list.Add(root.val);
PreOrder(root.left);
PreOrder(root.right);
}
/* **中順**走査 */
void InOrder(TreeNode? root) {
if (root == null) return;
// 訪問優先度：**左**部分木 -> **ルート**ノード -> **右**部分木
InOrder(root.left);
list.Add(root.val);
InOrder(root.right);
}
/* **後順**走査 */
void PostOrder(TreeNode? root) {
if (root == null) return;
// 訪問優先度：**左**部分木 -> **右**部分木 -> **ルート**ノード
PostOrder(root.left);
PostOrder(root.right);
list.Add(root.val);
}
覚え方：
前順：根左右、中順：左根右、後順：左右根。