Duyệt cây nhị phân tìm kiếm - Freetuts

Trong bài này mình sẽ trình làng những bạn những cách duyệt cây nhị phân tìm kiếm. Đây là một bước rất quan trọng để kiếm ra tác dụng và hiển thị những thành phần trong cây .

test php

banquyen png

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

freetuts.net

Bạn đang đọc: Duyệt cây nhị phân tìm kiếm – Freetuts

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

Chúng ta sẽ tìm hiểu và khám phá lần lượt 6 cách duyệt cây nhị phân tìm kiếm :

Duyệt NLR cây nhị phân tìm kiếm.
Duyệt NRL cây nhị phân tìm kiếm.
Duyệt LNR cây nhị phân tìm kiếm.
Duyệt RNL cây nhị phân tìm kiếm.
Duyệt LRN cây nhị phân tìm kiếm.
Duyệt RLN cây nhị phân tìm kiếm.

Tóm Tắt

1. Duyệt NLR cây nhị phân tìm kiếm

Trong phần này mình sẽ ra mắt những bạn duyệt cây theo cách NLR ( Node -> Left -> Right ) .
Giả sử tất cả chúng ta có một dãy số gồm có những số : 5, 1, 2, – 2, 6, 7. Ta sẽ thêm lần lượt những số này vào cây, sau khi thêm ta được cây như sau :Bài viết này được đăng tại [ không lấy phí tuts. net ]

duyet cay 2 PNG

Duyệt NLR là tất cả chúng ta sẽ triển khai xuất Node trước rồi thực thi cây con bên trái và cây con bên phải. Mình sẽ lấy ví dụ trên để thực thi duyệt NLR :

Đầu tiên ta vào Node đầu tiên là số 5, theo quy tắc NLR thì ta sẽ xuất số 5 ra rồi thực hiện duyệt Left.
Khi duyệt Left ta có một Node mới là số 1, theo quy tắc NLR thì ta sẽ xuất số 1 ra thồi thực hiện duyệt Left.
Tiếp tục duyệt Left ta có một số Node -2, theo quy tắc NLR thì ta xuất số -2 ra rồi thực hiện duyệt Left. Khi này Left không còn Node ta duyệt qua Right cũng không còn Node. Ta sử dụng đệ quy để quay lên duyệt Right ở Node số 1.
Duyệt Right ở Node số 1 ta có một Node 2, theo quy tắc NLR thì ta xuất số 2 ra và thực hiện duyệt Left. Left không còn phần tử nào ta duyệt qua Right cũng không còn phần tử nào. Khi đó ta sử dụng đệ quy quay lại Node số 5 để thực hiện duyệt Right.
Cứ như vậy ta duyệt Right Node số 5 ta được Node số 6 và Node số 7.

Sau khi duyệt theo tuần tự như vậy ta được một dãy số mới : 5, 1, – 2, 2, 6, 7. Khác với dãy số khởi đầu thêm vào cây, từ đây ta có một Tóm lại rằng :

Kết luận: Với mỗi cách duyệt khác nhau sẽ cho ra kết quả khác nhau, ta có tất cả 6 cách duyệt và các cách duyệt này đều cho ra kết quả khác nhau.

/* hàm xuất cây nhị phân theo NLR */
void Duyet_NLR(TREE t)
{ 
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		cout << t->data << " "; // xuất dữ liệu trong node
		Duyet_NLR(t->pLeft); // duyệt qua trái
		Duyet_NLR(t->pRight); // duyệt qua phải
	}
}

Kết quả: Thực hiên Code trong C++

duyet cay NLR PNG

2. Duyệt NRL cây nhị phân tìm kiếm.

Tương tự như duyệt NLR cây nhị phân, ta triển khai xuất lần lượt những Node theo thứ tự NRL .

Với dãy số như trên: 5, 1, 2, 2, 6, 7 ta thực hiện duyệt NRL. Sau khi duyệt ta được kết quả như sau: 5, 6, 7, 1, 2, -2.

Xem thêm: Laravel là gì? Giới thiệu Laravel 2021 cho những ai quan tâm

// hàm xuất cây nhị phân theo NRL
void Duyet_NRL(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		cout << t->data << " "; // xuất dữ liệu trong node
		Duyet_NRL(t->pRight); // duyệt qua phải 
		Duyet_NRL(t->pLeft); // duyệt qua trái
	}
}

Kết quả:

duyet cay NRL PNG

3. Duyệt LNR cây nhị phân tìm kiếm.

