二分木の基礎知識（概念、特性、走査方法）について前回の記事で学びました。今回は主にコードの実装に焦点を当てます。

目次

二分木の疑似作成 二分木の走査 二分木のノード数の取得 二分木の葉ノード数の取得 二分木の第Kレベルのノード数の取得 二分木の高さの取得 二分木での要素検索

二分木の疑似作成

なぜ疑似作成と呼ぶのでしょうか。二分木の作成は非常に複雑なプロセスであるため、学習の初期段階では手動での作成から始めます。木はノードの集合で構成されるため、まずノードを作成する必要があります。ノードの表現にはシンプルな子表現法を使用します：

// 木のノード
static class Node {
    public char data; // データ領域
    public Node left; // 左部分木
    public Node right; // 右部分木

    public Node(char data) {
        this.data = data;
    }
}

作成する二分木の図形は以下の通りです：

public Node createBinaryTree() {
    Node A = new Node('A');
    Node B = new Node('B');
    Node C = new Node('C');
    Node D = new Node('D');
    Node E = new Node('E');
    Node F = new Node('F');
    Node G = new Node('G');
    // 図形の関係に基づいてノード間を接続
    A.left = B;
    A.right = C;
    B.left = D;
    B.right = E;
    C.left = F;
    C.right = G;
    // 根ノードを返す
    return A;
}

二分木の走査

二分木の作成が完了したら、期待通りの結果が得られるか確認するために走査して表示します。4つの走査方法は以前にも学びました。

先行順走査：

// 先行順走査
public void preOrder(Node root) {
    if (root == null) {
        return;
    }
    // 根ノードの値を出力
    System.out.print(root.data+" ");
    // 根の左部分木を再帰的に走査
    preOrder(root.left);
    // 根の右部分木を再帰的に走査
    preOrder(root.right);
}

再帰の制限条件：rootがnullに到達したとき、戻り始めます。再帰が深まるにつれて、rootはnullに近づいていきます。

中間順走査：

// 中間順走査
public void inOrder(Node root) {
    // 中間順走査：左部分木→根→右部分木
    if (root == null) {
        return;
    }
    // 根の左部分木を再帰的に走査
    inOrder(root.left);
    // 根ノードの値を出力
    System.out.print(root.data+" ");
    // 根の右部分木を再帰的に走査
    inOrder(root.right);
}

後行順走査：

// 後行順走査
public void postOrder(Node root) {
    // 後行順走査：左部分木→右部分木→根
    if (root == null) {
        return;
    }
    // 根の左部分木を再帰的に走査
    postOrder(root.left);
    // 根の右部分木を再帰的に走査
    postOrder(root.right);
    // 根ノードの値を出力
    System.out.print(root.data+" ");
}

レベル順走査は比較的複雑なため、後で学習します。

二分木のノード数の取得

方法1：これも二分木の走査と同様に、空でないノードに遭遇するたびに++し、最終的に木のノード数を統計します。

// ノード数を記録
public int nodeCount; 
public void countNodes(Node root) {
    if (root == null) {
        return;
    }
    // 根ノード
    nodeCount++;
    // 左部分木
    countNodes(root.left);
    // 右部分木
    countNodes(root.right);
}

方法2：木全体のノード数は、根ノード+左部分木のノード数+右部分木のノード数に等しい

// 木のノード数を取得
public int getNodeCount(Node root) {
    if (root == null) {
        return 0;
    }
    // 左部分木のノード数+右部分木のノード数+根ノード
    return getNodeCount(root.left)+getNodeCount(root.right)+1;
}

方法1は走査方式を採用し、方法2は部分問題への分割方式を採用しています。方法2は再帰に近いアプローチです。

二分木の葉ノード数の取得

考え方：まず、葉ノードとは何かを理解する必要があります。葉ノードの特徴は、その左子と右子が両方ともnullであることです。これも走査方式を採用します。

方法1：部分問題のアプローチを使用

// 葉ノード数を取得
public int getLeafNodeCount(Node root) {
    if (root == null) {
        return 0;
    }
    // 葉ノードに遭遇したら1を返す
    if (root.left == null && root.right == null) {
        return 1;
    }
    // 左部分木の葉ノード数+右部分木の葉ノード数を返す
    return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}

方法2：走査方式を使用

public int leafCount;
public void countLeafNodes(Node root) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null) {
        leafCount++;
    }
    // 左部分木を走査
    countLeafNodes(root.left);
    // 右部分木を走査
    countLeafNodes(root.right);
}

二分木の第Kレベルのノード数の取得

上記は第Kレベルの紹介で、根ノードを第一レベルとしています。

考え方：Kが1の場合、このレベルのノード数を直接返すことができます。したがって、Kが1に近づくように再帰する必要があります。

方法1：部分問題のアプローチを使用

// 第Kレベルのノード数を取得
public int getKLevelNodeCount(Node root, int k) {
    // Kが無効な場合はないと仮定
    if (root == null) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    // 左部分木の第k-1レベルのノード数+右部分木の第k-1レベルのノード数
    return getKLevelNodeCount(root.left, k-1) +
            getKLevelNodeCount(root.right, k-1);
}

方法2：走査方式を使用

public int levelNodeCount;
public void getKLevelNodeCount(Node root, int k) {
    // Kが無効な場合はないと仮定
    if (root == null) {
        return;
    }
    if (k == 1) {
        levelNodeCount++;
    }
    // 左部分木の第k-1レベルを走査
    getKLevelNodeCount(root.left, k-1);
    // 右部分木の第k-1レベルを走査
    getKLevelNodeCount(root.right, k-1);
}

二分木の高さの取得

考え方：二分木の高さの取得は、第Kレベルのノード数の取得に似ています。同様に、根ノードの高さを1とします。次に、左部分木と右部分木の高さの最大値をそれぞれ再帰的に計算します。

部分問題のアプローチを使用

// 二分木の高さを取得
public int getTreeHeight(Node root) {
    if (root == null) {
        return 0;
    }
    // 左部分木と右部分木の最大の高さ+根ノード
    return Math.max(getTreeHeight(root.left), getTreeHeight(root.right)) + 1;
}

これを部分問題のアプローチではなく、走査方式で書くと、レベル順走査でしか書けません。また、レベル順走査は非常に複雑であるため、当面はこのコードは書きません。

二分木での要素検索

考え方：これは比較的簡単で、走査して比較するだけです。

// 値valueの要素が存在するか検出
public Node search(Node root, int value) {
    if (root == null) {
        return null;
    }
    // 先行順走査の方式を使用：根→左部分木→右部分木
    // 根
    if (root.data == value) {
        return root;
    }
    // 左部分木で検索、結果があるはず
    Node foundLeft = search(root.left, value);
    // nullでない場合は見つかったことになる
    if (foundLeft != null) {
        return foundLeft;
    }
    // 右部分木で検索、結果に関係なく直接返す
    return search(root.right, value);
}

注意：ここで二分木内のノードを検索する際、先行順走査の方式が最も効率的です。なぜなら先行順走査はまず根ノードを比較し、まさに根ノードを比較する必要があるからです。

二分木の基本的な操作はこれで学習完了です。これらの基本的な操作を基に、簡単な問題演習を行うことができます。今後も問題演習の中で二分木の関連操作を引き続き改善していきます。