CÂY NHỊ PHÂN
CÂY ĐỎ ĐEN
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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:

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.
  • 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:

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 << "\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à 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é !!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

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

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ẽ giới thiệu các bạn cách tìm kiếm một Node…

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…

Top