ìm kiếm Node trên cây nhị phân tìm kiếm - Cấu trúc cây

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node trên cây nhị phân tìm kiếm. Đây là thao tác đặc biệt nhất trong cây nhị phân tìm kiếm, vì nó được thực hiện một cách dễ dàng và nhanh chóng.

Chúng ta sẽ tìm hiều về cách hoạt động của hàm tìm kiếm trong cây như thế nào, sau đó thực hiện một ví dụ tìm kiếm cụ thể để các bạn hiểu rõ hơn.

1. Tìm kiếm Node trong cây nhị phân tìm kiếm

Như các bạn đã biết thì thao tác tìm kiếm là một thao tác rất phổ biến trong các cấu trúc dữ liệu. Mỗi cấu trúc có mỗi cách tìm kiếm khác nhau, trong phần này các bạn hãy cùng mình tìm hiểu xem cách tìm kiếm trong cây nhị phân tìm kiếm như thế nào nhé.

Để thực hiện tìm kiếm đầu tiên các bạn phải nắm được cấu trúc lưu trữ của cây nhị phân tìm kiếm như thế nào, khi đó các bạn mới dựa vào đó để tìm kiếm. Khi lưu trữ các phần tử nhỏ hơn Node gốc (root) được lưu trữ ở cây con trái và các phần tử lớn hơn root được lưu ở cây con phải. Vì vậy khi tìm kiếm ta cũng thực hiện so sánh với root để tìm.

Việc tìm kiếm một Node trong cây đơn giản chỉ là kiểm tra xem phần tử đó còn tồn tại trong cây hay không, nếu có thì trả về Node đó, ngược lại nếu không thì trả về NULL.

Ta có một hàm TimKiem() với tham số truyền vào là một cây t và một số nguyên x (ta sẽ tìm một số nguyên x trong cây số nguyên).

Việc đầu tiền là ta sẽ kiểm tra xem cây rỗng hay không, nếu cây rỗng thì trả về NULL, nếu cây có phần tử thì khi đó ta bắt đầu thực hiện tìm kiếm. Ta sẽ có 3 trường hợp khi thực hiện tìm kiếm trong cây:

Trường hợp 1: Phần tử x cần tìm kiếm nhỏ hơn t -> data.

Khi đó ta sẽ thực hiện gọi đệ quy hàm TimKiem() để duyệt sang bên cây con trái đề tìm phần tử x.

Trường hợp 2: Phần tử x cần tìm kiếm lớn hơn t -> data.

Khi đó ta sẽ thực hiện gọi đệ quy hàm TimKiem() để duyệt sang bên cây con phải để tìm phần tử x.

Trường hợp 3: Phần tử x cần tìm kiếm bằng t -> data.

Trong trường hợp này đơn giản ta chỉ cần trả về t -> data, vì đây chính là giá trị cần tì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
		}
	}

}

2. Ví dụ: Tìm kiếm phần tử x trong cây nhị phân tìm kiếm

Trong ví dụ về tìm kiếm phần tử x trong cây nhị phân, mình sẽ thực hiện tìm kiếm một số nguyên x trong cây số nguyên bao gồm các số sau: 3, 5, -2, 0, 9, 6, 8.

Giả sử mình cần tìm số 8 trong dãy các số trên, khi đó việc tìm kiếm sẽ thực hiện theo các bước sau: Biểu diễn bằng mũi tên màu đỏ.

Đầu tiên nó sẽ so sánh số 8 (số cần tìm) với root là số 3, vì 8 > 3 nên nó sẽ gọi đệ quy và duyệt sang cây con phải. Tiếp tục so sánh với số 5, 8 > 5 vì vậy gọi đệ quy và duyệt sang cây con phải.

Đến đây tiếp tục so sánh với số 9, khi này 8 < 9 nên sẽ gọi đệ quy và duyệt sang trái. Khi duyệt sang trái tiếp tục só sánh với số 6 , vì 8 > 6 nên sẽ gọi đệ quy và duyệt qua bên phải. Đến đây khi so sánh thì số cần tìm là số 8 lại bằng chính với t -> data, khi đó đã tìm thấy số 8.

#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 << "

		 ============ MENU ============";
		cout << "
1. Nhập phần tử trong cây";
		cout << "
2. Duyệt cây";
		cout << "
3. Tìm kiếm phần tử trong cây";
		cout << "
0. Thoát";
		cout << "

		 =============  END  =============";

		cout << "
Nhập lựa chọn của bạn: ";
		cin >> luachon;

    if(luachon < 0 || luachon > 3){
      cout<<"
Lựa chọn của bạn không hợp lệ";
    }
		else if (luachon == 1)
		{
			int x;
			cout << "
Nhập giá trị: ";
			cin >> x;
			ThemNodeVaoCay(t, x);
		}
		else if (luachon == 2)
		{
			cout << "
	 Cây nhị phân tìm kiếm
";
			NLR(t);
		}
		else if (luachon == 3)
		{
			int x;
			cout << "
Nhập phần tử cần tìm kiếm: ";
			cin >> x;
			NODE *p = TimKiem(t, x);
			if (p == NULL)
			{
				cout << "
Phần tử " << x << " không tồn tại trong cây";
			}
			else
			{
				cout << "
Phần tử " << x << " có tồn tại trong c";
			}
		}
		else
		{
			break;
		}
	}
}


int main()
{
	TREE t;
	KhoiTaoCay(t);
	Menu(t);

	cout<<"
-------------------------------------
";
        cout<<"Chương trình này được đăng tại Zaidap.com.net";
}

Kết quả: Thực hiện kiểm tra hai số x = 0 và x = 10 trong dãy số: 3, 5, -2, 0, 9, 6, 8.

3. Kết luận

Như vậy là chúng ta đã tìm hiểu xong về cách tìm kiếm phần tử trong cây nhị phân tìm kiếm. Ở ví dụ trên mình thực hiện tìm kiếm số nguyên x trong cây số nguyên, các bạn có thể tự thực hành bằng cách tìm số nguyên tố trong cây số nguyên để có thể luyện tập. Ở bài tiếp theo mình sẽ tiếp tục thực hiện các thao tác thường gặp trong cây nhị phân, các bạn hay chú ý theo dõi nhé !!