二分探索木で辞書操作を実行するC++プログラム

二分探索木は、すべてのノードが次の2つのプロパティを持つソートされた二分木です-

ノードの右側のサブツリーには、その親ノードのキーよりも大きいキーがあります。

ノードの左側のサブツリーには、その親ノードのキー以下のキーがあります。

各ノードには2つ以上の子を含めることはできません。

これは、二分探索木で辞書操作を実行するためのC++プログラムです。

アルゴリズム

挿入の場合：

Begin
   Declare function insert(int k)
      in = int(k mod max)
      p[in] = (n_type*) malloc(sizeof(n_type))
      p[in]->d = k
      if (r[in] == NULL) then
         r[in] = p[in]
         r[in]->n = NULL
         t[in] = p[in]
      else
         t[in] = r[in]
         while (t[in]->n != NULL)
            t[in] = t[in]->n
         t[in]->n= p[in]
End.

値を検索する場合：

Begin
   Declare function search(int k)
      int flag = 0
      in= int(k mod max)
      t[in] = r[in]
      while (t[in] != NULL) do
         if (t[in]->d== k) then
            Print “Search key is found”.
            flag = 1
            break
         else
            t[in] = t[in]->n
      if (flag == 0)
         Print “search key not found”.
End.

削除の場合：

Begin
   Declare function delete_element(int k)
      in = int(k mod max)
      t[in] = r[in]
      while (t[in]->d!= k and t[in] != NULL)
         p[in] = t[in]
         t[in] = t[in]->n
      p[in]->n = t[in]->n
      Print the deleted element
      t[in]->d = -1
      t[in] = NULL
      free(t[in])
End

例

#include<iostream>
#include<stdlib.h>
using namespace std;
# define max 20
typedef struct dictionary {
   int d;
   struct dictionary *n;
} n_type;
n_type *p[max], *r[max], *t[max];
class Dict {
   public:
      int in;
      Dict();
      void insert(int);
      void search(int);
      void delete_element(int);
};
int main(int argc, char **argv) {
   int v, choice, n, num;
   char c;
   Dict d;
   do {
      cout << "\n1.Create";
      cout << "\n2.Search for a value";
      cout<<"\n3.Delete a value";
      cout << "\nEnter your choice:";
      cin >> choice;
      switch (choice) {
         case 1:
            cout << "\nEnter the number of elements to be inserted:";
            cin >> n;
            cout << "\nEnter the elements to be inserted:";
            for (int i = 0; i < n; i++) {
               cin >> num;
               d.insert(num);
            }
         break;
         case 2:
            cout << "\nEnter the element to be searched:";
            cin >> n;
            d.search(n);
         case 3:
            cout << "\nEnter the element to be deleted:";
            cin >> n;
            d.delete_element(n);
         break;
         default:
            cout << "\nInvalid choice....";
            break;
      }
      cout << "\nEnter y to continue......";
      cin >> c;
   }
   while (c == 'y');
}
Dict::Dict() {
   in = -1;
   for (int i = 0; i < max; i++) {
      r[i] = NULL;
      p[i] = NULL;
      t[i] = NULL;
   }
}
void Dict::insert(int k) {
   in = int(k % max);
   p[in] = (n_type*) malloc(sizeof(n_type));
   p[in]->d = k;
   if (r[in] == NULL) {
      r[in] = p[in];
      r[in]->n = NULL;
      t[in] = p[in];
   } else {
      t[in] = r[in];
      while (t[in]->n != NULL)
      t[in] = t[in]->n;
      t[in]->n= p[in];
   }
}
void Dict::search(int k) {
   int flag = 0;
   in= int(k % max);
   t[in] = r[in];
   while (t[in] != NULL) {
      if (t[in]->d== k) {
         cout << "\nSearch key is found!!";
         flag = 1;
         break;
      } else
         t[in] = t[in]->n;
   }
   if (flag == 0)
      cout << "\nsearch key not found.......";
}
void Dict::delete_element(int k) {
   in = int(k % max);
   t[in] = r[in];
   while (t[in]->d!= k && t[in] != NULL) {
      p[in] = t[in];
      t[in] = t[in]->n;
   }
   p[in]->n = t[in]->n;
   cout << "\n" << t[in]->d << " has been deleted.";
   t[in]->d = -1;
   t[in] = NULL;
   free(t[in]);
}

出力

1.Create
2.Search for a value
3.Delete a value
Enter your choice:1
Enter the number of elements to be inserted:3
Enter the elements to be inserted:111 222 3333
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:2
Enter the element to be searched:111
Search key is found!!
Enter the element to be deleted:222
222 has been deleted.
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:222
Invalid choice....
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:2
Enter the element to be searched:222
search key not found.......
Enter the element to be deleted:0