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

C++では、デストラクタとdeleteキーワードを組み合わせることで、二分木（バイナリツリー）全体を再帰的に解放できます。まずは、int型のデータと左右の子ノードへのポインタを持つクラスで二分木を定義してみましょう。ここでは、クラスのすべてのメンバをpublicとしています。

class btree_node {
   public:
      int data;
      btree_node* leftChild;
      btree_node* rightChild;
};

ノードの生成：コンストラクタ

新しいノードを作成するためのコンストラクタは、int型の値を引数として受け取り、新しく生成されたノードにその値を代入します。leftChildとrightChildはNULLで初期化されます。

btree_node(int data){
   this->data = data;
   this->leftChild = NULL;
   this->rightChild = NULL;
}

メモリの解放：デストラクタ

デストラクタが呼び出されると、deleteキーワードを使って左の子ノードと右の子ノードが削除されます。この仕組みにより、削除処理は自動的に子孫ノードへと再帰的に伝播していきます。

~btree_node(){
   delete leftChild;
   delete rightChild;
   cout << this->data << " is being deleted"<<endl;
}

木全体の削除を実行する

木全体の削除をトリガーするには、ルートノードに対してdeleteを呼び出すだけです。ルートの左部分木と右部分木も連鎖的に削除されるため、個別に各ノードを解放する必要はありません。

delete root;

サンプルコード

それでは、deleteキーワードを使用して二分木を削除する実際の実装例を見てみましょう。

#include <iostream>
using namespace std;
class btree_node {
   public:
   int data;
   btree_node* leftChild;
   btree_node* rightChild;
   btree_node(int data){
      this->data = data;
      this->leftChild = NULL;
      this->rightChild = NULL;
   }
   ~btree_node(){
      delete leftChild;
      delete rightChild;
      cout << this->data << " is being deleted"<<endl;
   }
};
int main(){
   btree_node* root = new btree_node(2);
   btree_node* node1 = new btree_node(4);
   btree_node* node2 = new btree_node(6);
   btree_node* node3 = new btree_node(8);
   btree_node* node4 = new btree_node(10);
   root->leftChild = node1;
   root->rightChild = node2;
   node1->leftChild = node3;
   node1->rightChild = node4;
   delete root;
   return 0;
}

出力結果

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

8 is being deleted
10 is being deleted
4 is being deleted
6 is being deleted
2 is being deleted

出力を見ると、葉に近いノードから順に削除されていることがわかります。これは、デストラクタ内で先に子ノードをdeleteしてから自身のデータを出力しているため、木の事後順（ポストオーダー）走査と同じ順序でメモリ解放が行われるからです。この手法を使えば、ルートをdeleteするだけで木全体のメモリを確実に解放でき、メモリリークを防ぐことができます。