C ++のバイナリツリーでの削除？

削除は、削除されたモードを一番下の右端のノードに置き換えることによって実行されます。

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

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

削除（struct Node * root、int data）関数は、指定されたデータ値を持つノードを削除するために使用されます。ルートノードとデータ値を検索して削除します。子ノードがなく、データ値がルートのデータ値と等しい場合はnullが返され、そうでない場合はルートノードが返されます。

Node* deletion(struct Node* root, int data){
   if (root == NULL)
      return NULL;
   if (root->leftChild == NULL && root->rightChild == NULL) {
      if (root->data == data)
         return NULL;
      else
         return root;
   }

ここで、タイプstruct Node *のキューを作成し、qという名前を付けて、ルートノードをqにプッシュします。また、Nodeへのポインタであるtempとdata_nodeを宣言し、data_nodeをNULLとして設定します。

struct Node* temp;
struct Node* data_node = NULL;

次に、レベル順トラバーサルを実行して、最も深いノードを見つけます。 whileループは、キューqが空でなくなるまで実行されます。キューはFIFOデータ構造であるため、レベル順トラバーサルを実行すると、キューの最後の要素が右端の最も深いノードになります。一時は常にキューの先頭を指し、要素は先頭からポップされます。

while (!q.empty()) {
   temp = q.front();
   q.pop();
   if (temp->data == data)
      data_node = temp;
   if (temp->leftChild)
      q.push(temp->leftChild);
   if (temp->rightChild)
   q.push(temp->rightChild);
}

次に、data_nodeがNULLでない場合、削除するノードをxに格納し、最も深いノードであるtempを削除します。次に、data_node値が最も深いノード値に置き換えられ、最も深いノードが削除されます。削除と置換の後、関数から新しいノードが返されます。

if (data_node != NULL) {
   int x = temp->data;
   deleteDeepest(root, temp);
   data_node->data = x;
}

deleteDeepest（struct Node * root、struct Node * deepestNode）関数は、渡されたノードが実際に最も深いノードであるか、右または左の子が最も深いノードであるかを確認します。この場合、子の値をnullに設定してから、親を削除します。最も深いノード。

void deleteDeepest(struct Node* root,
   struct Node* deepestNode){
      queue<struct Node*> q;
      q.push(root);
      struct Node* temp;
      while (!q.empty()) {
         temp = q.front();
         q.pop();
      if (temp == deepestNode) {
         temp = NULL;
         delete (deepestNode);
         return;
      }
      if (temp->rightChild) {
         if (temp->rightChild == deepestNode) {
            temp->rightChild = NULL;
            delete (deepestNode);
            return;
         }
         else
            q.push(temp->rightChild);
         }
      if (temp->leftChild) {
         if (temp->leftChild == deepestNode) {
            temp->leftChild = NULL;
            delete (deepestNode);
            return;
         }
         else
            q.push(temp->leftChild);
      }
   }
}

例

次の実装を見て、バイナリツリーの削除を確認しましょう-

#include <iostream>
#include <queue>
using namespace std;
struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};
struct Node* NewNode(int data){
   struct Node* temp = new Node;
   temp->data = data;
   temp->leftChild = temp->rightChild = NULL;
   return temp;
};
void inorder(struct Node* temp){
   if (!temp)
      return;
   inorder(temp->leftChild);
   cout << temp->data << " ";
   inorder(temp->rightChild);
}
void deleteDeepest(struct Node* root,
   struct Node* deepestNode){
      queue<struct Node*> q;
      q.push(root);
      struct Node* temp;
      while (!q.empty()) {
         temp = q.front();
         q.pop();
         if (temp == deepestNode) {
            temp = NULL;
            delete (deepestNode);
            return;
         }
         if (temp->rightChild) {
            if (temp->rightChild == deepestNode) {
               temp->rightChild = NULL;
               delete (deepestNode);
               return;
            }
            else
               q.push(temp->rightChild);
         }
         if (temp->leftChild) {
            if (temp->leftChild == deepestNode) {
               temp->leftChild = NULL;
               delete (deepestNode);
               return;
            }
         else
            q.push(temp->leftChild);
         }
      }
   }
Node* deletion(struct Node* root, int data){
   if (root == NULL)
      return NULL;
   if (root->leftChild == NULL && root->rightChild == NULL) {
      if (root->data == data)
         return NULL;
      else
         return root;
   }
   queue<struct Node*> q;
   q.push(root);  
   struct Node* temp;
   struct Node* data_node = NULL;
while (!q.empty()) {
   temp = q.front();
   q.pop();
   if (temp->data == data)
      data_node = temp;
   if (temp->leftChild)
      q.push(temp->leftChild);
   if (temp->rightChild)
      q.push(temp->rightChild);
}
if (data_node != NULL) {
   int x = temp->data;
   deleteDeepest(root,temp);
   data_node->data = x;
   }
   return root;
}
// Driver code
int main(){
   struct Node* root = NewNode(12);
   root->leftChild = NewNode(13);
   root->leftChild->leftChild = NewNode(9);
   root->leftChild->rightChild = NewNode(14);
   root->rightChild = NewNode(11);
   root->rightChild->leftChild = NewNode(17);
   root->rightChild->rightChild = NewNode(10);
   cout << "Inorder traversal before deletion : ";
   inorder(root);
   int data = 13;
   root = deletion(root, data);
   cout <<endl<< "Inorder traversal after deletion : ";
   inorder(root);
   return 0;
}

出力

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

Inorder traversal before deletion : 9 13 14 12 17 11 10
Inorder traversal after deletion : 9 10 14 12 17 11