C++で指定した値kを持つ葉ノードを削除する方法

このチュートリアルでは、二分木から指定した値を持つ葉ノード（リーフノード）を削除する方法を学びます。再帰的なアプローチを使えば、この問題はシンプルかつ効率的に解決できます。

解決の手順

問題を解くためのステップは以下の通りです。

• 二分木用の Node 構造体を定義します。
• 木を走査してすべてのデータを出力する関数（中順・前順・後順トラバーサル）を作成します。
• Node 構造体を使ってノードを生成し、木を初期化します。
• 削除対象の値 k を設定します。
• 指定した値を持つ葉ノードを削除する関数を作成します。この関数は、根ノードと値 k の2つの引数を受け取ります。
  • 根が NULL の場合はそのまま返します。
  • 左の子ノードに対して再帰的に処理を行い、結果で置き換えます。
  • 右の子ノードについても同様に処理します。
  • 現在のノードのデータが k と一致し、かつ葉ノード（左右の子が存在しない）である場合は、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 k) {
    if (root == NULL) {
        return nullptr;
    }
    root->left = deleteLeafNodes(root->left, k);
    root->right = deleteLeafNodes(root->right, k);
    // 現在のノードの値とkを比較
    if (root->data == k && 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

この例では、値4を持つすべての葉ノードが削除されています。注目すべき点として、削除によって新たに葉になったノードは、今回の実装では削除されません。もし連鎖的に削除したい場合は、処理を繰り返し適用する必要があります。

まとめ

再帰を使った葉ノードの削除は、子ノード側から処理を行うことで、親ノードへの影響を正しく反映できるのがポイントです。木構造の操作に慣れるための良い練習問題なので、ぜひ自分でもコードを書いて動作を確認してみてください。