Duyệt LNR cây nhị phân tìm kiếm ta thực thi duyệt theo thứ tự Left -> Node -> Right. Ta sử dụng những số 5, 1, 2, – 2, 6, 7. Khi ta sử dụng cách này để triển khai duyệt cây, những thành phần sẽ được sắp xếp tăng dần khi xuất ra màn hình hiển thị .

// hàm xuất cây nhị phân theo LNR <=> xuất ra các phần tử từ bé đến lớn
void Duyet_LNR(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		Duyet_LNR(t->pLeft); // duyệt qua trái
		cout << t->data << "  "; // xuất giá trị của node
		Duyet_LNR(t->pRight); // duyệt qua phải
	}
}

Kết quả:

duyet cay LNR PNG

4. Duyệt RNL cây nhị phân tìm kiếm.

Duyệt RNL cây nhị phân tìm kiếm ta triển khai duyệt theo thứ tự Right -> Node -> Left. Sử dụng cách duyệt này sẽ cho tất cả chúng ta hiệu quả là một dãy số sắp xếp theo thứ tự giảm dần .

// hàm xuất cây nhị phân theo RNL <=> xuất ra các phần tử từ lớn đến bé
void Duyet_RNL(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		Duyet_RNL(t->pRight); // duyệt qua phải
		cout << t->data << "  "; // xuất giá trị của node
		Duyet_RNL(t->pLeft); // duyệt qua phải
	}
}

Kết quả:

duyet cay RNL PNG

5. Duyệt LRN cây nhị phân tìm kiếm.

Duyệt LRN cây nhị phân tìm kiếm ta thực thi duyệt theo thứ tự Left -> Right -> Node. Về cơ bản những cách duyệt này hoạt động giải trí tương tự như nhau, chỉ khác thứ tự duyệt mà thôi .

// hàm xuất cây nhị phân theo LRN
void Duyet_LRN(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		Duyet_LRN(t->pLeft); // duyệt qua trái
		Duyet_LRN(t->pRight); // duyệt qua phải
		cout << t->data << "  "; // xuất giá trị của node
	}
}

Kết quả:

duyet cay LRN PNG

6. Duyệt RLN cây nhị phân tìm kiếm.

Và ở đầu cuối tất cả chúng ta sẽ triển khai duyệt RLN cây nhị phân tìm kiếm. Ta cũng sẽ thực thi theo thứ tự Right -> Left -> Node, mình sẽ lấy ví dụ dãy số ở trên để chạy thử cho cách duyệt này nhé .

// hàm xuất cây nhị phân theo RLN
void Duyet_RLN(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		Duyet_RLN(t->pRight); // duyệt qua phải
		Duyet_RLN(t->pLeft); // duyệt qua trái
		cout << t->data << "  "; // xuất giá trị của node
	}
}

Kết quả:

Xem thêm: Sửa bảng với Migration Laravel 8

duyet cay RLN PNG

7. Code mẫu trong C++

#include
using namespace std;
// khai báo cấu trúc  1 cái node
struct node
{
	int data; // dữ liệu của node ==> dữ liệu mà node sẽ lưu trữ
	struct node *pLeft; // node liên kết bên trái của cây <=> cây con trái
	struct node *pRight; // node liên kết bên phải của cây <=> cây con phải
};
typedef struct node NODE;
typedef NODE* TREE;

// khởi tạo cây
void KhoiTaoCay(TREE &t)
{
	t = NULL; // cây rỗng
}

// hàm thêm phần tử x vào cây nhị phân
void ThemNodeVaoCay(TREE &t, int x)
{
	// nếu cây rỗng
	if (t == NULL)
	{
		NODE *p = new NODE; // khởi tạo 1 cái node để thêm vào cây
		p->data = x;// thêm dữ liệu x vào data
		p->pLeft = NULL;
		p->pRight = NULL;
		t = p;// node p chính là node gốc <=> x chính là node gốc
	}
	else // cây có tồn tại phần tử
 	{
		// nếu phần tử thêm vào mà nhỏ hơn node gốc ==> thêm nó vào bên trái
		if (t->data > x)
		{
			ThemNodeVaoCay(t->pLeft, x); // duyệt qua trái để thêm phần tử x
		}
		else if (t->data < x) // nếu phần tử thêm vào mà lớn hơn node gốc ==> thêm nó vào bên phải
		{
			ThemNodeVaoCay(t->pRight, x); // duyệt qua phải để thêm phần tử x
		}
	}
}

