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

C++で値がxの葉ノードを削除するには？

本記事では、C++を使って二分木から「値がxと等しい葉ノード（リーフノード）」を削除する方法を解説します。ノード構造体の定義から、ノード生成用の関数、再帰的な削除処理、そして結果の表示まで、順を追って見ていきましょう。

1. ツリーノード構造体の定義

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

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

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

次に、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);
}

3. 葉ノードを削除するdeleteLeafNode関数

続いて、ルートノードと削除対象の値xを受け取るdeleteLeafNode(Node* root, int x)関数を作成します。この関数は再帰的に木をたどり、「値がxであり、かつ左右どちらの子も持たないノード（＝葉ノード）」を削除します。子ノードが削除された結果、親ノードが新たな葉になり、その値もxであれば、親ノードも連鎖的に削除されます。関数は、削除処理後の木のルートノードを返します。

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

4. 木の内容を表示するinorder関数

最後に、削除後の木の状態を確認するためのinorder(Node* root)関数を用意します。この関数は木を再帰的にたどりながら各ノードの値を出力します。なお、この実装は「左部分木→右部分木→根」の順で訪問するため、厳密には後順走査（postorder）に相当します。

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

サンプルコード（完全版）

以下は、値がxと等しい葉ノードを削除する処理全体をまとめた実装例です。この例では、ルート4の下に左子2・右子12が接続され、さらに2の下に3と5、12の下に9がぶら下がっています。deleteNode(root, 3)を呼び出すことで、値3の葉ノードのみが削除されます。

#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* deleteNode(Node* root, int x){
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteNode(root->leftChild, x);
    root->rightChild = deleteNode(root->rightChild, x);
    if (root->data == x && 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(4);
    root->leftChild = newNode(2);
    root->rightChild = newNode(12);
    root->leftChild->leftChild = newNode(3);
    root->leftChild->rightChild = newNode(5);
    root->rightChild->rightChild = newNode(9);

    deleteNode(root, 3);

    cout << "Inorder traversal after deletion : ";
    inorder(root);
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

Inorder traversal after deletion : 5 2 9 12 4

出力から、値3の葉ノードが正しく削除され、残りのノード（5, 2, 9, 12, 4）だけが出力されていることが確認できます。

まとめ

このように、再帰を使えば「値がxの葉ノードの削除」をシンプルに実装できます。ポイントは、左右の子に対する再帰呼び出しの結果を親ノードのポインタに代入し直すことで、削除されたノードへの参照を自動的に切り離せる点です。計算量は木のノード数に比例するO(n)となります。