Giải phương trình bậc nhất ax + b = 0 trong C / C++ 
Lệnh Alert trong Javascript Tìm kiếm trên cây nhị phân tìm kiếm
Trong bài viết này, codehow sẽ hướng dẫn các bạn cách tìm kiếm trên cây nhị phân tìm kiếm. Đúng như tên của nó là cây nhị phân tìm kiếm, thao tác tìm kiếm được xem là nhanh nhất và tối ứu nhất trong các cấu trúc dữ liệu.
Đối với các cấu trúc dữ liệu khác, khi tìm kiếm sẽ duyệt từng phần tử rồi thực hiện so sánh các phần tử với nhau rồi thực hiện sắp xếp.
Vậy đối với cây nhị phân tìm kiếm nó sẽ thực hiện như thế nào? Các bạn hãy cùng mình tìm hiểu ngay thôi nhé.
Tìm kiếm trong cây nhị phân tìm kiếm
Trước khi thực hiện tìm kiếm, phải đảm bảo rằng các bạn đã khai báo và khởi tạo cấu trúc dữ liệu cây nhị phân. Đây là điều kiện cần đầu tiên khi thực hiện tìm kiếm.
Như các bạn đã biết thì cây nhị phân tìm kiếm sẽ lưu trữ các giá trị nhỏ hơn bên trái node gốc và các giá trị lớn hơn bên phải node gốc. Vậy khi tìm kiếm ta chỉ cần so sánh giá trị cần tìm với giá trị của node gốc. Nếu nhỏ hơn thì ta tìm bên trái, ngược lại lớn hơn thì ta tìm bên phải. Trong trường hợp bằng thì node gốc chính là giá trị cần tìm. Cụ thể như sau:
Đầu tiên chúng ta kiểm tra xem cây nhị phân có rỗng không nhé, nếu rỗng thì ta thông báo rồi kết thúc hàm. Nếu cây nhị phân không rỗng, khi đó ta chia làm ba trường hợp sau đây.
// nếu cây rỗng
if (t == NULL)
{
return NULL;
}Trường hợp 1: Phần tử x nhỏ hơn giá trị của node t (node gốc).
Ta thực hiện gọi đệ quy hàm TimKiem() để duyệt sang cây con bên trái để tìm phần tử x.
// nếu phần tử cần tìm kiếm mà nhỏ hơn node gốc thì duyệt(đệ quy) sang bên trái để tìm
if (x < t->data)
{
TimKiem(t->pLeft, x);
}Trường hợp 2: Phần tử x lớn hơn giá trị của node t.
Ta thực hiện gọi đệ quy hàm TimKiem() để duyệt sang cây con bên phải để tìm phần tử x.
else if (x > t->data) // duyệt sang bên phải
{
TimKiem(t->pRight, x);
}Trường hợp 3: Phần tử x bằng giá trị của node t.
Đối với trường hợp này, node t chính là giá trị cần tìm, vậy nên chỉ cần trả về t -> data.
else // <=> t->data == x
{
return t; // trả về node cần tìm kiếm
}Hàm tìm kiếm trong cây nhị phân tìm kiếm.
// nếu node có tồn tại trong cây thì trả về cái node đó - còn không tồn tại thì trả về NULL
NODE* TimKiem(TREE t, int x)
{
// nếu cây rỗng
if (t == NULL)
{
return NULL;
}
else
{
// nếu phần tử cần tìm kiếm mà nhỏ hơn node gốc thì duyệt(đệ quy) sang bên trái để tìm
if (x < t->data)
{
TimKiem(t->pLeft, x);
}
else if (x > t->data) // duyệt sang bên phải
{
TimKiem(t->pRight, x);
}
else // <=> t->data == x
{
return t; // trả về node cần tìm kiếm
}
}
}Ví dụ tìm kiếm trong cây nhị phân tìm kiếm
Trong phần này, mình sẽ thực một chương trình tìm kiếm phần tử trong cây nhị phân tìm kiếm. Chương trình sẽ áp dụng các kiến thức ở bài trước và vận dụng kiến thức vừa mới học trong bài này.
Cụ thể như sau:
- Khai báo và khởi tạo cấu trúc dữ liệu cây nhị phân tìm kiếm.
- Khai báo và khởi tạo cấu trúc node.
- Thêm node vào cây nhị phân tìm kiếm.
- Duyệt cây nhị phân tìm kiếm theo thứ tự Node - Left - Right.
- Tìm kiếm phần tử trong cây nhị phân tìm kiếm. Phần tử này được nhập bởi người dùng.
- Tạo menu với các yêu cầu trên.
Bây giờ chúng ta sẽ thực hiện từng yêu cầu nhé.
Bước 1: Khai báo và khởi tạo cấu trúc dữ liệu cây nhị phân tìm kiếm.
typedef struct node NODE;
typedef NODE* TREE;
// hàm khởi tạo cây nhị phân tìm kiếm
void KhoiTaoCay(TREE &t)
{
t = NULL;
}Bước 2: Khai báo và khởi tạo cấu trúc node.
// nhập vào cây nhị phân tìm kiếm các số nguyên
// khai báo cấu trúc 1 cái node trong cây nhị phân tìm kiếm
struct node
{
int data; // dữ liệu chứa trong 1 cái node
struct node *pLeft; // con trỏ liên kết với cái node bên trái <=> cây con trái
struct node *pRight; // con trỏ liên kết với cái node bên phải <=> cây con phải
};Bước 3: Thêm node vào cây nhị phân tìm kiếm.
// hàm thêm 1 cái phần tử vào cây
void ThemNodeVaoCay(TREE &t, int x)
{
// nếu cây rỗng
if (t == NULL)
{
NODE *p = new NODE;
p->data = x;
p->pLeft = NULL;
p->pRight = NULL;
t = p;
}
else
{
// nếu phần tử thêm vào mà nhỏ hơn nút gốc thì sẽ duyệt qua bên trái
if (x < t->data)
{
ThemNodeVaoCay(t->pLeft, x);
}
else if (x > t->data)
{
ThemNodeVaoCay(t->pRight, x);
}
}
}Bước 4: Duyệt cây nhị phân tìm kiếm theo thứ tự Node - Left - Right.
// hàm xuất phần tử trong cây nhị phân tìm kiếm
void NLR(TREE t)
{
if (t != NULL)
{
// xử lí
cout << t->data << " ";
NLR(t->pLeft);
NLR(t->pRight);
}
}Bước 5: Tìm kiếm phần tử trong cây nhị phân tìm kiếm.
// nếu node có tồn tại trong cây thì trả về cái node đó - còn không tồn tại thì trả về NULL
NODE* TimKiem(TREE t, int x)
{
// nếu cây rỗng
if (t == NULL)
{
return NULL;
}
else
{
// nếu phần tử cần tìm kiếm mà nhỏ hơn node gốc thì duyệt(đệ quy) sang bên trái để tìm
if (x < t->data)
{
TimKiem(t->pLeft, x);
}
else if (x > t->data) // duyệt sang bên phải
{
TimKiem(t->pRight, x);
}
else // <=> t->data == x
{
return t; // trả về node cần tìm kiếm
}
}
}Bước 6: Tạo menu với các thao tác trên.
// hàm nhập cây nhị phân tìm kiếm
void Menu(TREE &t)
{
int luachon;
while(true)
{
cout << "\n\n\t\t ============ MENU ============";
cout << "\n1. Nhập phần tử trong cây";
cout << "\n2. Duyệt cây";
cout << "\n3. Tìm kiếm phần tử trong cây";
cout << "\n0. Thoát";
cout << "\n\n\t\t ============= END =============";
cout << "\nNhập lựa chọn của bạn: ";
cin >> luachon;
if(luachon < 0 || luachon > 3){
cout<<"\nLựa chọn của bạn không hợp lệ";
}
else if (luachon == 1)
{
int x;
cout << "\nNhập giá trị: ";
cin >> x;
ThemNodeVaoCay(t, x);
}
else if (luachon == 2)
{
cout << "\n\t Cây nhị phân tìm kiếm\n";
NLR(t);
}
else if (luachon == 3)
{
int x;
cout << "\nNhập phần tử cần tìm kiếm: ";
cin >> x;
NODE *p = TimKiem(t, x);
if (p == NULL)
{
cout << "\nPhần tử " << x << " không tồn tại trong cây";
}
else
{
cout << "\nPhần tử " << x << " có tồn tại trong c";
}
}
else
{
break;
}
}
}Full code:
#include<iostream>
using namespace std;
// nhập vào cây nhị phân tìm kiếm các số nguyên
// khai báo cấu trúc 1 cái node trong cây nhị phân tìm kiếm
struct node
{
int data; // dữ liệu chứa trong 1 cái node
struct node *pLeft; // con trỏ liên kết với cái node bên trái <=> cây con trái
struct node *pRight; // con trỏ liên kết với cái node bên phải <=> cây con phải
};
typedef struct node NODE;
typedef NODE* TREE;
// hàm khởi tạo cây nhị phân tìm kiếm
void KhoiTaoCay(TREE &t)
{
t = NULL;
}
// hàm thêm 1 cái phần tử vào cây
void ThemNodeVaoCay(TREE &t, int x)
{
// nếu cây rỗng
if (t == NULL)
{
NODE *p = new NODE;
p->data = x;
p->pLeft = NULL;
p->pRight = NULL;
t = p;
}
else
{
// nếu phần tử thêm vào mà nhỏ hơn nút gốc thì sẽ duyệt qua bên trái
if (x < t->data)
{
ThemNodeVaoCay(t->pLeft, x);
}
else if (x > t->data)
{
ThemNodeVaoCay(t->pRight, x);
}
}
}
// hàm xuất phần tử trong cây nhị phân tìm kiếm
void NLR(TREE t)
{
if (t != NULL)
{
// xử lí
cout << t->data << " ";
NLR(t->pLeft);
NLR(t->pRight);
}
}
// nếu node có tồn tại trong cây thì trả về cái node đó - còn không tồn tại thì trả về NULL
NODE* TimKiem(TREE t, int x)
{
// nếu cây rỗng
if (t == NULL)
{
return NULL;
}
else
{
// nếu phần tử cần tìm kiếm mà nhỏ hơn node gốc thì duyệt(đệ quy) sang bên trái để tìm
if (x < t->data)
{
TimKiem(t->pLeft, x);
}
else if (x > t->data) // duyệt sang bên phải
{
TimKiem(t->pRight, x);
}
else // <=> t->data == x
{
return t; // trả về node cần tìm kiếm
}
}
}
// hàm nhập cây nhị phân tìm kiếm
void Menu(TREE &t)
{
int luachon;
while(true)
{
cout << "\n\n\t\t ============ MENU ============";
cout << "\n1. Nhập phần tử trong cây";
cout << "\n2. Duyệt cây";
cout << "\n3. Tìm kiếm phần tử trong cây";
cout << "\n0. Thoát";
cout << "\n\n\t\t ============= END =============";
cout << "\nNhập lựa chọn của bạn: ";
cin >> luachon;
if(luachon < 0 || luachon > 3){
cout<<"\nLựa chọn của bạn không hợp lệ";
}
else if (luachon == 1)
{
int x;
cout << "\nNhập giá trị: ";
cin >> x;
ThemNodeVaoCay(t, x);
}
else if (luachon == 2)
{
cout << "\n\t Cây nhị phân tìm kiếm\n";
NLR(t);
}
else if (luachon == 3)
{
int x;
cout << "\nNhập phần tử cần tìm kiếm: ";
cin >> x;
NODE *p = TimKiem(t, x);
if (p == NULL)
{
cout << "\nPhần tử " << x << " không tồn tại trong cây";
}
else
{
cout << "\nPhần tử " << x << " có tồn tại trong c";
}
}
else
{
break;
}
}
}
int main()
{
TREE t;
KhoiTaoCay(t);
Menu(t);
cout<<"\n-------------------------------------\n";
cout<<"Chương trình này được đăng tại codehow.net";
}Kết quả: Các phần tử trong cây chúng ta sẽ nhập từ bàn phím, ở đây mình đã nhập sẵn, các bạn có thể tự nhập cho mình nhé.
