C ++で値kのリーフノードを削除しますか？

まず、データとその左右のノードの子を含むツリーノードを表す構造体を定義しましょう。これが最初に作成されるノードの場合はルートノード、それ以外の場合は子ノードです。

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

次に、int値を取得してノードのデータメンバーに割り当てるnewNode（int data）関数を作成します。この関数は、作成された構造体ノードへのポインターを返します。また、新しく作成されたノードの左右の子はnullに設定されます。

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

次に、ルートノードと削除するノードのデータ値を取得するdeleteNode（Node * root、int k）関数を作成します。指定されたノードが親ノードである場合、その左右の子も削除されます。この関数は、指定されたノードを削除した後、変更されたルートノードを返します。

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;
}

最後に、削除後にツリーを支払うために、inorder関数でツリーをトラバースする関数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;
}

出力

上記のコードは次の出力を生成します-

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