C++で二分木のノードを削除する方法を徹底解説

このチュートリアルでは、C++における二分木（バイナリツリー）からノードを削除する方法について学びます。

二分木の削除の基本的な考え方

二分探索木（BST）と異なり、二分木のノードには特定の順序規則がありません。そのため、ノードを削除した後に木の構造をどのように整えればよいのでしょうか。

答えはシンプルです。削除したいノードを、木の中で最も深い位置にあるノード（最深ノード）と入れ替え、その後、最深ノードを削除します。この手法により、木の構造を崩すことなく任意のノードを取り除くことができます。

解決手順

それでは、問題を解決するための手順を確認しましょう。

• 二分木のノード構造体を定義し、木を初期化します。
• 木のノードを出力するための関数（先行順・中間順・後行順のいずれか）を作成します。
• 指定されたキーを持つノードを検索して削除する関数を作成します。
  • 木を走査するためにキューを初期化します。
  • キューが空になるまで反復処理を行います。
  • 指定されたキーを持つノードを見つけたら、変数に保存しておきます。
  • キューから最後に取り出されるノードが最深ノードとなります。
• 別の関数を使って最深ノードを削除します。
  • キューを使って木を走査します。
  • 該当ノードが見つかったら、親からの参照を切り離してメモリを解放し、処理を終了します。
• 木を出力して、ノードが正しく削除されたかどうかを確認します。

サンプルコード

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
struct Node* newNode(int data) {
    struct Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
};
void inorder(struct Node* node) {
    if (node == NULL) {
        return;
    }
    inorder(node->left);
    cout << node->data << " ";
    inorder(node->right);
}
void deleteDeepestNode(struct Node* root, struct Node* deleting_node){
    queue<struct Node*> nodes;
    nodes.push(root);
    struct Node* temp;
    while (!nodes.empty()) {
        temp = nodes.front();
        nodes.pop();
        if (temp == deleting_node) {
            temp = NULL;
            delete (deleting_node);
            return;
        }
        if (temp->right) {
            if (temp->right == deleting_node) {
                temp->right = NULL;
                delete deleting_node;
                return;
            }
            else {
                nodes.push(temp->right);
            }
        }
        if (temp->left) {
            if (temp->left == deleting_node) {
                temp->left = NULL;
                delete deleting_node;
                return;
            }
            else {
                nodes.push(temp->left);
            }
        }
    }
}
Node* deleteNode(struct Node* root, int key) {
    if (root == NULL){
        return NULL;
    }
    if (root->left == NULL && root->right == NULL) {
        if (root->data == key) {
            return NULL;
        }
        else {
            return root;
        }
    }
    queue<struct Node*> nodes;
    nodes.push(root);
    struct Node* temp;
    struct Node* key_node = NULL;
    while (!nodes.empty()) {
        temp = nodes.front();
        nodes.pop();
        if (temp->data == key) {
            key_node = temp;
        }
        if (temp->left) {
            nodes.push(temp->left);
        }
        if (temp->right) {
            nodes.push(temp->right);
        }
    }
    if (key_node != NULL) {
        int deepest_node_data = temp->data;
        deleteDeepestNode(root, temp);
        key_node->data = deepest_node_data;
    }
    return root;
}
int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(4);
    root->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->left = newNode(8);
    root->right->left->right = newNode(9);
    cout << "Tree before deleting key: ";
    inorder(root);
    int key = 5;
    root = deleteNode(root, key);
    cout << "\nTree after deleting key: ";
    inorder(root);
    cout << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

Tree before deleting key: 3 2 4 1 8 6 9 5 7
Tree after deleting key: 3 2 4 1 8 6 9 7

コードのポイント

このアルゴリズムでは、幅優先探索（BFS）に基づいてレベル順に木を走査することで、最深ノードを効率的に特定しています。削除対象ノードが見つかった場合でも走査を続けることで、必ず最後に出てくるノードが最深ノードになります。その値を削除対象ノードにコピーした上で、最深ノードへの参照を親から切り離し、delete演算子でメモリを解放します。

計算量は、木の走査が必要なため O(n) となります。ただし、この方法では木の平衡性や順序は保証されない点に注意してください。あくまで「構造を保ちながらノードを除去する」ためのシンプルな手法です。

まとめ

本チュートリアルでは、C++で二分木からノードを削除する方法を、キューを用いた幅優先探索による実装例とともに解説しました。最深ノードとの入れ替えというシンプルなアイデアで、順序を持たない二分木でも安全にノードを削除できることを理解できたと思います。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。