二分木
最終更新
二分木は、各ノードが最大2つの子（左の子と右の子）を持つ階層構造です。最上位のノードが根、子を持たないノードが葉で、根から最も深い葉までの辺の数が木の高さです。二分探索木とは異なり、単純な二分木には順序の規則がなく、形状だけを表します。上の再生ボタンを押すと、木がレベルごとに埋まっていき、その後中間順（左・ノード・右）にたどられる様子を見られます。
二分木は多くの構造の基礎になっています。二分探索木、ヒープ、式木などです。走査は各ノードを定められた順序で訪れます。中間順・前順・後順の3つが深さ優先の走査で、それぞれ異なる用途に役立ちます。
用語
| 用語 | 意味 |
|---|---|
| 根 | 親を持たない最上位のノード |
| 葉 | 子を持たないノード |
| 高さ | 根から葉までの最長経路（辺の数） |
| 深さ | あるノードの根からの距離 |
| 完全 | 最後のレベルを除くすべてのレベルが埋まり、最後は左から右へ埋められる |
3つの深さ優先走査
| 走査 | 順序 | よくある用途 |
|---|---|---|
| 中間順 | 左・ノード・右 | BSTのソート済み出力 |
| 前順 | ノード・左・右 | 木のコピー / シリアライズ |
| 後順 | 左・右・ノード | 木の削除 / 評価 |
具体例
[4, 2, 6, 1, 3, 5] から構築した（レベルごとに埋めた）木の中間順走査:
| ステップ | 対象ノード | 動作 |
|---|---|---|
| 1 | 4 | 4 を訪れる前に、その左部分木へ再帰する |
| 2 | 2 | 2 を訪れる前に、その左部分木へ再帰する |
| 3 | 1 | 葉で左の子なし: 1 を訪れ、出力 [1] |
| 4 | 2 | 左が完了: 2 を訪れ、出力 [1, 2]、次に右へ再帰 |
| 5 | 3 | 葉: 3 を訪れ、出力 [1, 2, 3] |
| 6 | 4 | 左部分木が完了: 4 を訪れ、出力 [1, 2, 3, 4]、次に右へ再帰 |
| 7 | 5 | 6 の左の子で葉: 5 を訪れ、出力 [1, 2, 3, 4, 5] |
| 8 | 6 | 左が完了で右の子なし: 6 を訪れ、出力 [1, 2, 3, 4, 5, 6] |
二分木を使うべきとき
| 使うべきとき | 避けるべきとき |
|---|---|
| 本質的に階層的なデータ（ファイルシステム、式木、DOM）をモデル化する必要があるとき | データが平坦でリストや配列で足りるとき。木はオーバーヘッドを増やすだけ |
| 順序付き操作が必要で、平衡を保てるとき（BSTや自己平衡木） | キーによる平均 O(1) の探索が必要なとき。ハッシュテーブルがどの木よりも優れる |
| 構造化データを中間順・前順・後順で処理する必要があるとき | 非平衡なBSTにソート済み順でノードを挿入するとき。O(n) のリストに退化する |
| 範囲クエリや順序付き反復が重要なとき。ハッシュテーブルでは実現できない | メモリが逼迫しているとき。各ノードはデータに加えて2つの子ポインタを持つ |
Binary Treeのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なBinary Treeの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのBinary Treeのコード
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))JavaScriptでのBinary Treeのコード
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));JavaでのBinary Treeのコード
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}C++でのBinary Treeのコード
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}CでのBinary Treeのコード
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}二分木のよくある質問
二分木と二分探索木の違いは何ですか？
二分木は各ノードを最大2つの子に制限するだけで、順序はありません。二分探索木は、左部分木のすべてが小さく、右部分木のすべてが大きいという規則を加えます。これが探索を高速にします。
中間順走査とは何ですか？
中間順走査は、再帰的に左部分木、次にノード、次に右部分木を訪れます。二分探索木ではこれにより値が昇順で得られるため、最もよく示される走査です。
完全二分木とは何ですか？
完全二分木は、最後のレベルを除くすべてのレベルが完全に埋まり、最後は左から右へ埋められます。この形状により、木を配列にコンパクトに（子ポインタなしで）格納でき、二分ヒープはこの方法で実装されます。
配列やハッシュテーブルではなく二分木を使うべきなのはいつですか？
データが自然に階層的であるとき、または範囲クエリやソート済み反復のような順序付き操作が必要なとき（ハッシュテーブルには提供できない）に木を選びます。順序不要でキーの高速探索だけが必要なら、ハッシュテーブルの平均
O(1) アクセスが木を上回り、平坦なデータには配列の方が単純でキャッシュにも優しいです。二分木の高さと深さの違いは何ですか？
深さは根から特定のノードまで下向きに測る値で、根からそのノードへの経路上の辺の数です。高さはあるノードから最も深い葉まで下向きに測るので、木全体の高さは最も深いノードの深さになります。単一ノードの木は高さ
0 で、その唯一のノードの深さも 0 です。なぜ非平衡な二分木は性能が悪いのですか？
二分探索木での探索・挿入・削除は、高さを
h として O(h) かかります。キーをソート済み順で挿入すると木は一直線になり、h は n まで伸びて各操作は O(n) に退化します。連結リストと変わりません。AVL木や赤黒木のような自己平衡木は、これを防ぐために高さを O(log n) に保ちます。関連リソース
その他の可視化
