C++で二分木のノードを削除する方法｜最深ノードとの置換アルゴリズム

二分木における削除処理の概要

二分木からのノード削除は、削除したいノードを「木の中で最も深い位置にある右端のノード」で置き換えることによって行われます。この手法では、まず削除対象ノードの値を最深ノードの値で上書きし、その後、最深ノードを木から切り離してメモリを解放します。

まず、データ本体と左右の子ノードへのポインタを保持する、ツリーノードを表す構造体を定義します。最初に作成されたノードはルートノードとなり、それ以降に作成されたものは子ノードとして扱われます。

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

新しいノードを作成する

次に、int型の値を受け取り、その値をノードのdataメンバに代入するnewNode(int data)関数を作成します。この関数は生成したNode構造体へのポインタを返します。また、新しく作成されたノードの左右の子ポインタはNULLに初期化されます。

struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}

削除関数deletion()の実装

deletion(struct Node* root, int data)関数は、指定されたデータ値を持つノードを削除するために使用されます。引数としてルートノードと、検索・削除対象となるデータ値を受け取ります。もし子ノードが存在せず、かつデータ値がルートのデータ値と一致する場合はNULLを返し、一致しない場合はそのままルートノードを返します。

Node* deletion(struct Node* root, int data){
   if (root == NULL)
      return NULL;
   if (root->leftChild == NULL && root->rightChild == NULL) {
      if (root->data == data)
         return NULL;
      else
         return root;
   }

続いて、struct Node* 型のキューqを作成し、そこにルートノードをプッシュします。また、Nodeへのポインタであるtempとdata_nodeを宣言し、data_nodeはNULLで初期化しておきます。

struct Node* temp;
struct Node* data_node = NULL;

次に、レベル順走査（幅優先探索）を行って最も深いノードを見つけます。whileループはキューqが空になるまで実行されます。キューはFIFO（先入れ先出し）のデータ構造なので、レベル順に走査していけば、キューの最後の要素が最も深い位置にある右端のノードとなります。tempは常にキューの先頭を指し、要素は前から順番にポップされていきます。

while (!q.empty()) {
   temp = q.front();
   q.pop();
   if (temp->data == data)
      data_node = temp;
   if (temp->leftChild)
      q.push(temp->leftChild);
   if (temp->rightChild)
      q.push(temp->rightChild);
}

その後、data_nodeがNULLでない場合、削除対象ノードのデータをxに保存し、tempが指す最深ノードを削除します。data_nodeの値は最深ノードの値で置き換えられ、最深ノード自体は削除されます。削除と置き換えが完了すると、更新されたルートノードが関数から返されます。

if (data_node != NULL) {
   int x = temp->data;
   deleteDeepest(root, temp);
   data_node->data = x;
}

deleteDeepest()関数による最深ノードの削除

deleteDeepest(struct Node* root, struct Node* deepestNode)関数は、渡されたノードが実際に最深ノードであるか、あるいはその左右の子が最深ノードであるかを確認します。該当する場合には、親ノード（deepestNode）をdeleteで解放する前に、対応する子ポインタをNULLに設定します。

void deleteDeepest(struct Node* root,
   struct Node* deepestNode){
      queue<struct Node*> q;
      q.push(root);
      struct Node* temp;
      while (!q.empty()) {
         temp = q.front();
         q.pop();
      if (temp == deepestNode) {
         temp = NULL;
         delete (deepestNode);
         return;
      }
      if (temp->rightChild) {
         if (temp->rightChild == deepestNode) {
            temp->rightChild = NULL;
            delete (deepestNode);
            return;
         }
         else
            q.push(temp->rightChild);
         }
      if (temp->leftChild) {
         if (temp->leftChild == deepestNode) {
            temp->leftChild = NULL;
            delete (deepestNode);
            return;
         }
         else
            q.push(temp->leftChild);
      }
   }
}

サンプルコード

以下の実装例では、二分木における実際の削除処理の一連の流れを確認できます。

#include <iostream>
#include <queue>
using namespace std;
struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};
struct Node* NewNode(int data){
   struct Node* temp = new Node;
   temp->data = data;
   temp->leftChild = temp->rightChild = NULL;
   return temp;
};
void inorder(struct Node* temp){
   if (!temp)
      return;
   inorder(temp->leftChild);
   cout << temp->data << " ";
   inorder(temp->rightChild);
}
void deleteDeepest(struct Node* root,
   struct Node* deepestNode){
      queue<struct Node*> q;
      q.push(root);
      struct Node* temp;
      while (!q.empty()) {
         temp = q.front();
         q.pop();
         if (temp == deepestNode) {
            temp = NULL;
            delete (deepestNode);
            return;
         }
         if (temp->rightChild) {
            if (temp->rightChild == deepestNode) {
               temp->rightChild = NULL;
               delete (deepestNode);
               return;
            }
            else
               q.push(temp->rightChild);
         }
         if (temp->leftChild) {
            if (temp->leftChild == deepestNode) {
               temp->leftChild = NULL;
               delete (deepestNode);
               return;
            }
         else
            q.push(temp->leftChild);
         }
      }
   }
Node* deletion(struct Node* root, int data){
   if (root == NULL)
      return NULL;
   if (root->leftChild == NULL && root->rightChild == NULL) {
      if (root->data == data)
         return NULL;
      else
         return root;
   }
   queue<struct Node*> q;
   q.push(root);  
   struct Node* temp;
   struct Node* data_node = NULL;
while (!q.empty()) {
   temp = q.front();
   q.pop();
   if (temp->data == data)
      data_node = temp;
   if (temp->leftChild)
      q.push(temp->leftChild);
   if (temp->rightChild)
      q.push(temp->rightChild);
}
if (data_node != NULL) {
   int x = temp->data;
   deleteDeepest(root,temp);
   data_node->data = x;
   }
   return root;
}
// Driver code
int main(){
   struct Node* root = NewNode(12);
   root->leftChild = NewNode(13);
   root->leftChild->leftChild = NewNode(9);
   root->leftChild->rightChild = NewNode(14);
   root->rightChild = NewNode(11);
   root->rightChild->leftChild = NewNode(17);
   root->rightChild->rightChild = NewNode(10);
   cout << "Inorder traversal before deletion : ";
   inorder(root);
   int data = 13;
   root = deletion(root, data);
   cout << endl<< "Inorder traversal after deletion : ";
   inorder(root);
   return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

Inorder traversal before deletion : 9 13 14 12 17 11 10
Inorder traversal after deletion : 9 10 14 12 17 11

この結果から、値13を持つノードが削除され、代わりに木の中で最も深く右側にあった値10がその位置へ移動していることが分かります。このように、最深ノードとの置換によって木の構造を崩さずにノードを削除できるのが、この手法の特徴です。