Duyệt Cây Nhị Phân Tìm Kiếm - Freetuts

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.

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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 [free tuts .net]

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++

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ả:

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ả:

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ả:

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ả:

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ả:

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é !!