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

Trong bài này mình sẽ giới thiệu các bạn các 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 kết quả và hiển thị các phần tử trong cây.

Chúng ta sẽ tìm hiểu 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.

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

Trong phần này mình sẽ giới thiệu các bạn duyệt cây theo cách NLR (Node -> Left -> Right).

Giả sử chúng ta có một dãy số bao gồm các số: 5, 1, 2, -2, 6, 7. Ta sẽ thêm lần lượt các 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 [kiso.vn]

duyet cay 2 PNG

Duyệt NLR là chúng ta sẽ thực hiện xuất Node trước rồi thực hiện 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 hiện duyệt NLR:

  1. Đầ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.
  2. 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.
  3. 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.
  4. 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.
  5. 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ố ban đầu thêm vào cây, từ đây ta có một kết luận 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 thực hiện xuất lần lượt các 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.

// 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 hiện duyệt theo thứ tự Left -> Node -> Right. Ta sử dụng các số 5, 1, 2, -2, 6, 7. Khi ta sử dụng cách này để thực hiện duyệt cây, các phần tử sẽ được sắp xếp tăng dần khi xuất ra màn hình.

// 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 thực hiện duyệt theo thứ tự Right -> Node -> Left. Sử dụng cách duyệt này sẽ cho chúng ta kết 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 hiện duyệt theo thứ tự Left -> Right -> Node. Về cơ bản các cách duyệt này hoạt động tương tự 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à cuối cùng chúng ta sẽ thực hiện duyệt RLN cây nhị phân tìm kiếm. Ta cũng sẽ thực hiện 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ả:

duyet cay RLN PNG

7. Code mẫu trong C++

#include<iostream>
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 << "nntt =========== 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 << "nntt ============================";

		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 NLRn";
			Duyet_NLR(t);
		}
		else if (luachon == 3)
		{
			cout << "nDuyệt cây theo NRLn";
			Duyet_NRL(t);
		}
		else if (luachon == 4)
		{
			cout << "nDuyệt cây theo LNRn";
			Duyet_LNR(t);
		}
		else if (luachon == 5)
		{
			cout << "nDuyệt cây theo RNLn";
			Duyet_RNL(t);
		}
		else if (luachon == 6)
		{
			cout << "nDuyệt cây theo LRNn";
			Duyet_LRN(t);
		}
		else if (luachon == 7)
		{
			cout << "nDuyệt cây theo RLNn";
			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 Kiso.vn";
}

Kết luận

Như vậy là chúng ta đã thực hiện xong các 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, các bạn hãy sử dụng nó một cách linh hoạt. Như các bạn đã thấy thì mỗi cách duyệt đều cho ra kết quả khác nhau mặc dù đầu vào của nó là giống nhau.

Ở bài tiếp theo mình sẽ hướng dẫn các bạn cách tìm kiếm trong cây, đây là một thao tác được xem như là đặc biệt 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ú ý theo dõi nhé !!

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *