C++プログラムで値kのリーフノードを削除します

このチュートリアルでは、指定された値を持つツリーからリーフノードを削除する方法を学習します。

問題を解決するための手順を見てみましょう。

• 二分木の構造体ノードを記述します。

• ツリーをトラバース（順序付け、事前順序付け、事後順序付け）し、すべてのデータを出力する関数を記述します。

• 構造体を使用してノードを作成し、ツリーを初期化します。

• x値を初期化します。

• 指定された値を持つリーフノードを削除する関数を記述します。ルートノードと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);
   // checking the current node data with k
   if (root->data == k && root->left == NULL && root->right == NULL) {
      // deleting the node
      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

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。