二进制搜索树中执行字典操作的C ++程序

二进制搜索树是排序的二进制树，其中所有节点都具有以下两个属性：

节点的右子树的键大于其父节点的键。

节点的左子树的键小于或等于其父节点的键。

每个节点不应有两个以上的子节点。

这是一个在二进制搜索树中执行字典操作的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 << " 已被删除。";
   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 已被删除。
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