Cây tìm kiếm nhị phân (BST) là cây nhị phân đã sắp xếp, nơi mọi nút có hai tính chất:
- Cây con phải của nút có khóa lớn hơn khóa nút cha.
- Cây con trái của nút có khóa nhỏ hơn hoặc bằng khóa nút cha.
- Mỗi nút không có quá hai nút con.
Đây là chương trình C++ thực hiện các phép toán từ điển (tìm, chèn, xóa) trên cây tìm kiếm nhị phân.
Thuật toán
Để chèn:
Begin
Khai báo hàm 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.
Để tìm kiếm giá trị:
Begin
Khai báo hàm 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
In "Search key is found".
flag = 1
break
else
t[in] = t[in]->n
if (flag == 0)
In "search key not found".
End.
Để xóa:
Begin
Khai báo hàm 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
In phần tử đã xóa
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);
break;
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]);
}
Kết quả
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