C++のdeleteキーワードを使って二分木（バイナリツリー）を削除する方法

このチュートリアルでは、C++のdeleteキーワードを使って二分木（バイナリツリー）を削除する方法を学びます。

二分木の削除には、デストラクタメンバ関数を利用します。デストラクタとは、オブジェクトがスコープを抜けたときや、deleteによって明示的に破棄されたときに自動的に呼び出される特殊なメンバ関数のことです。

デストラクタの名前は、クラス名の先頭にチルダ（~）を付けた形で定義します。

解決のための手順

それでは、二分木を削除するまでの手順を順番に見ていきましょう。

• Nodeという名前のクラスを定義します。

• ノードのデータを受け取るコンストラクタを作成します。

• デストラクタを定義します。

  • 左側の子ノードを削除します。

  • 右側の子ノードを削除します。

  • 現在のノードのデータを出力します。

• ダミーデータを使って二分木を初期化します。

• delete rootステートメントで二分木全体を削除します。

コード例

#include <bits/stdc++.h>
using namespace std;
class Node {
    public:
    int data;
    Node* left;
    Node* right;
    // コンストラクタ
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
    // デストラクタ
    ~Node() {
        // 左右のポインタを削除
        delete left;
        delete right;
        // ノードのデータを出力
        cout << "Deleted node with data " << this->data << endl;
    }
};
int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    // デストラクタを使って木全体を削除
    delete root;
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

Deleted node with data 4
Deleted node with data 5
Deleted node with data 2
Deleted node with data 6
Deleted node with data 7
Deleted node with data 3
Deleted node with data 1

削除の仕組みのポイント

出力結果から分かるように、ノードは「左の子 → 右の子 → 自身」の順番、つまり後行順（ポストオーダー）で削除されていきます。これは、デストラクタ内でまず左右の子ノードに対してdeleteを呼び出し、その処理が完了した後に自身のデータを出力する構造になっているためです。子ノードから先に解放することで、メモリリークを防ぎながら木全体を安全に削除できるのがポイントです。

まとめ

このように、デストラクタとdeleteキーワードを組み合わせることで、再帰的な処理を明示的に書かなくても、二分木全体をシンプルかつ安全に削除できます。本チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。