// hàm xuất cây nhị phân theo NLR
void Duyet_NLR(TREE t)
{ 
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		cout << t->data << " "; // xuất dữ liệu trong node
		Duyet_NLR(t->pLeft); // duyệt qua trái
		Duyet_NLR(t->pRight); // duyệt qua phải
	}
}

// hàm xuất cây nhị phân theo NRL
void Duyet_NRL(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		cout << t->data << " "; // xuất dữ liệu trong node
		Duyet_NRL(t->pRight); // duyệt qua phải 
		Duyet_NRL(t->pLeft); // duyệt qua trái
	}
}

// hàm xuất cây nhị phân theo LNR <=> xuất ra các phần tử từ bé đến lớn
void Duyet_LNR(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		Duyet_LNR(t->pLeft); // duyệt qua trái
		cout << t->data << "  "; // xuất giá trị của node
		Duyet_LNR(t->pRight); // duyệt qua phải
	}
}

// hàm xuất cây nhị phân theo RNL <=> xuất ra các phần tử từ lớn đến bé
void Duyet_RNL(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		Duyet_RNL(t->pRight); // duyệt qua phải
		cout << t->data << "  "; // xuất giá trị của node
		Duyet_RNL(t->pLeft); // duyệt qua phải
	}
}

// hàm xuất cây nhị phân theo LRN
void Duyet_LRN(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		Duyet_LRN(t->pLeft); // duyệt qua trái
		Duyet_LRN(t->pRight); // duyệt qua phải
		cout << t->data << "  "; // xuất giá trị của node
	}
}

// hàm xuất cây nhị phân theo RLN
void Duyet_RLN(TREE t)
{
	// nếu cây còn phần tử thì tiếp tục duyệt
	if (t != NULL)
	{
		Duyet_RLN(t->pRight); // duyệt qua phải
		Duyet_RLN(t->pLeft); // duyệt qua trái
		cout << t->data << "  "; // xuất giá trị của node
	}
}


// hàm nhập dữ liệu
void Menu(TREE &t)
{
	while (true)
	{
		cout << "\n\n\t\t =========== MENU ===========";
		cout << "\n1. Nhập dữ liệu cho cây: ";
		cout << "\n2. Duyệt cây NLR";
		cout << "\n3. Duyệt cây NRL";
		cout << "\n4. Duyệt cây LNR";
		cout << "\n5. Duyệt cây RNL";
		cout << "\n6. Duyệt cây LRN";
		cout << "\n7. Duyệt cây RLN";
		cout << "\n0. Thoát";
		cout << "\n\n\t\t ============================";

		int luachon;
		cout << "\nNhập lựa chọn của bạn: ";
		cin >> luachon;
		if (luachon < 0 || luachon > 7)
		{
			cout << "\nLựa chọn không hợp lệ";
		}
		else if (luachon == 1)
		{
			int x;
			cout << "\nNhập số nguyên x: ";
			cin >> x;
			ThemNodeVaoCay(t, x);
		}
		else if (luachon == 2)
		{
			cout << "\nDuyệt cây theo NLR\n";
			Duyet_NLR(t);
		}
		else if (luachon == 3)
		{
			cout << "\nDuyệt cây theo NRL\n";
			Duyet_NRL(t);
		}
		else if (luachon == 4)
		{
			cout << "\nDuyệt cây theo LNR\n";
			Duyet_LNR(t);
		}
		else if (luachon == 5)
		{
			cout << "\nDuyệt cây theo RNL\n";
			Duyet_RNL(t);
		}
		else if (luachon == 6)
		{
			cout << "\nDuyệt cây theo LRN\n";
			Duyet_LRN(t);
		}
		else if (luachon == 7)
		{
			cout << "\nDuyệt cây theo RLN\n";
			Duyet_RLN(t);
		}
		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 luận

Như vậy là tất cả chúng ta đã thực thi xong những cách duyệt cây nhị phân. Tuy nhiên trong mỗi trường hợp khác nhau ta cần sử dụng cách duyệt khác nhau, những bạn hãy sử dụng nó một cách linh động. Như những bạn đã thấy thì mỗi cách duyệt đều cho ra hiệu quả khác nhau mặc dầu nguồn vào của nó là giống nhau .
Ở bài tiếp theo mình sẽ hướng dẫn những bạn cách tìm kiếm trong cây, đây là một thao tác được xem như thể đặc biệt quan trọng nhất của cây nhị phân tìm kiếm ( như cái tên của nó ). Các bạn hãy chú ý quan tâm theo dõi nhé ! !

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

admin

final-blade.com