C++プログラムのバイナリツリーでの削除

このチュートリアルでは、バイナリツリーのノードを削除する方法を学習します。

二分木のノードは、二分探索木のような順序には従いません。では、二分木でノードを削除した後にノードを配置するにはどうすればよいですか？

さて、ツリーの最も深いノードを削除ノードに置き換えます。次に、ノードから最も深いノードを削除します。

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

• バイナリノード構造体でツリーを初期化します。

• ツリーのノードを出力する関数（preorder、order、postorder）を記述します。

• ノードを削除する関数を記述します。

  • キューを初期化して、ツリーを反復処理します。

  • キューが空になるまで繰り返します。

  • 指定されたキーを持つノードを見つけて、変数に格納します。

  • そして、キューの最後のノードが最も深いノードです。

• 別の関数を使用して最も深いノードを削除します。

  • キューを使用してツリーをトラバースします。

  • ノードが見つかったら、それを削除して返します。

• ツリーを印刷して、ノードが削除されているかどうかを確認します。

例

コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
struct Node* newNode(int data) {
   struct Node* temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
};
void inorder(struct Node* node) {
   if (node == NULL) {
      return;
   }
   inorder(node->left);
   cout << node->data << " ";
   inorder(node->right);
}
void deleteDeepestNode(struct Node* root, struct Node* deleting_node){
   queue<struct Node*> nodes;
   nodes.push(root);
   struct Node* temp;
   while (!nodes.empty()) {
      temp = nodes.front();
      nodes.pop();
      if (temp == deleting_node) {
         temp = NULL;
         delete (deleting_node);
         return;
      }
      if (temp->right) {
         if (temp->right == deleting_node) {
            temp->right = NULL;
            delete deleting_node;
            return;
         }
         else {
            nodes.push(temp->right);
         }
      }
      if (temp->left) {
         if (temp->left == deleting_node) {
            temp->left = NULL;
            delete deleting_node;
            return;
         }
         else {
            nodes.push(temp->left);
         }
      }
   }
}
Node* deleteNode(struct Node* root, int key) {
   if (root == NULL){
      return NULL;
   }
   if (root->left == NULL && root->right == NULL) {
      if (root->data == key) {
         return NULL;
      }
      else {
         return root;
      }
   }
   queue<struct Node*> nodes;
   nodes.push(root);
   struct Node* temp;
   struct Node* key_node = NULL;
   while (!nodes.empty()) {
      temp = nodes.front();
      nodes.pop();
      if (temp->data == key) {
         key_node = temp;
      }
      if (temp->left) {
         nodes.push(temp->left);
      }
      if (temp->right) {
         nodes.push(temp->right);
      }
   }
   if (key_node != NULL) {
      int deepest_node_data = temp->data;
      deleteDeepestNode(root, temp);
      key_node->data = deepest_node_data;
   }
   return root;
}
int main() {
   struct Node* root = newNode(1);
   root->left = newNode(2);
   root->left->left = newNode(3);
   root->left->right = newNode(4);
   root->right = newNode(5);
   root->right->left = newNode(6);
   root->right->right = newNode(7);
   root->right->left->left = newNode(8);
   root->right->left->right = newNode(9);
   cout << "Tree before deleting key: ";
   inorder(root);
   int key = 5;
   root = deleteNode(root, key);
   cout << "\nTree after deleting key: ";
   inorder(root);
   cout << endl;
   return 0;
}

出力

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

Tree before deleting key: 3 2 4 1 8 6 9 5 7
Tree after deleting key: 3 2 4 1 8 6 9 7

結論

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