【C++】二分木から指定した値xを持つ葉ノードを削除する方法

このチュートリアルでは、二分木から指定された値を持つ葉ノード（リーフノード）を削除する方法を学びます。再帰的なアプローチを用いて、木を走査しながら条件に合致する葉ノードを取り除いていきます。

解決の手順

• 二分木のノードを表す構造体 Node を定義します。

• 木を走査（中順・前順・後順）して、すべてのノードのデータを出力する関数を作成します。

• 構造体を使ってノードを生成し、木を初期化します。

• 削除対象となる値 x を設定します。

• 指定された値を持つ葉ノードを削除する関数を作成します。この関数は、根ノードと値 x の2つの引数を受け取ります。

  • 根が NULL の場合はそのまま返します。

  • 根の左の子ノードを、削除処理後の新しい部分木で置き換えます。

  • 右の子ノードも同様に置き換えます。

  • 現在の根ノードのデータが x と等しく、かつ葉ノードである場合は、NULL ポインタを返してノードを削除します。

  • 最後に根ノードを返します。

コード例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
struct Node* newNode(int data) {
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
Node* deleteLeafNodes(Node* root, int x) {
    if (root == NULL) {
        return nullptr;
    }
    root->left = deleteLeafNodes(root->left, x);
    root->right = deleteLeafNodes(root->right, x);
    // 現在のノードのデータとxを比較
    if (root->data == x && root->left == NULL && root->right == NULL) {
        // ノードを削除
        return nullptr;
    }
    return root;
}
void inorder(Node* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}
int main(void) {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(3);
    root->left->right = newNode(4);
    root->right->right = newNode(5);
    root->right->left = newNode(4);
    root->right->right->left = newNode(4);
    root->right->right->right = newNode(4);
    deleteLeafNodes(root, 4);
    cout << "Tree: ";
    inorder(root);
    cout << endl;
    return 0;
}

出力結果

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

Tree: 3 2 1 3 5

アルゴリズムのポイント

この実装の重要なポイントは、子ノードの削除処理を先に行い、その後に現在のノードが葉ノードになったかどうかを判定する点です。これにより、子ノードが削除されたことで新たに葉となったノードも、値が x に一致していれば自動的に削除されます。つまり、連鎖的な削除にも対応できる堅牢なアルゴリズムになっています。

まとめ

このチュートリアルでは、C++を使って二分木から指定した値を持つ葉ノードを再帰的に削除する方法を解説しました。後順（postorder）に近い流れで処理を行うことで、木全体を一度の走査で効率的に処理できる点も魅力です。チュートリアルの内容について質問がある場合は、ぜひコメント欄でお知らせください。