C++で値kの葉ノード（リーフノード）を削除する方法

C++で二分木を扱う際、「特定の値kを持つ葉ノード（リーフノード）だけを削除したい」というケースがあります。本記事では、再帰処理を活用して値kの葉ノードを削除する方法を、サンプルコードとともにわかりやすく解説します。

1. ノード構造体の定義

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

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

2. 新しいノードを生成する関数

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

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

3. 値kの葉ノードを削除する関数

続いて、本体となる deleteLeafNode(Node* root, int k) 関数です。この関数はルートノードと、削除したいノードの値 k を引数として受け取ります。処理の流れは以下のとおりです。

• ノードが NULL の場合は、そのまま nullptr を返します。
• 左右の子に対して再帰的に同じ関数を呼び出し、葉に近いノードから順に削除処理を行います。
• 「ノードの値が k と一致し、かつ左右どちらの子も持たない」場合にのみ、そのノードを削除します（nullptr を返すことで親からの参照を切ります）。
• 最後に、削除処理を反映したルートノードを返します。

Node* deleteLeafNode(Node* root, int k) {
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteLeafNode(root->leftChild, k);
    root->rightChild = deleteLeafNode(root->rightChild, k);
    if (root->data == k && root->leftChild == NULL &&
        root->rightChild == NULL)
        return nullptr;
    return root;
}

ここでのポイントは、この関数が削除するのは「値が k の葉ノードのみ」という点です。子を持つ内部ノードは、たとえ値が k であっても削除されません。ただし、子ノードが削除された結果として親が葉になり、その値も k であれば、親も同時に削除されます。

4. 木を走査して表示する関数

削除後の木の状態を確認するため、inorder(Node* root) 関数を用意します。この関数は再帰的に木をたどり、左の子 → 右の子 → 自分自身の順で各ノードの値を出力します。

void inorder(Node* root){
    if (root != NULL){
        inorder(root->leftChild);
        inorder(root->rightChild);
        cout << root->data << " ";
    }
}

実装例

それでは、値 k を持つ葉ノードを削除するプログラム全体を見てみましょう。

#include <iostream>
using namespace std;

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

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

Node* deleteLeafNode(Node* root, int k){
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteLeafNode(root->leftChild, k);
    root->rightChild = deleteLeafNode(root->rightChild, k);
    if (root->data == k && root->leftChild == NULL &&
    root->rightChild == NULL)
        return nullptr;
    return root;
}

void inorder(Node* root){
    if (root != NULL){
        inorder(root->leftChild);
        inorder(root->rightChild);
        cout << root->data << " ";
    }
}

int main(void){
    struct Node* root = newNode(6);
    root->leftChild = newNode(7);
    root->rightChild = newNode(7);
    root->leftChild->leftChild = newNode(5);
    root->leftChild->rightChild = newNode(3);
    root->rightChild->rightChild = newNode(7);

    deleteLeafNode(root, 7);

    cout << "Inorder traversal after deleting given leaf node: ";
    inorder(root);

    return 0;
}

このサンプルでは、値 7 を持つノードを複数含む二分木を構築しています。削除対象になるのは「葉ノードである 7」だけであり、子を持つノード（左側の 7）は値が同じでも残る点に注目してください。

出力結果

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

Inorder traversal after deleting given leaf node: 5 3 7 6

出力を見ると、値 7 の葉ノードが正しく削除され、残りのノード（5、3、7、6）だけが出力されていることが確認できます。