Cây tìm kiếm nhị phân (Binary Search Tree - BST) là một cây nhị phân được sắp xếp, trong đó tất cả các nút có các thuộc tính sau:
- 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â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.
- Mỗi nút không có quá hai nút con.
Dưới đây là chương trình C++ triển khai cây tìm kiếm nhị phân ngẫu nhiên.
Thuật toán
Bắt đầu
Lớp BST khai báo các hàm sau:
search() = Tìm kiếm một phần tử trong BST.
Khởi tạo temp = root;
while(temp != NULL)
Tăng độ sâu
if(temp->info == data)
In dữ liệu và độ sâu
else if(temp->info > data)
temp = temp->l;
else
temp = temp->r;
insert() = Chèn các phần tử vào cây:
Nếu cây rỗng, chèn dữ liệu làm gốc.
Nếu cây không rỗng:
Nếu data < root: chèn làm con trái.
Ngược lại: chèn làm con phải.
del() = Xóa một phần tử khỏi cây.
casea() = Được gọi từ del() nếu l = r = null.
caseb() = Được gọi từ del() nếu l != null, r = null.
caseb() = Được gọi từ del() nếu l = null, r != null.
casec() = Được gọi từ del() nếu l != null, r != null.
inorder() để duyệt nút theo thứ tự inorder: trái – gốc – phải.
preorder() để duyệt nút theo thứ tự preorder: gốc – trái – phải.
postorder() để duyệt nút theo thứ tự postorder: trái – phải – gốc
Kết thúc
Mã ví dụ
#include <iostream>
#include <cstdlib>
using namespace std;
struct nod {
int info;
struct nod *l;
struct nod *r;
}*r;
class BST {
public:
void search(nod *, int);
void find(int, nod **, nod **);
void insert(nod *, nod *);
void del(int);
void casea(nod *, nod *);
void caseb(nod *, nod *);
void casec(nod *, nod *);
void preorder(nod *);
void inorder(nod *);
void postorder(nod *);
void show(nod *, int);
BST() { r = NULL; }
};
void BST::find(int i, nod **par, nod **loc) {
nod *ptr, *ptrsave;
if (r == NULL) {
*loc = NULL;
*par = NULL;
return;
}
if (i == r->info) {
*loc = r;
*par = NULL;
return;
}
if (i < r->info)
ptr = r->l;
else
ptr = r->r;
ptrsave = r;
while (ptr != NULL) {
if (i == ptr->info) {
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (i < ptr->info)
ptr = ptr->l;
else
ptr = ptr->r;
}
*loc = NULL;
*par = ptrsave;
}
void BST::search(nod *root, int data) {
int depth = 0;
nod *temp = new nod;
temp = root;
while(temp != NULL) {
depth++;
if(temp->info == data) {
cout << "\nDữ liệu tìm thấy tại độ sâu: " << depth << endl;
return;
} else if(temp->info > data)
temp = temp->l;
else
temp = temp->r;
}
cout << "\n Dữ liệu không tìm thấy" << endl;
return;
}
void BST::insert(nod *tree, nod *newnode) {
if (r == NULL) {
r = new nod;
r->info = newnode->info;
r->l = NULL;
r->r = NULL;
cout << "Nút gốc đã được thêm" << endl;
return;
}
if (tree->info == newnode->info) {
cout << "Phần tử đã có trong cây" << endl;
return;
}
if (tree->info > newnode->info) {
if (tree->l != NULL) {
insert(tree->l, newnode);
} else {
tree->l = newnode;
(tree->l)->l = NULL;
(tree->l)->r = NULL;
cout << "Nút đã thêm vào bên trái" << endl;
return;
}
} else {
if (tree->r != NULL) {
insert(tree->r, newnode);
} else {
tree->r = newnode;
(tree->r)->l = NULL;
(tree->r)->r = NULL;
cout << "Nút đã thêm vào bên phải" << endl;
return;
}
}
}
void BST::del(int i) {
nod *par, *loc;
if (r == NULL) {
cout << "Cây rỗng" << endl;
return;
}
find(i, &par, &loc);
if (loc == NULL) {
cout << "Phần tử không có trong cây" << endl;
return;
}
if(loc->l == NULL && loc->r == NULL) {
casea(par, loc);
cout << "phần tử đã xóa" << endl;
}
if (loc->l != NULL && loc->r == NULL) {
caseb(par, loc);
cout << "phần tử đã xóa" << endl;
}
if (loc->l == NULL && loc->r != NULL) {
caseb(par, loc);
cout << "phần tử đã xóa" << endl;
}
if (loc->l != NULL && loc->r != NULL) {
casec(par, loc);
cout << "phần tử đã xóa" << endl;
}
free(loc);
}
void BST::casea(nod *par, nod *loc) {
if (par == NULL) {
r = NULL;
} else {
if (loc == par->l)
par->l = NULL;
else
par->r = NULL;
}
}
void BST::caseb(nod *par, nod *loc) {
nod *child;
if (loc->l != NULL)
child = loc->l;
else
child = loc->r;
if (par == NULL) {
r = child;
} else {
if (loc == par->l)
par->l = child;
else
par->r = child;
}
}
void BST::casec(nod *par, nod *loc) {
nod *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->r;
while (ptr->l != NULL) {
ptrsave = ptr;
ptr = ptr->l;
}
suc = ptr;
parsuc = ptrsave;
if (suc->l == NULL && suc->r == NULL)
casea(parsuc, suc);
else
caseb(parsuc, suc);
if (par == NULL) {
r = suc;
} else {
if (loc == par->l)
par->l = suc;
else
par->r = suc;
}
suc->l = loc->l;
suc->r = loc->r;
}
void BST::preorder(nod *ptr) {
if (r == NULL) {
cout << "Cây rỗng" << endl;
return;
}
if (ptr != NULL) {
cout << ptr->info << " ";
preorder(ptr->l);
preorder(ptr->r);
}
}
void BST::inorder(nod *ptr) {
if (r == NULL) {
cout << "Cây rỗng" << endl;
return;
}
if (ptr != NULL) {
inorder(ptr->l);
cout << ptr->info << " ";
inorder(ptr->r);
}
}
void BST::postorder(nod *ptr) {
if (r == NULL) {
cout << "Cây rỗng" << endl;
return;
}
if (ptr != NULL) {
postorder(ptr->l);
postorder(ptr->r);
cout << ptr->info << " ";
}
}
void BST::show(nod *ptr, int level) {
int i;
if (ptr != NULL) {
show(ptr->r, level+1);
cout << endl;
if (ptr == r)
cout << "Root->: ";
else {
for (i = 0; i < level; i++)
cout << " ";
}
cout << ptr->info;
show(ptr->l, level+1);
}
}
int main() {
int c, n, item;
BST bst;
nod *t;
while (1) {
cout << "1. Chèn phần tử" << endl;
cout << "2. Xóa phần tử" << endl;
cout << "3. Tìm kiếm phần tử" << endl;
cout << "4. Duyệt Inorder" << endl;
cout << "5. Duyệt Preorder" << endl;
cout << "6. Duyệt Postorder" << endl;
cout << "7. Hiển thị cây" << endl;
cout << "8. Thoát" << endl;
cout << "Nhập lựa chọn của bạn: ";
cin >> c;
switch(c) {
case 1:
t = new nod;
cout << "Nhập số cần chèn: ";
cin >> t->info;
bst.insert(r, t);
break;
case 2:
if (r == NULL) {
cout << "Cây rỗng, không có gì để xóa" << endl;
continue;
}
cout << "Nhập số cần xóa: ";
cin >> n;
bst.del(n);
break;
case 3:
cout << "Tìm kiếm:" << endl;
cin >> item;
bst.search(r, item);
break;
case 4:
cout << "Duyệt Inorder của BST:" << endl;
bst.inorder(r);
cout << endl;
break;
case 5:
cout << "Duyệt Preorder của BST:" << endl;
bst.preorder(r);
cout << endl;
break;
case 6:
cout << "Duyệt Postorder của BST:" << endl;
bst.postorder(r);
cout << endl;
break;
case 7:
cout << "Hiển thị BST:" << endl;
bst.show(r, 1);
cout << endl;
break;
case 8:
exit(1);
default:
cout << "Lựa chọn sai" << endl;
}
}
}
Kết quả đầu ra
1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 1 Nhập số cần chèn: 6 Nút gốc đã được thêm 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 1 Nhập số cần chèn: 7 Nút đã thêm vào bên phải 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 1 Nhập số cần chèn: 5 Nút đã thêm vào bên trái 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 1 Nhập số cần chèn: 4 Nút đã thêm vào bên trái 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 3 Tìm kiếm: 7 Dữ liệu tìm thấy tại độ sâu: 2 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 3 Tìm kiếm: 1 Dữ liệu không tìm thấy 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 4 Duyệt Inorder của BST: 4 5 6 7 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 5 Duyệt Preorder của BST: 6 5 4 7 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 6 Duyệt Postorder của BST: 4 5 7 6 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 7 Hiển thị BST: 7 Root->: 6 5 4 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 2 Nhập số cần xóa: 1 Phần tử không có trong cây 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 5 Duyệt Preorder của BST: 6 5 4 7 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 2 Nhập số cần xóa: 5 phần tử đã xóa 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 7 Hiển thị BST: 7 Root->: 6 4 1. Chèn phần tử 2. Xóa phần tử 3. Tìm kiếm phần tử 4. Duyệt Inorder 5. Duyệt Preorder 6. Duyệt Postorder 7. Hiển thị cây 8. Thoát Nhập lựa chọn của bạn: 8