Chương trình C ++ để thực hiện các phép toán từ điển trong cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân là một cây nhị phân được sắp xếp trong đó tất cả các nút có hai thuộc tính sau đây−

Cây con bên phải của một nút có khóa lớn hơn khóa của nút cha của nó.

Cây con bên trái của một nút có khóa nhỏ hơn hoặc bằng khóa của nút cha của nó.

Mỗi nút không được có nhiều hơn hai nút con.

Đây là một chương trình C ++ để thực hiện các phép toán từ điển trong cây tìm kiếm nhị phân.

Thuật toán

Để chèn:

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.

Đối với tìm kiếm, một giá trị:

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.

Để xóa:

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

Ví dụ

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

Đầu ra

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