Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ ra mắt những 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 quan trọng nhất trong cây nhị phân tìm kiếm, vì nó được triển khai một cách thuận tiện và nhanh gọn .

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

Bạn đang đọc: Tìm kiếm Node trên cây nhị phân tìm kiếm

, không được copy dưới mọi hình thức.

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

Tóm Tắt

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

Như những bạn đã biết thì thao tác tìm kiếm là một thao tác rất thông dụng trong những cấu trúc tài 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 những bạn hãy cùng mình tìm hiểu và khám phá xem cách tìm kiếm trong cây nhị phân tìm kiếm như thế nào nhé .
Để triển khai tìm kiếm tiên phong những bạn phải nắm được cấu trúc tàng trữ của cây nhị phân tìm kiếm như thế nào, khi đó những bạn mới dựa vào đó để tìm kiếm. Khi tàng trữ những thành phần nhỏ hơn Node gốc ( root ) được tàng trữ ở cây con trái và những thành phần 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 thi so sánh với root để tìm .

tim kiem cay 1 PNG

Việc tìm kiếm một Node trong cây đơn thuần chỉ là kiểm tra xem thành phần đó còn sống sót 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ó thành phần thì khi đó ta khởi đầu thực thi tìm kiếm. Ta sẽ có 3 trường hợp khi thực thi 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.

Xem thêm: Vòng lặp for trong C++ (có bài tập thực hành)

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 thuầ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 thành phần x trong cây nhị phân, mình sẽ triển khai tìm kiếm 1 số ít nguyên x trong cây số nguyên gồm có những số sau : 3, 5, – 2, 0, 9, 6, 8 .
Giả sử mình cần tìm số 8 trong dãy những số trên, khi đó việc tìm kiếm sẽ triển khai theo những bước sau : Biểu diễn bằng mũi tên màu đỏ .

tim kiem cay 2 PNG

Đầ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 thế cho nên gọi đệ quy và duyệt sang cây con phải .
Đến đây liên 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 liên 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
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 Freetuts.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.

Xem thêm: Các kiểu dữ liệu trong C++ và cách khai báo

tim kiem cay 3 PNG

3. Kết luận

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

Source: https://final-blade.com
Category: Kiến thức Internet

admin

final-blade.com